Consider the following grammars and the corresponding random strings they generate:

$1.$ S $->+$ S S $|*$ S S $|+$ S$|$ a $+$a$+*++$a$*$aa$+$a$*$aa

$2.$ S $->$ S $($ S S $)|$ a $|$ e $($a$($a$(($aa$)$a$)($a$)))$

$3.$ S $->$ S $+$ S $*$ S $|$ S $*$ S $+$ S $|($ S $)|$ a $($a$+$a$*$a$)*$a$*$a$+$a$+($a$)$

A$.$ For each grammar fully construct the parser states LR$(0),$ SLR$(1),$ LR$(1)$

and LALR$(1),$ and examine whether it belongs to one or more of the four classes of LR$-$type parser. Identify any conflicts that may occur in the states without building any parser tables.

B$.$ For those grammars that are not LR$(1)$ explain whether they can be LR$($k$)$ for any

k$>1$ or not and why.

C$.$ Depending on your answer to question A$,$ construct the simplest deterministic LR$-$type parser matrix you can for each of the three grammars.

D$.$ For non$-$LR$(1)$ grammars, construct the LR$(1)$ parser table with multiple moves at the positions where there is a conflict, and then see if preselecting one move per case can resolve the conflict, if deleting the rest of the moves results in a deterministic matrix of syntactic analyzer which can

recognize the same language as the language of the original grammar.

Q$.$ Based on the tables you constructed in the previous questions, describe

the steps to identify the matching strings. In particular, if an array is non$-$deterministic, use backtracking where necessary so that by trying multiple options you can reach identification.