A few days ago, I asked the following question:
>Hello,
>
>We are have a problem with a yacc grammar file for the c language. the
>professor
>who gave this to me said the grammar has been around on the net for about ten
>years and has been used successfully.
>
>The problem is with action routines in the first position of the rule. (I'm
>not a yacc expert, this was how it was described to me.) The section we are
>having a
>problem with is below. (the complete grammar file is attached below my
>signature.)
>
>declarator2
> : identifier
> | '(' declarator ')'
> | declarator2 '[' ']'
> | declarator2 '[' constant_expr ']'
> | declarator2 /* {printf("*** action ***");} */ '(' ')'
> | declarator2 '(' parameter_type_list ')'
> | declarator2 '(' parameter_identifier_list ')'
> ;
>
>If the action routine is commented out, yacc runs correctly. If
>the action routine is uncommented, yacc fails with a rule not reduced error.
>
>declarator2
> : identifier
> | '(' declarator ')'
> | declarator2 '[' ']'
> | declarator2 '[' constant_expr ']'
> | declarator2 {printf("*** action ***");} '(' ')'
> | declarator2 '(' parameter_type_list ')'
> | declarator2 '(' parameter_identifier_list ')'
> ;
>ksh> yacc fail.yacc
>1 rules never reduced
>
>conflicts: 3 shift/reduce
>
[Complete description removed. Please see the archive for the whole grammar]
>The grammar shown in example 2 supposed worked under OSF/1 V1.3.
>
>Could any one shed any light on how and why the change happened? Is it a
>change in the spec for yacc, a POSIX requirement, or ????? Also any options on
>fixing the problem with re-writing the grammar file?
I received 1 reply, included below.
Thanks,
Dave Harrold
...............................................................................
David Harrold harrold_at_msoe.edu
Systems Manager
Milwaukee School Of Engineering Phone: 414-277-7286
Computer and Communication Services Department
1025 N. Broadway Street
Milwaukee, WI 53202-3109
...............................................................................
"I remember when mice were trapped, windows were washed and eunuchs guarded
the harem." -Unknown
+++++++++++++++++++++++++++ Begin Included Reply ++++++++++++++++++++++++++
From: MX%"kpe_at_ne.dk" 8-FEB-1995 04:03:50.75
To: MX%"harrold_at_barcly.acsd.msoe.edu"
CC: MX%"kpe_at_ne.dk"
Subj: Re: YACC problem with OSF/1 V2.1
Return-Path: <kpe_at_ne.dk>
Date: Wed, 8 Feb 95 10:49:58 +0100
From: Ketil Perstrup <kpe_at_ne.dk>
Message-ID: <9502080949.AA29767_at_facit.ne.dk>
To: harrold_at_barcly.acsd.msoe.edu
CC: kpe_at_ne.dk
In-Reply-To: <0098B934.8D91CBC0.5_at_barcly.acsd.msoe.edu> ("David Harrold,
Milwaukee School Of Engineering"_at_sws1.ctd.ornl.gov)
Subject: Re: YACC problem with OSF/1 V2.1
X-Charset: ASCII
X-Char-Esc: 29
Hello Harold
I assume that you have some knowledge of LALR(1)-grammers (otherwise
you shouldn't really try to write a parser for C as C is not exactly
the easiest thing to fit into a LALR(1)-grammar).
What happens when yacc reads the following tiny piece of your grammar:
declarator2
: declarator2 {printf("*** action ***");} '(' ')'
| declarator2 '(' parameter_type_list ')'
;
is that it is silently by yacc rewritten as
declarator2
: declarator2 M '(' ')'
| declarator2 '(' parameter_type_list ')'
;
M : {printf("*** action ***");}
where M is a marker nonterminal. I hope you can see the problem now:
When the parser reaches a state where its marker (*) is placed like
this:
declarator2
: declarator2 (*) M '(' ')'
| declarator2 (*) '(' parameter_type_list ')'
;
it _has_ to decide which of the two productions it should actually act
on: It should either reduce the marker nonterminal, M, as the first
production indicates, or shift the left parenthesis onto the stack as
the second production indicates.
Now A LALR(1) parser like yacc has a lookahead of 1, so the parser has
to decide which production to use by looking at the next token in the
input stream. Since the marker nonterminal is epsilon (empty), the
lookahead is '(' in both cases, and yacc can't decide which of the two
productions to use.
To me it seems that the immediate solution to your problem is to move
the action (and thereby the marker nonterminal) to the other side of
the '('. I can't see any reason why shouldn't be able to do this.
A word of comfort: You aren't the first one to be bitten by yacc's
userfriendlyness. The problem with yacc is that you don't have to do
much rewriting to insert actions in a LALR(1) grammar, but you still
get bitten, when an action introduces conflict, because yacc does the
rewriting _you_ would have done with a "purer" parsergenerator. So the
price for friendlyness is that it just stops being obvious where the
problems are when they arrive (Well, with a LALR(1) parser I should
probably not say obvious, but "obvious").
/Ketil
----------
Ketil Perstrup (kpe_at_ne.dk)
Me? I'm not told anything. I'm just the sysadm.
++++++++++++++++++++++++++++ End Included Reply +++++++++++++++++++++++++++
Received on Fri Feb 10 1995 - 12:57:12 NZDT