CS320 Assignment 5- Context Free Grammars Solution

⟨digit⟩ ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
⟨nat⟩ ::= ⟨digit⟩ | ⟨digit⟩⟨nat⟩
⟨int⟩ ::= ⟨nat⟩ | -⟨nat⟩
⟨expr⟩ ::= ⟨int⟩
| ( ⟨expr⟩ )
| ⟨expr⟩ + ⟨expr⟩
| ⟨expr⟩ * ⟨expr⟩
Derive the sentence using rightmost derivation.
12 + 2 * -07
1
2. Given the following grammar where ⟨stmt⟩ is the starting symbol.
⟨digit⟩ ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
⟨letter⟩ ::= a | b | c | ... | z
⟨nat⟩ ::= ⟨digit⟩ | ⟨digit⟩⟨nat⟩
⟨int⟩ ::= ⟨nat⟩ | -⟨nat⟩
⟨expr⟩ ::= ⟨int⟩
| ( ⟨expr⟩ )
| ⟨expr⟩ + ⟨expr⟩
| ⟨expr⟩ * ⟨expr⟩
⟨id⟩ ::= ⟨letter⟩ | ⟨letter⟩⟨id⟩
⟨stmt⟩ ::= ⟨id⟩ = ⟨expr⟩
| for ⟨id⟩ = ⟨expr⟩ to ⟨expr⟩ do ⟨stmt⟩
| { ⟨stmts⟩ }
| pass
⟨stmts⟩ ::= ⟨stmt⟩ | ⟨stmt⟩ ; ⟨stmts⟩
Derive the sentence using leftmost derivation.
for x = -12 to 10 do { y = 0; pass }
Page 2