CSCI 5220
Spring 2016
Practice Questions for Exam 3

G is the following grammar, with start nonterminal S. Symbols 'x' ',' '(' and ')' are tokens.

1. S → '(' L ')'
2. S → 'x'
3. L → S R
4. R → ε
5. R → ',' L

  1. Define FIRST(S), FIRST(L) and FIRST(R) for grammar G.

    Answer.

  2. Define FOLLOW(S), FOLLOW(L) and FOLLOW(R) for G.

    Answer.

  3. Show an LL(1) parsing table for G.

    Answer.

  4. Write a recursive-descent parser for G. Assume that function match(t) is available, and that the lookahead token is in global variable lookahead. The lookahead will be '$' at the end of the input.

    Make each of your functions return the total number of 'x' tokens in the part of the input that it matches.

    If your parser encounters a syntax error, make it call syntax_error(). syntax_error() will not return.

    Answer.

H is the following grammar, with start nonterminal S. Symbols 'a', 'b' and 'c' are tokens.

1. S → 'a' S 'a'
2. S → 'b' S 'b'
3. S → L
4. L → ε
5. L → 'c' L

  1. Define FIRST(S) and FIRST(L) for grammar H.

    Answer.

  2. Define FOLLOW(S) and FOLLOW(L) for H.

    Answer.

  3. Show an LL(1) parsing table for H.

    Answer.

  4. Write a recursive-descent parser for H. Assume that function match(t) is available, and that the lookahead token is in global variable lookahead. The lookahead will be '$' at the end of the input.

    Make each of your functions return the total number of 'c' tokens in the part of the input that it matches.

    If your parser encounters a syntax error, make it call syntax_error(). syntax_error() will not return.

    Answer.