Transform the following grammar to Chomsky Normal Form:

S → (S)|A
A → SS|““

Please give the detailed steps of the algorithm.

Consider the following grammar:

E ::= E+E
E ::= E*E
E ::= E=E
E ::= Num | true | false

Where Num represents integers.

Run Earley's parsing algorithm on the following input: 1=2*3=true

How many parse trees do you obtain?

Write down those parse trees that are correct according to the following types:

+ : Int x Int→Int

* : Int x Int→Int

= : Bool x Bool → Bool

= : Int x Int → Bool

Solution