Problem $5$: WLP$4$ Parser $($filename: wlp$4$parse.cc OR wlp$4$parse.rkt$)[3$ marks, $1$ release$+$secret, $1$ secret$]$

In this problem, you will modify your solution to the previous problem to parse WLP$4$ programs, and to produce a representation of a parse tree as output.

The input no longer contains a CFG or parsing DFA, and is no longer formatted into components. Instead, the input format is simply the output format of the WLP$4$ scanner.

The output format of the parser is also different. You should construct a parse tree for the program, in which the value stored at each node in the tree is either the production rule used to expand the nonterminal at the node $($if it is an internal node$),$ or the token kind and lexeme $($if it is a leaf node$).$ If the parse is successful, the print the node values, one per line, using a left$-$to$-$right preorder traversal of the tree:

$1.$ Print the value at the root of the tree $($that is$,$ print the production rule or the token kind and lexeme, depending on which kind of node$).$

$2.$ Visit the children in order from left to right. For each child subtree, recursively print the values in the subtree using a left$-$to$-$right preorder traversal.

The result of this preorder traversal is a $.$wlp$4$i $($WLP$4$ Intermediate$)$ file.

In this problem, it is possible that the parse will be unsuccessful. This happens if there is no transition on the kind of the next token when the parsing DFA tells you to shift. If this occurs, output a single line consisting of the string ERROR at k $($terminated with a line feed$)$ to standard error, where k is one greater than the number of WLP$4$ tokens that were successfully read from the input prior to the error.

Note that BOF and EOF are not part of the input, so they do not contribute to the value of k in this problem. Note also that "one token" means a kind and lexeme pair; so each line of the input contains one token.

Unlike in some earlier assignments, where your error message simply had to contain "ERROR", in this problem your error message must exactly match the required message. Extraneous output $($such as debugging output$)$ on standard error will cause you to fail some Marmoset tests.

WLP$4$ Grammar and Parsing Data

You may find the following files useful:

wlp$4$data.h is a C$++$ header file that provides four string constants:

WLP$4\_$CFG is a CFG component for the augmented WLP$4$ grammar.

WLP$4\_$TRANSITIONS is a TRANSITIONS component for the WLP$4$ SLR$(1)$ DFA.

WLP$4\_$REDUCTIONS is a REDUCTIONS component for the WLP$4$ SLR$(1)$ DFA.

WLP$4\_$COMBINED is a single string containing the above three strings followed by a $.$END line.

wlp$4$data.rkt is a Racket module that provides four string constants:

wlp$4-$cfg is a CFG component for the augmented WLP$4$ grammar.

wlp$4-$transitions is a TRANSITIONS component for the WLP$4$ SLR$(1)$ DFA.

wlp$4-$reductions is a REDUCTIONS component for the WLP$4$ SLR$(1)$ DFA.

wlp$4-$combined is a single string containing the above three strings followed by a $.$END line.

Example

For the following input:

INT int

WAIN wain

LPAREN $($

INT int

ID a

COMMA $,$

INT int

ID b RPAREN $)$

LBRACE $\{$

RETURN return

NUM $42$

SEMI ;

RBRACE $\}$

The output should be:

start BOF procedures EOF

BOF BOF

procedures main

main INT WAIN LPAREN dcl COMMA dcl RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE

INT int

WAIN wain

LPAREN $($

dcl type ID

type INT

INT int

ID a COMMA $,$

dcl type ID

type INT

INT int

ID b

RPAREN $)$

LBRACE $\{$ dcls $.$EMPTY

statements $.$EMPTY

RETURN return

expr term

term factor

factor NUM

NUM $42$

SEMI ;

RBRACE $\}$

EOF EOF

Testing

You can compare your output with the course tool wlp$4$parse to see if it is correct.