[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Conflicts in large grammar
From: |
Hans Aberg |
Subject: |
Re: Conflicts in large grammar |
Date: |
Sat, 4 Aug 2007 12:11:20 +0200 |
On 3 Aug 2007, at 16:49, Laurence Finston wrote:
I've run into a problem with the grammar of GNU 3DLDF. It's rather
large,
and I believe that's part of the problem, so it's not
possible to provide a minimal example. I tried to attached the
debugging output files from three runs of Bison in a tarball,
but I kept getting my message returned.
Since the files are rather large, did you considering provide a URL
instead.
I've now attached them as plain
text files.
I would like to have the following rule:
point_primary: GET_POINT numeric_secondary
conic_section_lattice_primary
When I run Bison, however, I get the following, not very informative
message: Abort
Bison succeeds when I change the rule, with varying numbers of
conflicts:
point_primary: GET_POINT LEFT_PARENTHESIS numeric_secondary COMMA
conic_section_lattice_expression RIGHT_PARENTHESIS
-->
parser.y++: conflicts: 421 shift/reduce, 1 reduce/reduce
There were 420 s/r conflicts before I added the rule. I don't
consider
this to be a problem.
Conflict are a problem if the resolution that Bison does (shift
before reduce, first reduce in rule list) does not result in the
correct parsing. Keeping track of hundreds of conflicts are resoled
correctly seems rather difficult.
Have you tried resolving them using precedences %left, etc.? Look in
the conflicting state, and apply the precedences to the tokens
immediately before and after the "." in the conflicting shift/reduce
states.
(See debugging output file `p0.txt' in attached tarball.)
*********************
point_primary: GET_PATH_POINT LEFT_PARENTHESIS numeric_secondary COMMA
conic_section_lattice_expression RIGHT_PARENTHESIS
-->
parser.y++: conflicts: 424 shift/reduce, 1 reduce/reduce
(See `p1.txt' in attached tarball.)
*********************
point_primary: GET_POINT numeric_secondary COMMA
conic_section_lattice_expression
parser.y++: conflicts: 844 shift/reduce, 1 reduce/reduce
(See `p2.txt' in attached tarball.)
************************
The relationship between the states and the rules seems to be rather
complex.
Right, that is dictated by the LALR(1) algorithm (plus some
optimizations).
When Bison has failed before, I've sometimes been able to
fix the problem by using a `<type>_secondary' or `<type>_tertiary'
rather than a `<type>_primary' or making a similar substition.
This didn't work in this case.
So one has to fiddle around with the grammar a bit. If you had given
a link to the .y grammar, folks might have done some test-compiles.
I also tried using a different token instead of `GET_POINT', namely
`GET_PATH_POINT'. The results were similar, but not completely
the same. I really don't want to be using parentheses or
different tokens like this if I can avoid it.
For example, you have a rule
any_variable:
...
| color_variable
...
;
and then
...
color_variable: variable . COLOR;
...
This means that any_variable does not have a token in it, to
determine which state to go to, which might generate shift/reduce
conflicts. It might be better with
any_variable:
...
| variable . COLOR
...
;
Anyway, because of the way LALR(1) works, fiddling around a bit like
that might help. The reason is that lookahead is just one token, so
it might help having a token in the state. The algorithm can resolve
some, but for example, shift/reduce resolution requires is more crude.
My grammar is likely to become larger and more complex as I add
symbols
and and rules for more geometrical entities, so I'm afraid this will
keep happening.
Any suggestions would be much appreciated.
I think you need to focus on getting rid of the shift/reduce
conflicts you already have.
Hans Aberg
- Conflicts in large grammar, Laurence Finston, 2007/08/03
- Re: Conflicts in large grammar,
Hans Aberg <=
- Re: Conflicts in large grammar, Laurence Finston, 2007/08/05
- Re: Conflicts in large grammar, Hans Aberg, 2007/08/05
- Re: Conflicts in large grammar, Laurence Finston, 2007/08/05
- Re: Conflicts in large grammar, henrik . sorensen, 2007/08/05
- Re: Conflicts in large grammar, lfinsto1, 2007/08/06
- Re: Conflicts in large grammar, Laurence Finston, 2007/08/08
- Re: Conflicts in large grammar, Hans Aberg, 2007/08/08
- Re: Conflicts in large grammar, Laurence Finston, 2007/08/08
- Re: Conflicts in large grammar, Alfonso Urdaneta, 2007/08/08
- Re: Conflicts in large grammar, Hans Aberg, 2007/08/08