The Following Context Free Grammar Generates Boolean Expressions

The following Context-free grammar generates Boolean expressions.

                                                      E -> E or T

                                                         -> E nor T

                                                         -> E xor T

                                                         -> T

                                                      T -> F and T

                                                         -> F nand T

                                                         -> F

                                                      F -> not F

                                                         -> P

                                                      P -> ( E )

                                                         -> i

                                                         -> true

                                                         -> false

Determine whether this grammar is LL(1) or not.  Justify your answer.If the grammar is not LL(1), transform it into  an equivalent grammar that is LL(1).Build a parse table from your resulting grammar  in Part 2.Using your parse table from Part 3, show how the following input string is parsed:

true nand (false xor i) or not i and not false nor i

Using the table lookups from Part 4, build the  derivation tree (top-down, left-most derivation) for the string parsed in Part 4.Write (pseudo) code for a Recursive Descent  parser for the grammar you obtained in part 2. Include “Write()” statements to  build the Derivation Tree in bottom-up fashion.Show the sequence of productions produced by  your recursive descent parser, for the following input string:Modify the code for the Recursive Descent parser  for the grammar in part 6, so that it generates the derivation tree for the  original grammar.  Show the sequence of  productions produced by this new recursive descent parser, for the same input  string as in part 7.  Show the  corresponding derivation tree.Modify the code in part 8 so it will generate  the Abstract Syntax Tree.  The  String-to-Tree Transduction grammar is as follows:

         E -> E or T                => ‘or’

                                                         -> E nor T             => ‘nor’

                                                         -> E xor T              => ‘xor’

                                                         -> T

                                                      T -> F and T            => ‘and’

                                                         -> F nand T          => ‘nand’

                                                         -> F

                                                      F -> not F                => ‘not’

                                                         -> P      

                                                      P -> ( E )

                                                         -> i                           => ‘i’

                                                         -> true => ‘true’

                                                         -> false                  => ‘false’

Show the sequence of calls to Build_tree() that are carried out by your new recursive descent parser, for the same input string as in Part 8.  Show the corresponding Abstract Syntax Tree.

Prof. Angela


Calculate Price

Price (USD)