CS374: Programming Language Principles - Parsers and Interpreters
Activity Goals
The goals of this activity are:- To explain the limitations of an LL(1) parser
- To remove left recursion and to left factor a grammar for LL(1) parsing, where possible
The Activity
Directions
Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.Model 1: An LL(1) Parser Implemented with Recursive Descent
Questions
- Try this example with some sample calculations.
- An LL(1) parser requires a grammar with no left recursion, and with unique nonterminals starting each production. Are these requirements met? If not, on what inputs will this parser fail? How can we fix it?
- Typically, a scanner functions pops each token, stores it in a variable, and returns the type of constant read. Modify this program to include a function
addsubthat pops a token and returns a constant representing the type of token found (either a'+'or a'-'character). - Move the scanning functions to a separate
.cfile with a corresponding header, and include that header from the scanner code module and main parser code module. Don't forget to use an include guard to ensure that the file is only included once during compilation.
Consider the expression 6+6-4+3. This should result in 11, but our parser incorrectly returns 5. Why is this? Consider this alteration to our grammar:
expr: term (addsub term)*
And consider the reuslting change to our implementation:
int expr() {
printf("In expr\n");
// Start with the first term
int value = term();
token = peek();
// Handle all '+' and '-' operators iteratively
while (token == '+' || token == '-') {
if (token == '+') {
pop(); // Consume '+'
value += term(); // Evaluate the next term and add
} else if (token == '-') {
pop(); // Consume '-'
value -= term(); // Evaluate the next term and subtract
}
token = peek();
}
printf("Expression value: %d\n", value);
return value;
}
What about this revision addresses the issue in our original grammar?