A4, CSE3322, 2006

Purpose: Mastering [LR parsing], Imp VII+, p.118+.

Due 4pm Monday 16 October 2006.

 

Consider the grammar with terminal symbols a, b, and c, non-terminal symbols S, X, and Y where S is the start symbol, and the following production rules

Number Production 1 S -> X c Y 2 Y -> X Y 3 Y -> b X 4 X -> a X 5 X -> a

(a) In words, describe the members of the language defined by this grammar.

[0-marks]

 

(b) Is the language regular? If so give a regular expression that defines the same language. If not explain why it is not.

[1-marks]

 

(c) Give the canonical collection of LR(0) items for this grammar. Apply exactly the algorithm in the lecture notes ([Imp.VIII] p.140+) and use the grammar symbols in the order S, X, Y, a, b, c.

[1-marks]

 

(d) Fill in the SLR parsing table for the grammar. (You might not need all the rows.)

[2-marks]

STATE ACTION GOTO abc$ SXY 0         1         2         3         4         5         6         7         8         9         10         11         12         13         14         15        

(e) Detail how the sentence aacba would be parsed by an LR parser using the table from the previous part. For each step of the process give the input, the parser action (shift/reduce) and the stack in the table below.

[1-marks]

ACTION STACK INPUT start                                                                                              

(You might not need all the rows of the table.)

 

Submission:

Due 4pm Monday 16 October,

on paper(!), submitted through the general office in building 75,

counts for 5% of the cse3322 final mark.

Hints