patrickhuber / Pliant

MIT License
26 stars 4 forks source link

Ambiguous grammars with right recursions do not reuse existing parse nodes. #54

Closed patrickhuber closed 8 years ago

patrickhuber commented 8 years ago

The Elizabeth Scott paper on parse forest creation reuses parse forest nodes if they already exist. Because the Leo completion function utilizes transition items and virtual parse forest nodes, the parse forest creation is deferred and must be recreated lazily during parse forest traversal.

Currently the Leo completion algorithm doesn't reuse the existing parse forest nodes and causes duplicate trees.

Example:

Input: "01"

S = A | B
A = '0' C
B = '0' C
C = '1'