Answers to Self-Study Questions

Test Yourself #1

   grammar: S -> epsilon | ( S ) | [ S ]

   parse table:
      
           (         )       [        ]       EOF
       +--------------------------------------------
     S | ( S ) | epsilon | [ S ] | epsilon | epsilon
       +--------------------------------------------


   input seen so far   stack         action
   -----------------   -----         ------
         [              S EOF       pop, push "[S]"
         [              [S] EOF     pop, scan (top-of-stack term matches curr token)
         [[             S] EOF      pop, push "[S]"
         [[             [S]] EOF    pop, scan (top-of-stack term matches curr token)
         [[]            S]] EOF     pop, push epsilon (no push)
         [[]            ]] EOF      pop, scan (top-of-stack term matches curr token)
         [[]]           ] EOF       pop, scan (top-of-stack term matches curr token)
         [[]] EOF       EOF         pop, scan (top-of-stack term matches curr token)
         [[]] EOF                   empty stack: input accepted!

Test Yourself #2

• The original grammar is:
  exp -> ( exp ) | exp exp | ( )

• After left-factoring, the grammar becomes:
  exp -> ( exp' | exp exp
  exp' -> exp ) | )

• After removing immediate left-recursion, the grammar becomes:
  exp -> ( exp' exp''
  exp'' -> exp exp'' | epsilon
  exp' -> exp ) | )

Test Yourself #3

Question 1:

X                                   First(X)                Follow(X)
---------------------------------------------------------------------
methodHeader                        VOID                    EOF

paramList                           epsilon, ID             RPAREN

nonEmptyParamList                   ID                      RPAREN

VOID ID LPAREN paramList RPAREN     VOID

epsilon                             epsilon

nonEmptyParamList                   ID

ID ID                               ID

ID ID COMMA nonEmptyParamList       ID

Question 2: Note: To save space, the tokens "(" and ")" are used instead of LPAREN and RPAREN.

input seen so far   stack                           action
-----------------   -----                           ------
 VOID               methodHeader EOF                pop,
                                                    push "VOID ID ( paramList )"

 VOID               VOID ID ( paramList ) EOF       pop, scan (top-of-stack term matches curr token)

 VOID ID            ID ( paramList ) EOF            pop, scan (top-of-stack term matches curr token)

 VOID ID (          ( paramList ) EOF               pop, scan (top-of-stack ter

 VOID ID ( )        paramList ) EOF                 pop,
                                                    push nothing; i.e.,
                                                    choose production paramList -> epsilon
                                                    because ) is in Follow(paramList)
                                                    
 VOID ID ( )        ) EOF                           pop, scan (top-of-stack term matches curr token)

 VOID ID ( ) EOF    EOF                             pop, scan (top-of-stack term matches curr token)

 VOID ID ( ) EOF                                    empty stack: input accepted!

Test Yourself #4

      a     b     c     d     EOF        
   +-----------------------------+
 S | B c |     | B c | D B |     |
   | D B |     | D B |     |     |
   |-----|-----|-----|-----|-----| 
 B | a B |     | c S |     |     |
   |     |     |     |     |     |
   |-----|-----|-----|-----|-----| 
 D |epsil|     |epsil| d   |     |
   |     |     |     |     |     |
   +-----------------------------+

Test Yourself #5

Question 1(a):

A  |	First(A)	       |  Follow(A)
==============================================
S  |	epsilon, a, c, d       |  EOF, a, c, d
---+---------------------------+---------------
X  |	epsilon, a, c, d       |  a, c, d
---+---------------------------+---------------
Y  |	epsilon, a             |  b, c, d
---+---------------------------+---------------
Z  |	c, d                   |  EOF, a, c, d
---+---------------------------+---------------

Note that we have these dependences when computing Follow sets (i.e., everything in the left-side set must be put into the right-side set):

Follow(X) → Follow(S) // because of grammar rule (4)
Follow(S) → Follow(Z) // because of grammar rule (2)

Question 1(b):

   |     a     |    b   |    c    |    d    |    EOF
===============+========+=========+=========+=========
S  |   (1)(2)  |        |  (1)(2) |  (1)(2) |   (1)
---+-----------+--------+---------+---------+---------
X  |   (3)(4)  |        |  (3)(4) |  (3)(4) |
---+-----------+--------+---------+---------+---------
Y  |    (6)    |   (5)  |   (5)   |   (5)   |
---+-----------+--------+---------+---------+---------
Z  |           |        |   (7)   |   (8)   |
---+-----------+--------+---------+---------+---------