Part 1: A logical grammar defines logical expressions. You are given the followi

ID: 3759923 • Letter: P

Question

Part 1:

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

A--> A V A (1)

A--> A A (2)

A--> A ¬ A (3)

A--> (A) (4)

A--> 0|1 (5)

Generate by hand the parse tree for the following expressions

0 V 1 ¬1

(1 0) V ¬0

((1 0) 0) V (1 (¬0))

I. Building a parser for Boolean Logic Expressions:

Your unambiguous grammar is probably left recursive and cannot be implemented using recursive descent parsing.

1. Rewrite the grammar so that it is not left recursive and can be used directly for top-down parsing with one terminal look-ahead.

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