search

mdaines / grammophone

A tool for analyzing and transforming context-free grammars.
https://mdaines.github.io/grammophone
MIT License
200 stars 23 forks source link

Left recursion elimination hangs #14

Closed deliciouslytyped closed 2 years ago

deliciouslytyped commented 2 years ago

When I try to do left recursion elimination on this grammar firefox tells me the tab is slowing down my browser, and the app seems to hang:

S -> S + S | S * S | ( S ) | Int.
Int -> 0 | 1.
mdaines commented 2 years ago

It looks like applying this transformation is producing the following grammar. Trying to analyze it causes a hang for me as well.

S -> ( S ) S' .
S -> Int S' .
S' -> + S S' .
S' -> * S S' .
S' -> .
Int -> 0 .
Int -> 1 .

I think the hang may be due to the example sentences calculation not terminating. I'll verify that and will try applying a fix I made on the development branch.

deliciouslytyped commented 2 years ago

That sounds consistent with what would happen when I told firefox to stop the tab. It would display a resulting grammar and the example area would not be rendered.

mdaines commented 2 years ago

I just published this fix: https://github.com/mdaines/grammophone/commit/6bcc898ae97fab876973b9bc554de72d8efada70

The grammar resulting from applying that transformation no longer causes a hang for me. Does it work now for you?

deliciouslytyped commented 2 years ago

Works for me! Thanks! :D