Re: Conflict resolution in EBNF

Anna Nikitin wrote:
>
> 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}*
>


Sorry, but I am one of the few who does not see the advantage of using
EBNF in parser generators. The extra clarity of the longer BNF form
seems well worth the effort of writing a few more productions. This also
leaves more room for inserting semantic actions, without so much
overcrowding of the grammar. Separating things like {b}* into a null and
a non-null production allows a more natural specification of two
separate actions, rather than something like testing for the null case
in a single action. The EBNF operators can be a bit confusing if the
grammar also contains them. The new white-space delimited syntax used in
SLK eliminates the need for operators almost entirely. The colon
separator is the only operator, and it is not reserved because SLK can
detect what is meant by its position. For example, the following is a
legal, if somewhat odd production. Only the first colon is not a part of
the production's right hand side.


A : : ::opt ::: {} : b & ** c : : -> ::= --> d e no-terminator_needed_*


SLK (http://pages.prodigy.net/dr_feriozi) handles grammar (1) by
automatically using the first specified production, similar to the
dangling-else resolution. This avoids the need for a directive in the
grammar.


The different behavior encountered in grammar (2) is caused by right
recursion. Again, this would be more easily noticed in a BNF grammar
like


A : a B
    | a b B
B : b B
    |


Sadly, this causes my algorithm to report that the grammar is not LL(k),
instead of detecting the ambiguity. However, the grammar trace makes the
problem obvious. The solution is to use the :! separator rather than the
: separator. This instructs SLK to ignore the conflict and just use the
first specified production.

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