Re: reduce/reduce conflict

Ray Dillinger <>
4 Feb 2004 21:27:27 -0500

          From comp.compilers

Related articles
reduce/reduce conflict (TJB) (2004-02-01)
Re: reduce/reduce conflict (Ray Dillinger) (2004-02-04)
Re: reduce/reduce conflict (Chris Dodd) (2004-02-08)
| List of all articles for this month |

From: Ray Dillinger <>
Newsgroups: comp.compilers
Date: 4 Feb 2004 21:27:27 -0500
Organization: Compilers Central
References: 04-02-027
Keywords: parse
Posted-Date: 04 Feb 2004 21:27:27 EST

TJB wrote:
> Hi,
> I'm currently writing a grammar for a C/Pascal-like language using
> btyacc (bactracking yacc). The grammar is free from conflicts except
> for 1 shift/reduce conflict. When I tried using inherited attributes I
> got 1 reduce/reduce conflict. Is there any way I can get rid of it
> without having to rewrite the grammar ?
> [No. -John]

As the moderator mentioned, you *will* have to rewrite the specific
grammar you're using to parse the language. But that doesn't mean you
will have to change the structure or specification of the language
accepted. You just have to find a better grammar for parsing it.

LL(1) languages are those capable of being parsed by some LL(1)
grammar; But you can also write grammars for the same languages that
aren't LL(1).

F'r example consider the classic instance in pascal where most
beginners think they need 2 tokens of lookahead to choose between a
procedure call and an assignment statement:

stmt --> ... assignment_stmt | proc_call_stmt | forloop_stmt
                          | whileloop_stmt ....
proc_call_stmt --> <identifier> "(" callparams ")"
assignment_stmt --> <identifier> ":=" expression

Now, if this is your grammar, you get to the point where you have a
stmt, and the next token is an <identifier>, you don't know whether to
reduce by calling it an assignment statement or a function call: You
have a reduce/reduce conflict that you'd need a second token of
lookahead to resolve.

But consider the following grammar:

stmt --> ident_stmt | forloop_stmt | whileloop_stmt ....
ident_stmt --> <identifier> (assignment_cont | proc_call_cont)
proc_call_cont --> "(" call_params ")"
assignment_cont --> ":=" expression

With this grammar, when you have a stmt and the next token is an
identifier, it's clear what transformation to use; you transform it
into an ident_stmt. The reduce/reduce conflict is eliminated. When
you have an ident_stmt and the next token is an identifier, you also
know what to do; you shift. If the next token is "(" then clearly you
reduce to proc_call_cont, whereas if the next token is ":=" then
clearly you reduce to assignment_cont.

The second grammar here accepts the same language as the first, and it
is an LL(1) grammar. The first grammar, which is the one most folks
write first, is an LL(2) grammar and will give you a conflict when
used with LL(1)-dependent tools.


Post a followup to this message

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