This exercise is unassessed. It helps you to see whether you understand how the translation of grammars to parsing methods from the lectures works, and where its limitations lie.
Parsing question 1
For each of the following situations that may arise in grammars, explain whether or not they cause problems for the predictive parsing technique covered in the lectures. (The letters "c", "d" and "e" are terminal symbols, as usual.) There could be other rules in the grammars apart from the ones given. You can convert the grammar rules to parsing methods as explained in the lectures, and see whether the resulting code makes sense.
(a) The same symbols occur on the right-hand side of two rules for the same non-terminal symbol, as in:
B → d c
B → c d
(b) The same symbol occurs as the first symbol on the right-hand side of two rules for the same non-terminal symbol, as in:
B → c d
B → c e
(c) A non-terminal symbol occurs on the right-hand side of one of its rules, as in:
B → c B
(d) A non-terminal symbol occurs multiple times on the right-hand side of one of its rules, as in:
B → c B c B
(e) The same symbol occurs on the right-hand side of two rules, as in
B → c d
A → c e
(f) There are no symbols on the right-hand side of some rules, as in
B → c B
B →
A → B d
(g) A non-terminal symbol occurs as the first symbol on the right-hand side of one of its rules, as in
B → B c A
(h) A non-terminal symbol A occurs as the first symbol of a rule for a non-terminal B, such that B occurs as the first symbol of a rule for A.
B → A c B
A → B c A
Parsing question 2
Consider the following grammar:
S → a B B c
B → d B
B → e
The letters "a", "c", "d", and "e" are terminal symbols, as usual. S is the start symbol. Translate the grammar rules into parsing methods using the technique from the lectures. You do not need to build the parse tree, so the methods can have return type void.
Solutions
After (yes, after) solving the questions, you can check the model solutions.