Re: Conflict resolution in EBNF

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]

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