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

mailings@jmksf.com writes:


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


The intent of non-assoc is to make "x=x=x" an error and the way to
implement that is to put an error action in the SR-table at the
location you are indicating. So, I believe you are correct here.
Putting a reduce there makes the grammar left associative. (If I can
keep my associativities straight.) Putting a shift there makes the
grammar right associative.


In some cases, (not this instance but other SR-coflicts) doing both,
shifting and reducing to create two paths in the parse forest, makes
the grammar GLR. Also, you can use additional lookahead in the GLR
instances to sometimes resolve the conflict, which can make the tables
LR(k).


As a rhetorical question, I'll ask why you can't use lookahead in the
cse you describe to use the conflict?


The answer being, that because the instance you describe is a
recursive application of a binary operator. In recursive applications
of binary operatos the lookahead doesn't provide additional
information. You can reduce the same sentences picking either left or
right. You simply build different trees for them.


In this case, associativity operators give approximately the right
level of control, although you might want to apply them more locally
than globally. In other cases, it is better to use lookahead (or GLR)
to guide the choice because the lookahead can tell you which strings
you are not allowing as sentences. In many of those case, selecting
shift allows the larger set of strings as belonging to the grammar.
However, if I recall correctly, it is possible to construct cases,
where the reduce option actually selects that grammar that has more
strings in it.


One of the subtly(*) good features of Yacc++ is how it handles these
conflicts. (Subtly meaning here, a good feature that goes (and should
go) essentially unnoticed because it simply does the right thing
without drawing attention to itself.) We actually spent a fair amount
of time looking at different types of conflicts and determining what
the parser generator should do with them. ELR has more kinds of
conflicts than LR does, especially if one is doing LR(k) parsing.


As to the Holub book, despite its errors, I think it is a good book.
To me the errors are simply a reflection of how difficult it is to do
parsing right. It is a much more subtle problem than most people
realize.


Hope this helps,
-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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