Writing an interpreter for a full programming language is a big job, and not something that we'll have time for in this class. However, for this assignment you'll write a small parser that will just determine if a particular piece of code is valid or invalid.
The language that you'll parse is one that consists of function calls in "traditional" format, i.e. where the function name appears to the left of the parentheses, and the arguments to the function call are separated by commas. One unusual aspect of this language is that it uses the keyword "call" to indicate a function is being called. Another unusual aspect of this language is that is allows arguments to be missing. Here are some samples:
call f ( ) call f ( x , y , z ) call f ( x , , z ) call f ( x , call g ( a , b , c ) , z )
You might notice that every lexeme is separated from all others via spaces. This is in order to make scanning the code simple, as opposed to making you have to write further code to separate parentheses from function names, and so on.
Here is the BNF for the tokenized version of this language, which should make the above description precise.
<funcall> ::= call id ( <args> ) <arg> ::= id | <funcall> | ε <args> ::= <arg> <args_tail> <args_tail> ::= , <args> | ε
Note that id is a token. When you scan your code, you should assume that any symbol you see that is not a comma, a parenthesis, or the word "call" should be tokenized as an id.
Determine all FIRST, FOLLOW, and PREDICT sets for this grammar. Explain how your answers verify that this grammar is LL(1). Turn in your answers to this on paper at the beginning of class.
Optional bonus question, just for fun: When I first designed this language, I did not have the call keyword in there. As I started to work through the assignment, I decided to add it. Why? More precisely, why is this assignment harder without it?
Followup optional bonus question, just for fun: Does the previous question, if you think you see the answer, provide any insight as to why Scheme does parentheses in the way that it does?
Write a program in Python called parsefun.py that takes as input the name of a file with a program in this language that we've created, and implements recursive-descent parsing to determine whether or not the program is syntactically correct. Your program should print to the screen "Correct" or "Error" as appropriate. Printing out the right one of those single words is as far as you need to go for this assignment, but if you want to try to additionally print out diagnostic information that would be helpful to the programmer when debugging (such as the nature of the error) go for it!
You should feel free (and encouraged) to modify the Python parsers that we work with in class. You don't need to start this from scratch.