Question on %nonassoc-directive in LALR(1) parser generators

Hello,


I have a question about the %nonassoc-directive in LALR(1) parser
generators like yacc, to influence the associativity and precedence of
terminals. Yacc defines terminals attributed with %nonassoc as
not-associative, so a grammar like:


%nonassoc '=';


test: expr 'n'
|
;


expr: expr '=' expr
| 'x'
;


results in a parser that correctly accepts "x=x" but not
"x=x=x". Running yacc (bison) in verbose mode also gives me the
message that the state


expr -> expr .'=' expr
expr -> expr '=' expr .


runs into an error because '=' is not associative.


Now, if I refer to the book [Holub] "Compiler Design in C", Holub
shows a table on how shift-reduce conflicts are handled when the
precedence of the production to be reduced and the symbol to be
shifted are equal (which is the case in above yacc grammar). This
table is


Associativity of conflict symbol | Perform
---------------------------------|--------
Left-associative | reduce
Right-associative | shift
Non-associative | reduce


Even his own parser generator occs (implemented in this book) and the
parser generator Anagram (http://www.parsifalsoft.com/) use this
(faulty?) approach: They always accept inputs like "x=x=x" when '=' is
declared non-associative, and I'm not sure now if this is a mistake in
Holubs book or a misunderstanding by me. The way yacc implements this
table is, in my opinion


Associativity of conflict symbol | Perform
---------------------------------|--------
Left-associative | reduce
Right-associative | shift
Non-associative | [remove shift from action table]


Am I right now or who made the mistake here?


Thank you & Best regards


Jan
[Holub's book had a stupendous number of mistakes. Have you looked at
the 50 page errata sheet? Google for "holub compiler design", click the
documentation link for a PDF that is mostly errata. -John]

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