Problem $4$: SLR$(1)$ Parsing $($filename: slr$.$cc OR slr$.$rkt$)[2$ marks, $1$ release$+$secret$]$

In this problem, you will modify your solution to the previous problem so that it determines whether to shift or reduce using an SLR$(1)$ DFA.

The input to your program will consist of a CFG component, an INPUT component, a TRANSITIONS component, and a REDUCTIONS component, terminated by a $.$END line. The latter two components encode the transitions and reducible items of an SLR$(1)$ DFA.

The CFG and the input$-$to$-$be$-$parsed will be augmented.

This means:

$$ The first rule in the CFG component will have the form:

augmented$-$start$-$symbol BOF original$-$start$-$symbol EOF

The augmented$-$start$-$symbol and the original$-$start$-$symbol may differ between test grammars, but all test grammars will use the symbols BOF and EOF to mark the beginning and end of input.

$$ The augmented$-$start$-$symbol will never appear on the right hand side of a CFG rule.

$$ The input sequence will start with BOF and end with EOF.

Your program should work the same way as in the previous problem, except that it uses the SLR$(1)$ DFA to decide whether to shift or reduce at each parsing step. Your program should perform the "print" action once at the start $($before shifting or reducing$),$ and also after every shift or reduce. In other words, your output should be a full trace of the parse.

Additionally, in this problem, it is possible that the parse will be unsuccessful. This happens if there is no transition on the next symbol of input when the 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 terminal symbols that were successfully shifted prior to the error.

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.

Example

For the following input:

$.$CFG

S BOF expr EOF

expr expr $-$ term

expr term

term id

term $($ expr $)$

$.$INPUT

BOF id $-($ id $-$ id $)-$ id EOF

$.$TRANSITIONS

$0$ BOF $6$

$1$ id $2$

$1(3$

$1$ term $8$

$3$ id $2$

$3(3$

$3$ term $4$

$3$ expr $7$

$6$ id $2$

$6(3$

$6$ term $4$

$6$ expr $10$

$7-1$

$7)9$

$10-1$

$10$ EOF $5$

$.$REDUCTIONS

$23$

$23)$

$23$ EOF

$42$

$42)$

$42$ EOF

$50.$ACCEPT

$81$

$81)$

$81$ EOF

$94$

$94)$

$94$ EOF

$.$END

The output should be:

$.$ BOF id $-($ id $-$ id $)-$ id EOF

BOF $.$ id $-($ id $-$ id $)-$ id EOF

BOF id $.-($ id $-$ id $)-$ id EOF

BOF term $.-($ id $-$ id $)-$ id EOF

BOF expr $.-($ id $-$ id $)-$ id EOF

BOF expr $-.($ id $-$ id $)-$ id EOF

BOF expr $-(.$ id $-$ id $)-$ id EOF

BOF expr $-($ id $.-$ id $)-$ id EOF

BOF expr $-($ term $.-$ id $)-$ id EOF

BOF expr $-($ expr $.-$ id $)-$ id EOF

BOF expr $-($ expr $-.$ id $)-$ id EOF

BOF expr $-($ expr $-$ id $.)-$ id EOF

BOF expr $-($ expr $-$ term $.)-$ id EOF

BOF expr $-($ expr $.)-$ id EOF

BOF expr $-($ expr $).-$ id EOF

BOF expr $-$ term $.-$ id EOF

BOF expr $.-$ id EOF

BOF expr $-.$ id EOF

BOF expr $-$ id $.$ EOF

BOF expr $-$ term $.$ EOF

BOF expr $.$ EOF

BOF expr EOF

$.$ S $.$

If the INPUT component was replaced with the following:

$.$INPUT

BOF id $-($ id $-)-$ id EOF

Then your program should print ERROR at $7$ to standard error. This signifies that the error occurred after $6$ symbols were read successfully and therefore the $7$th symbol is the one that caused the error. It does not matter what is printed to standard output; for example, it is fine if you produce a partial trace of the parse before the error.