Re: Conflict resolution in EBNF
27 Oct 2001 18:39:44 -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 (Sönke Kannapinn) (2001-10-20)
Re: Conflict resolution in EBNF (2001-10-20)
Re: Conflict resolution in EBNF (2001-10-20)
Re: Conflict resolution in EBNF (Chris F Clark) (2001-10-20)
Re: Conflict resolution in EBNF (2001-10-20)
Re: Conflict resolution in EBNF (2001-10-27)
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 27 Oct 2001 18:39:44 -0400
Organization: Prodigy Internet
References: 01-10-077
Keywords: parse
Posted-Date: 27 Oct 2001 18:39:44 EDT

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 ( 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

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

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.

Post a followup to this message

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