##### Differences

This shows you the differences between two versions of the page.

 cs-236:homework-4 [2015/09/28 16:23]egm [Problems] cs-236:homework-4 [2015/09/30 10:49] (current)egm Both sides previous revision Previous revision 2015/09/30 10:49 egm 2015/09/30 10:49 egm 2015/09/28 16:23 egm [Problems] 2015/02/06 12:14 egm [Problems] 2015/02/02 15:25 egm [Problems] 2015/02/02 14:59 egm [Problems] 2015/02/02 12:25 egm [Problems] 2014/09/03 11:49 egm created Next revision Previous revision 2015/09/30 10:49 egm 2015/09/30 10:49 egm 2015/09/28 16:23 egm [Problems] 2015/02/06 12:14 egm [Problems] 2015/02/02 15:25 egm [Problems] 2015/02/02 14:59 egm [Problems] 2015/02/02 12:25 egm [Problems] 2014/09/03 11:49 egm created 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).\\ ::= - | \\ ::= ( ) | int | int / + # (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).\\ ::= - | \\ ::= ( ) | int | int / # (2 points) Compute the FIRST sets for the following. Compute FOLLOW sets as well for extra credit.\\ ::= <​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 - # (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 from 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 | lambda ## 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.\\ ::= (<​P>​)\\

::= <​Z><​P>​ | \\ ::= 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.\\ ::= (<​P>​)\\

::= <​Z><​P>​ | \\ ::= 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).