[Haskell-cafe] I announce my library for checking context-free grammar for ambiguity (was: How to do reversible parsing?)

Askar Safin safinaskar at mail.ru
Mon May 24 02:01:50 UTC 2021

> Very cool! How’s your checking alg work?
I generate all strings of symbols, which can be reached from start symbol by replacing nonterminals with their productions no more than "count" times. If I get duplicate, then the grammar is ambiguous. This strings are strings of any symbols, not necessary terminals. And "count" means count of replacements, i. e. count of productions applications.

This is simple brute force algorithm. It does not really checks grammar for ambiguity (this is impossible on Turing machine).

I can give more details.

Also you can read my January letter: https://mail.haskell.org/pipermail/haskell-cafe/2021-January/133275.html . In it I gave links to some checking algorithms, which actually work, but for particular sets of grammars (i. e. not for all of grammars)

Askar Safin

More information about the Haskell-Cafe mailing list