Re: Conflict resolution in EBNF

Anna Nikitin <csanna@cs.Technion.AC.IL> wrote in message news:01-10-077...
> 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.


Hi,


The first example rarely occurs in practical examples. I am writing a
parser generator for EBNF myself. I intend to support many different
sorts of rules for conflict resolution, but I intend to simply forbid
cases like the first example.


On the second example. The normal way of implementing a parser
generator for EBNF is to generate a DFA per production. Each of these
DFAs recognizes the regular expression of the production from which it
is generated. Then you generate an LR(0) like automaton from these
DFAs, where you use the DFA states as items. Doing that the second
example is not ambiguous.


I wonder if you know these old articles:
    http://compilers.iecc.com/comparch/article/91-05-069
    http://compilers.iecc.com/comparch/article/91-05-076
    http://compilers.iecc.com/comparch/article/92-06-111
    http://compilers.iecc.com/comparch/article/93-02-125
You should read the articles refered in the postings.


Regards, Karsten Nyblad

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