LL(1) analysis and grammar transformations

Part A : Some exercises

(1) The following grammar has left recursion. Please, find an equivalent grammar without left recursion.

S --> SaA
S --> bB
A --> aB
A --> c
B --> Bb
B --> d

Note: S, A, et B are non-terminals. S is the starting symbol, the symbols a, b, c, and d are terminals.

(2) We consider the following grammar (a, b, and c are terminals). Use left factoring to find an equivalent LL(1) grammar.

S --> aA
S --> bB
A --> bA
A --> bB
B --> cB
B --> c

(3) We consider the following grammar:

bexpr --> bterm A’
A’ --> or bterm A’ | ε
bterm --> bfactor B’
B’ --> and bfactor B’ | ε
bfactor --> not bfactor | (bexpr) | true | false

• Determine the sets FIRST and FOLLOW for all non-terminals of the grammar.
• Construct a parsing table for this grammar.
• Is the grammar LL(1) ? - Explain !
  

Part B: Extending the Very-Simple-Programming-Language (VSPL)

VSPL is a very simple language (see description).

B-1: Find an equivalent grammar for VSPL that is LL(1).

1. Identify problems with the given grammar which make it non-LL(1).
2. Apply some transformations (equivalence changes) to make the grammar LL(1).
3. Calculate the sets First and Follow for your new grammar and check that the LL(1) conditions are met.

B-2: Extend the language

Please, extend the grammar of the "Very Simple Programming Language" in order to include arithmetic expressions with operators +, -, *, /, and ( ), taking into account the priority of operations.

1. Extend the grammar such as to support arithmetic expressions with operators +, -, *, /, and ( ), taking into account the priority of operations.
2. Check that your proposed grammar is LL(1). If it is not LL(1), apply some transformation rules in order to obtain an equivalent LL(1) grammar. Repeat until you get an LL(1) grammar.
3. A final validation: Does your grammar really accept the correct set of programs ? - Check with the stakeholder - perform some informal validation.