Re: Conflict resolution in EBNF

Anna Nikitin <csanna@cs.Technion.AC.IL>
16 Oct 2001 00:09:04 -0400

          From comp.compilers

Related articles
Re: Conflict resolution in EBNF csanna@cs.Technion.AC.IL (Anna Nikitin) (2001-10-16)
Re: Conflict resolution in EBNF Soenke.Kannapinn@wincor-nixdorf.com (Sönke Kannapinn) (2001-10-20)
Re: Conflict resolution in EBNF alexc@world.std.com (2001-10-20)
Re: Conflict resolution in EBNF knyblad@baan.com (2001-10-20)
Re: Conflict resolution in EBNF cfc@world.std.com (Chris F Clark) (2001-10-20)
Re: Conflict resolution in EBNF friwi@prosun.first.gmd.de (2001-10-20)
Re: Conflict resolution in EBNF dr_feriozi@prodigy.net (2001-10-27)
| List of all articles for this month |

From: Anna Nikitin <csanna@cs.Technion.AC.IL>
Newsgroups: comp.compilers
Date: 16 Oct 2001 00:09:04 -0400
Organization: Compilers Central
References: <Pine.WNT.4.33.0110141148380.-834121@milton.iecc.com>
Keywords: parse, question
Posted-Date: 16 Oct 2001 00:09:04 EDT

I'm working on a new compiler-compiler language which allows using
regular expressions. In other words, it's possible to describe
Extended Context Free Grammars (ECFG) using it. The parser for the
language works directly on ECFG, it doesn't transform ECFG into normal
CFG. Therefore two new kinds of Reduce/Reduce conflict may appear:


        1. Parser doesn't know which alternative to choose (when popping the
symbols from the stack). The conflict appears in the following grammar:
        A -> {a | aa}B
        B -> {ab | b}
        2. Parser doesn't know whether to stop or to continue popping symbols from
the stack. The conflict appears in the following grammar:
        A -> {a | ab}{b}*


In the first case we can use precedence rules (as in Yacc), i.e. give
priorities to the alternatives. If the conflict occurs we simply
choose the alternative with the highest priority. But in the second
case it's not so clear what to do. I don't think that I can use
precedence here but I suppose some other techniques may help. Does
somebody know such techniques? I'll appreciate any help in solving
this problem.


Thank you in advance,
                Anna.
[She knows the grammar is ambuguous, the question is whether there's some
reasonable trick like yacc's %left and %right to tell the parser generator
how to deal with it. -John]



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.