Consider the following grammar G. In the grammar, T and F are nonterminal, # and a are

Fantastic news! We've Found the answer you've been seeking!

Question:

Consider the following grammar G. In the grammar, T and F are nonterminal, # and a are terminals, and T is the start symbol.

T → F T

T → F

F → # F

F → a

a. Determine the First- and Follow-sets for T and F. Use $, as usual, to represent the “end-of-file”.

b. Formulate in your own words which sequences of terminal symbols are generated starting from S.

c. Is it possible to represent the language of G (consisting of # and a symbols) by a regular expression? Explain, if the answer is “no”, resp. gives a corresponding regular expression if the answer is “yes”.

d. Introduce a new start symbol S ′ with a production S ′ → S. Give the LR (0)-DFA for G right for that grammar. Give numbers to the states of the DFA.

e. Give a short argument determining which of the following 5 groups the grammar belongs to; more than one answer is possible: (Marks 3)

LR (1)
LALR (1)
SLR (1)
LR (0)
none of the above Hint: determine possible conflicts in the constructed DFA and/or if the grammar is unambiguous.

f. Give the parsing table for G, fitting the grammar type.

g. Show how the sentence “a #a” is being parsed. Do that, as done in the class, by writing the stack-contents and input for each shift- or reduce-operation executed during the parsing. Indicate also the numbers of the states on the stack.