[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
http://vk.com/safinaskar
- Please, detect ambiguous grammars,
Askar Safin <=