Reference no: EM134458

The executable should be testParser .Please include makefile. Please add as many comments as you can.

Verify the below Grammar is LL(1) or rewrite as needed in an equivalent form

Implement the parser in a separate file (parser.h and parser.c). Implement the main parser function in a separate file main.c: the main function should check for command line arguments, and then call the parser function to build the tree, and then implement recursive traversal to print the tree. Make sure it will check for the EOF token.  The display is just for testing.

Implement the parser in two iterations:

1. Parser1.c : Starting without the parse tree. Have your parses generate error (print the line number and the nature of the problem such as token received and token expected) on the first error and exit, or print OK message upon successful parse.

2. For each non-terminal, use a void function named after the non-terminal. Decide how to pass the token. Be systematic: suppose each function starts with unconsumed token (not matched yet) and returns unconsumed token. The non-LL(1) non-terminals with all-common prefix - implement the shortcut to mate them LL(1) rather than explicitly performing left-factorization

3. Parser2.c : Only after testing and completing the above to satisfaction, modify each parse function to build a subtree, and return its root node. Suppose each function builds just the root and connects its subtrees. Modify the main function to receive the tree built in the parser, and then display it (for testing) using a preorder display. Add declaration file node.h

o do left to right traversal, for each new level use 2 space indentation

o when visiting a node print what the node is and what tokens it has if any, then print its children left to right the same way

o for every token, print token type, instance and line number

 Some hints for tree:

• every node should have a label consistent with the name of the function creating it
• every function creates exactly one tree node (or possibly none)
• the number of children seems as 3 max but it is your decision
• all syntactic tokens such as () can be thrown away, all other tokens need to be stored in the tree
• when storing a token, you may need to make a copy depending on your interface

Grammar

<program> ->  Start <vars> <funs> <block> Stop
<block>   ->  { <vars> <stats> }
<vars>    ->  empty | Var ID <mvars> .
<mvars>   ->  empty | : ID <mvars>
<fun>     ->  Void() <block> Return(ID);
<funs>    ->  empty | <fun> <funs>
<expr>    ->  <T> + <expr> | <T> - <expr> | <T>
<T>       ->  <F> * <T> | <F>
<F>       ->  <G> / <F> | <G>
<G>       ->  - <G> | <R>
<R>       ->  (<expr>) | ID | NUMBER 
<stats>   ->  <stat>  <mStat>
<mStat>   ->  empty | <stat>  <mStat>
<stat>    ->  <in> | <out> | <block> | <if> | <loop> | <assign>
<in>      ->  Read (ID) ;
<out>     ->  Write (<expr>) ;
<if>      ->  Iff ( <expr> <RO> <expr> )  <block>             
<loop>    ->  While ( <expr> <RO> <expr> ) <block>
<assign>  ->  ID == <expr> ;
<RO>      ->  =< | => | = |  > | <  |  !

Example programs (assuming some standard semanticcs)

&short program prints 0
Start {
  Write (0);
} Stop
 
&program echoes input*2
Start
  Var x.
  { Read (x);
     Write (2*x);
  }
Stop
    
&print absolute value
Start {
  Var x: y;
  Read (x);
  Iff (x<0) {
    y == -x;
  }
  Write (y);
} Stop