Here's a question I asked on the midterm in 2006. It's probably a pretty good indication of the sort of thing you should be able to do on the midterm this year.
Consider the following grammar. (The terminal symbols are $ (end-of-file), i , “+”, and “;”. "epsilon" is used to mark an empty right-hand-side.)
Pgm ::= Block $
Block ::= Block E Sep
Block ::= E Sep
E ::= E "+" i
E ::= i
Sep ::= ";"
Sep ::= epsilon
Part a (5 points): Which of the following strings are accepted by the grammar?
i + i ; i + i
i i i ; i i
; i ; i
i + + i ;
i + i + i ;
Part b (15 points): Show that the grammar is not LR(0), but an LR(0) conflict is resolved using LALR(1) lookahead. (Just show enouggh states to show how one conflict in the LR(0) machine is resolved in the LALR(1) machine.)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment