search
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
cs-236:homework-4 [2015/02/02 15:25] egm [Problems] |
cs-236:homework-4 [2015/09/30 10:49] (current) egm |
||
|---|---|---|---|
| Line 12: | Line 12: | ||
| ==Problems== | ==Problems== | ||
| - | # (4 points) Show the top-down recursive parse with no look-ahead for the input ''int / int''. When choosing which rule to expand, go in order of the rules. The ''int'' terminal is an integer literal).\\ <E> ::= <T> - <E> | <T>\\ <T> ::= ( <E> ) | int | int / <T> | + | # (4 points) Do a brute force search to find a parse tree for the input ''int / int''. Use a top-down approach meaning you begin with the start rule (i.e., the first rule), and find a left-derivation. When choosing which rule to use in an expansion, go in order of the rules. The ''int'' terminal is an integer literal).\\ <E> ::= <T> - <E> | <T>\\ <T> ::= ( <E> ) | int | int / <T> |
| # (2 points) Compute the FIRST sets for the following. Compute FOLLOW sets as well for extra credit.\\ <A> ::= <A><A>'+' | <A><A>'*' | a | # (2 points) Compute the FIRST sets for the following. Compute FOLLOW sets as well for extra credit.\\ <A> ::= <A><A>'+' | <A><A>'*' | a | ||
| - | # (6 points) For each of the following grammars, devise predictive parsers and show the parsing tables. You may left-factor and/or eliminate left-recursion form your grammars first if needed: | + | # (6 points) For each of the following grammars, build an LL(1) parse table. You may left-factor and/or eliminate left-recursion from your grammars first if needed: |
| - | #* S --> 0 S 1 | 0 1 | + | ## S --> 0 S 1 | 0 1 |
| - | #* S --> + S S | * S S | a | + | ## S --> + S S | * S S | a |
| - | #* S --> S ( S ) S | epsilon | + | ## S --> S ( S ) S | lambda |
| # (8 points) Build the LL(1) parse table for the following grammar with start symbol X. You may left-factor or remove left-recursion if needed.\\ <X> ::= (<P>)\\ <P> ::= <Z><P> | <Z>\\ <Z> ::= 0 | 1 | # (8 points) Build the LL(1) parse table for the following grammar with start symbol X. You may left-factor or remove left-recursion if needed.\\ <X> ::= (<P>)\\ <P> ::= <Z><P> | <Z>\\ <Z> ::= 0 | 1 | ||
| - | # (4 points) The following is a grammar for regular expressions over symbols ''a'' and ''b'' only, using + in place of | for union, to avoid conflict with the use of vertical bar as a meta-symbol in grammars:\\ <rexpr> ::= <rexpr> '+' <rterm> | <rterm>\\ <rterm> ::= <rterm> <rfactor> | <rfactor>\\ <rfactor> ::= <rfactor> '*' | <rprimary>\\ <rprimary> ::= 'a' | 'b' | + | # (4 points) The following is a grammar describes a language for regular expressions over symbols ''a'' and ''b''; the language uses +-sign in place of a |-sign for union. As such the use of the |-sign is part of the BNF syntax while the +-sign is part of the language being defined by the grammar:\\ <rexpr> ::= <rexpr> '+' <rterm> | <rterm>\\ <rterm> ::= <rterm> <rfactor> | <rfactor>\\ <rfactor> ::= <rfactor> '*' | <rprimary>\\ <rprimary> ::= 'a' | 'b' |
| - | #* Is the grammar ready for LL(1) parsing? If yes, then justify your answer. If no, then modify the grammar so it is LL(1). | + | #* Is the grammar ready for LL(1) parsing (i.e., are you able to create a parse table with no non-determinism)? If yes, then justify your answer. If no, then modify the grammar so it is LL(1). |
