Sample Exam Questions

1. Explain what it is about a given context-free grammar that would cause a problem for a top-down parser, and give a string for which an LL(1) parser would fail for this grammar. Modify the grammar so that it can be parsed by a top-down parser.

2. Construct First and Follow sets for a given grammar.

3. Construct a non-deterministic, bottom-up parser for a given grammar.

4. Given a grammar, an LR parse table, and a string in the language defined by the grammar, show the moves the parser would make to recognize the string. Then draw the parse tree for the parse.

5. Show that the following grammar is not LR(0):

<List> -> ID [ <Elist> ]
<Elist> -> ID
<Elist> -> <Elist> , ID

5. Given a grammar, describe the entries that will be made in a parse table in rows labeled by specified non-terminals.

6. Consider the grammar G = ({A}, {a,b,c}, P, A), where P contains

     A -> AaA
     A -> AbA
     A -> c

Is this grammar ambiguous? If it is ambiguous, change it to be unambiguous, but still generate the same set of strings.

7. Construct a non-deterministic top-down push-down automaton (NPDA) for the grammar S -> 0S1 | c. Show a trace of the machine moves for the input string 00c11.

8. Explain what it is about the grammar below that would cause a problem for a top-down parser, and why. Construct an equivalent grammar that will not present this problem for a top-down parser.

<stmt> ::= EXEC BEGIN <decl-list> ; <stmt-list> END
<stmt-list> ::= <stmt-list> ; <stmt> | <stmt>

9. An LL(1) parse table M is constructed by the following rules:

FOR EACH PRODUCTION A -> a, DO THE FOLLOWING:
1. For each a in FIRST(a), add A -> a to M[A,a].
2. If e is in FIRST(a), add A -> a to M[A,b] for each terminal b in FOLLOW(A).
3. If e is in FIRST(a) and $ is in FOLLOW(A), add A -> a to M[A,$].
4. Each undefined entry is set to error.

For each of rules l, 2, and 3 (not 4), explain the rationale behind the construction of the table entries the rule describes, in terms of the way the LL(1) parser uses the table and the contents of FIRST and FOLLOW sets.

10. Indicate whether or not a given grammar is LL(1), and explain why or why not.