DOC PREVIEW
LSU CSC 4351 - Syntax Analysis

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

HW 2: Syntax AnalysisCSC 4351, Spring 2014Due: 26 February 20141. 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

LSU CSC 4351 - Syntax Analysis

Download Syntax Analysis
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 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 Syntax Analysis 2 2 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?