Überprüfung, ob zwei yacc-Grammatiken äquivalent sind

Sie haben eine yacc-Grammatik (oder eine andere LALR-Grammatik in dem Tool Ihrer Wahl) geschrieben, und Sie haben entschieden, dass Sie einige Produktionen für Effizienz, Klarheit, was auch immer umgestalten wollen. Zum Beispiel hatten Sie:

Sie möchten es deutlicher machen, dass es mehrere Semikola geben kann, also schreiben Sie es wie folgt um:

OK, sieht also plausibel aus ... aber habe ich eigentlich das Refactoring richtig gemacht? Es wäre großartig, wenn ich diese Deklarationen an ein Werkzeug weitergeben könnte, das mir sagen würde, ob die Grammatiken gleichwertig sind oder nicht. (Betrachten wir zunächst nur die Frage, ob wir die gleichen Sprachen erkennen oder nicht.)

Eine reflexartige Reaktion ist es, zu zitieren, dass kontextfreie Grammatik-Äquivalenz unentscheidbar ist. In der Tat ist selbst das Problem der Feststellung unentscheidbar, ob eine CFG regelmäßig ist . Aber yacc erkennt CFGs nicht: es erkennt deterministische kontextfreie Grammatiken, und für diese ist bekannt, dass Äquivalenz ist entscheidbar . Aber hat jemand irgendwelche dieser Entscheidungsprozeduren implementiert?