CSE P 501 23au Homework 3 - LR and LL Grammars & Parsing
Due: Monday, October 23 by 11 pm. Please
use Gradescope (gradescope.com
,
also linked from the CSE P 501 resources web page) to submit
your homework online. Gradescope's web site has several
instructional videos and help pages to outline the process,
and this guide has
specific information about scanning and uploading pdf files
containing assignments.
- Unreadable solutions cannot be graded--no blurry photos,
poor contrast, or illegible handwriting, please.
- Type-written solutions are encouraged but not required.
- If possible, don't split the solution to a problem across a page break.
We suggest you show your work to help us award partial credit
if appropriate, and for TA sanity. You should do this
assignment individually.
- The following is a grammar that generates epithets (E). An epithet is
a description (D). A description can be either a trait (T) or a simile
(S). Similies are of the form "trait like animal" (A).
E ::= D
D ::= T | S
S ::= T like
A
T ::= quick
| strong
A ::= bunny
| ox
- Construct the LR(0) state diagram and parse table for this grammar.
- Calculate FIRST, FOLLOW, and nullable for each non-terminal.
- Construct the SLR parse table.
- Is this grammar LR(0)? SLR?
- Consider the following grammar:
A ::= s
C n
g
| ε
B ::= C r
| t
C ::= B i
| t
Does this grammar satisfy the LL(1) condition? Justify
your answer. If it does not, change the grammar to make it
LL(1) without changing the language that it generates.
- Write a grammar that generates the straight-line code
language given below, but that is suitable for LL(1)
parsing. That is, eliminate the ambiguity, eliminate the left
recursion, and (if necessary) left-factor.
S ::= S ;
S
S ::= id
:=
E
S ::= print(
L )
E ::= id
E ::= num
E ::= E +
E
E ::= (
S ,
E )
L ::= E
L ::= L ,
E