Goals
Understand how some grammars require back-tracking to parse because it isn't possible to predict perfectly which production should be used.
Understand how to do parsing using table-driven parsing and recursive descent parsing for LL(1) grammars
Concepts
Recursive descent parsing
Backtracking and the use of a stack in parsing
LL(1) grammars
FIRST and FOLLOW sets
Constructing a table for table-driven parsing with and without FIRST and FOLLOW sets
Using the call stack via recursive function calls in recursive-descent parsing
Problems
(4 points) Do a brute force search to find a parse tree for the input int / int. Use a top-down approach meaning you begin with the start rule (i.e., the first rule), and find a left-derivation. When choosing which rule to use in an expansion, go in order of the rules. The int terminal is an integer literal).
<E> ::= <T> - <E> | <T>
<T> ::= ( <E> ) | int | int / <T>
(2 points) Compute the FIRST sets for the following. Compute FOLLOW sets as well for extra credit.
<A> ::= <A><A>'+' | <A><A>'*' | a
(6 points) For each of the following grammars, build an LL(1) parse table. You may left-factor and/or eliminate left-recursion from your grammars first if needed:
S –> 0 S 1 | 0 1
S –> + S S | * S S | a
S –> S ( S ) S | lambda
(8 points) Build the LL(1) parse table for the following grammar with start symbol X. You may left-factor or remove left-recursion if needed.
<X> ::= (<P>)
<P> ::= <Z><P> | <Z>
<Z> ::= 0 | 1
(4 points) The following is a grammar describes a language for regular expressions over symbols a and b; the language uses +-sign in place of a |-sign for union. As such the use of the |-sign is part of the BNF syntax while the +-sign is part of the language being defined by the grammar:
<rexpr> ::= <rexpr> '+' <rterm> | <rterm>
<rterm> ::= <rterm> <rfactor> | <rfactor>
<rfactor> ::= <rfactor> '*' | <rprimary>
<rprimary> ::= 'a' | 'b'
Is the grammar ready for LL(1) parsing (i.e., are you able to create a parse table with no non-determinism)? If yes, then justify your answer. If no, then modify the grammar so it is LL(1).
Back to top
search
