1. Context free grammars, LL and LR parsing Consider the following simple context free grammars: Grammar G1 G +AS A A+ Ab Grammar G2: GAS A + A Abb The start symbols are G, the nonterminals are G and A, and the terminal symbols are b and $ (end of file). Note that these grammars generate the same language: strings consisting of even numbers of b symbols (including zero of them). a. Attempt to show a shift-reduce parse of the input string bbbb for a parser for grammar G1. Show the contents of the stack, the input, and the actions in the style of Figure 3.18 on Page 58 but without the subscripts for the parse states). Indicate any conflicts and describe why they are conflicts. Is G LR(1)? Is it LR(0)? b. Attempt to show a shift-reduce parse of the input string bbbb for a parser for grammar G2. Show the contents of the stack, the input, and the actions in the style of Figure 3.18 on Page 58 but without the subscripts for the parse states). Indicate any conflicts and describe why they are conflicts. Is G2 LR(1)? Is it LR(O)? c. Indicate whether G and G2 are LL(1). You don't need to construct their LL(1) parse tables, you can argue from other properties. d. Of the language classes we have discussed in class, what is the smallest category into which L(G1) fits? Justify your answer. (Hint: This is a trick