Re: Conflict resolution in EBNF

> The parser for the language works directly on ECFG, it doesn't
> transform ECFG into normal CFG.


What you mean by "parser works directly on ecfg" is somewhat vague
here. And I do hope that the *parser* doesn't actually *transform* an
ecfg into a cfg. After all, parsers are supposed to find derivation
structures of input sentences assuming a given grammar, not transform
grammars. The latter is (if at all) part of the job of a *parser
generator*.


You may judge my comment to be word splitting. But getting the
concepts right here is, I believe, absolutely important. In combining
the ideas of ecfg and LR parsing, many errors have been made for some
25 years and they continue to be made. The important point is that you
have to keep theory and implementation neatly separated. Implemention
should apply theory that has been understood before. Otherwise
implementors will quickly reach a point where they don't really know
any longer what they are doing. At least, this is *my* experience with
applied compiler construction, and especially with LR parsing. So be
sure that *you* have understood enough of the theory before
approaching implementation.


> Therefore two new kinds of Reduce/Reduce conflict may appear:


Here's where I advise you to be careful. What exactly do you mean by
"new kinds of Reduce/Reduce conflict"? Are you sure you know exactly
what you mean by "Reduce" at all? What is the "derives" relation that
you have in mind? Do you (merely) expect a parser (a) to pop a complex
handle matching a rhs's regular expression (RE) from the parse stack?
Or do you expect it to do more for you, notably (b) to have the
reduction also find out *how* the handle is inductively generated by
the rhs's RE by finding a "backward walk" through the RE? I believe
that (b) is what compiler constructors will usually need when using LR
parsers for ecfgs because the inductive structure of a handle is
essential for associating semantic code with the reductions. And it
seems to me that (b) is also what you, Anna, have in mind
yourself. However, view (b) of LR parsing with cfgs is poorly backed
by literature which attempts to solve only (a) (and runs into
problems).


(See the second part of my PhD thesis
http://edocs.tu-berlin.de/diss/2001/kannapinn_soenke.htm for a deep
analysis and constructive criticism of the literature; sorry, it's in
German, only the abstract is in English.)


My transformational approach to ELR parsing defines an ecfg to be an
"ELR(k) grammar" iff a reasonable transformation yields an LR(k) cfg.
It also explains in a "natural way" (i.e. based on pure cfgs) all the
different types of parser conflicts that you will encounter: In fact,
one should distinguish between 4 different types of parser conflicts
instead of the usual "shift"/"reduce" and "reduce"/"reduce"
conflicts. To see this, note that an ELR parser's reduction consists
of three steps: (1) start the reduction by "jumping to the tail of a
rhs RE", (2) make a "one-symbol backward step" in a rhs RE (popping
the parse stack), and (3) "step out" of a RE at its beginning (pushing
state information for the lhs). Describing these steps by relations
"red", "rb" (readback), and "uce", we can define the production
relation "reduce" to be the union of "red", "rb", and "uce". A
complete complex reduction is a production concatenation from "red rb*
uce". And possible conflict types are "shift"/"red", "red"/"red",
"rb"/"rb", and "rb"/"uce". The union of the latter three conflict
types yields the classical "reduce"/"reduce" conflicts.


Now, in order to apply the old YACCish concepts of precedence and
associativity to the new context of ecfgs, I suggest to study what
these concepts, when applied at the "transformed cfg" level, mean at
the ecfg level, i.e. before transformation.


> [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]


I hope you all agree that there should be nothing "tricky" on this once the
theory behind ELR parsing has really been understood.


All the best,
Soenke
--
Dr.-Ing. Sönke Kannapinn

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