![university of washington logo](/images/UW_Wordmark_Left_White.png)
CSE 401/M501 18sp Homework 3 - LL Grammars & Parsing
Due: Sunday, April 29 by 11 pm. No late assignments accepted, even if you have late days remaining so we can discuss solutions before the midterm on Wednesday, May 2. Please use Gradescope (linked from the CSE 401 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.
- (Cooper & Torczon Sec. 3.3 ex. 5) Consider the following grammar:
A ::= B a B ::= dab B ::= C b C ::= c B C ::= A c
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
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX
Comments to admin