Re: reduce/reduce conflict

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.


Bear

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