New version page

LSU CSC 4351 - HW 2: Syntax Analysis

This preview shows page 1 out of 2 pages.

View Full Document
View Full Document

End of preview. Want to read all 2 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

HW 2: Syntax AnalysisCSC 4351, Spring 2018Due: 28 February 20181. Context free grammars, LL and LR parsingConsider the following simple context free grammars:Grammar G1Grammar G2G → A$ G → A$A →  A → A → bAb A → AbbThe start symbols are G, the nonterminals are G and A, and the terminal symbols are b and $ (end offile). Note that these grammars generate the same language: strings consisting of even numbers of bsymbols (including zero of them).(a) Attempt to show a shift-reduce parse of the input string bbbb for a parser for grammar G1. Showthe contents of the stack, the input, and the actions (in the style of Figure 3.18 on Page 58 butwithout the subscripts for the parse states).Indicate any conflicts and describe why they are conflicts. Is G1LR(1)? Is it LR(0)?(b) Attempt to show a shift-reduce parse of the input string bbbb for a parser for grammar G2. Showthe contents of the stack, the input, and the actions (in the style of Figure 3.18 on Page 58 butwithout the subscripts for the parse states).Indicate any conflicts and describe why they are conflicts. Is G2LR(1)? Is it LR(0)?(c) Indicate whether G1and G2are LL(1). You don’t need to construct their LL(1) parse tables, butyou may argue from other properties.(d) Of the language classes we have discussed in class, what is the smallest category into whichL(G1) fits? Justify your answer. [Hint: This is a trick question!]12. Context free grammars, LL parsingConsider the following grammar:E → E + T | TT → id | id() | id(L)L → E, L | EThe nonterminals are E, T , and L. The terminals are +, id, (, ), ;. The start symbol is E.(a) Modify the grammar such that it can be parsed by an LL(1) parser.(b) Show Nullable, FIRST, and FOLLOW and derive the LL(1) parse table for the modified gram-mar.(c) Give the (non-abstract) parse tree produced by your grammar for the inputa + b(c,


View Full Document
Loading Unlocking...
Login

Join to view HW 2: Syntax Analysis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view HW 2: Syntax Analysis and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?