[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Please, detect ambiguous grammars

From: Askar Safin
Subject: Please, detect ambiguous grammars
Date: Sat, 08 Dec 2018 19:43:08 +0300

Hi. First of all, thanks a lot for fixing move semantics in C++ parsers. I 
waited for this feature for a long time.

I use Bison 3.2.2.

I want Bison to detect whether the grammar is ambiguous (this is mainly of 
interest in GLR mode). Of course, "grammar is ambiguous" is not the same thing 
as "there are s/r and r/r conflicts", for example, the manual gives example of 
grammar for subset of Pascal language, which is unambiguous, but have 
conflicts. I think that ambiguous grammar simply always need to be fixed, but 
grammar which has conflicts but is unambiguous, of course, need not to be fixed 
(as shown by Pascal example). Moreover, directive %expect-rr always seemed for 
me as something ugly. Instead there should be directive (probably for GLR mode 
only) with the following meaning: "expect unambiguous grammar, i. e. if grammar 
is unambiguous, then ignore any s/r and r/r conflicts, if grammar is ambiguous, 
then refuse to generate parser".

I don't know how hard it is to detect ambiguous grammar. I don't know whether 
this is undecidable problem at all (similar to well-known halting problem). But 
at least Bison should try to detect ambiguous grammar and should give a warning 
if it detected grammar as certainly ambiguous or if it was unable to decide. At 
least Bison should detect that well known "dangling else" grammar is certainly 
ambiguous, and that Pascal example is certainly not.

Askar Safin

reply via email to

[Prev in Thread] Current Thread [Next in Thread]