Assignment

Part 1:

A logical grammar defines logical expressions. You are given the following CGF for Boolean Logic. The terminal symbols are ∑ = { (, ),¬, ∧, ∨, 0, 1}

A→ A ∨ A                        (1)
A→ A ∧ A                        (2)
A→ ¬A                            (3)
A→ (A)                            (4)
A→ 0|1                            (5)

a) Generate by hand the parse tree for the follovving expressions

1 ∨ 1 ¬ 1
(1 ∧ ¬ 0) ∨ ¬ 0
((¬1 ∨ 0) ∧ 0) ∨(0 ∧ (¬1))

b) Show that the grammar is ambiguous by building two parse trees for the same string.

c) Create a new grammar for the same language so that it is unambiguous. The operators are listed in ascending order of precedence in the above rules. The binary operators should be left-associative

Part 2: Building a parser for Boolean Logic Expressions:

a. Your unambiguous grammar is probably left recursive and cannot be implemented using recursive descent parsing. Rewrite the grammar so that it is not left recursive and can be used directly for top-down parsing with Al) terminal look-ahead

b. Implement your unambiguous, non-left recursive gramrnar using either the recursive descent or the table-driven method.