[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: BIG BUG



Philippe wrote:
> Hello, try to compile this file
>...
> You will have a bug :
>...
> ..shift/reduce conflict on TTlvk0600 in {
>  [PSsap = TTlvp8104 PSuite03Ssap PSuite04Ssap]:1:EOF,
>  [PSuite03Ssap = TTlvk0600 TTlvp8605]:0:TTeor,
>  [PSuite03Ssap = TTlvk0600 TTlvp8605]:0:TTlvk0600,
>  [PSuite03Ssap = ]:0:TTeor,
>  [PSuite03Ssap = ]:0:TTlvk0600
> }


OK. SableCC is telling you that your grammar has an LALR(1) shift/reduce
conflict.

It also tries to help you see the problem by telling you the exact place
the conflict happens.

shift/reduce conflict on TTlvk0600: The parser is looking at the next
input token and it sees a TTlvk0600.

Now, look at the line:
[PSsap = TTlvp8104 PSuite03Ssap PSuite04Ssap]:1:EOF

It tells you that the parser is possibly in the following parsing state:
[PSsap = TTlvp8104 PSuite03Ssap PSuite04Ssap]: it is parsing a ssap
production (default alternative)
1: it has already recognized one element. (tlvp8104)
EOF: The token expected to follow this production is EOF.

Simply put, the parser is at the (.) in:
ssap = tlvp8104 (.) suite03Ssap suite04Ssap, followed by EOF

So, if we rewrite everything:

PSsap = TTlvp8104 (.) PSuite03Ssap PSuite04Ssap, followed by EOF,
PSuite03Ssap = (.) TTlvk0600 TTlvp8605, followed by TTeor,
PSuite03Ssap = (.) TTlvk0600 TTlvp8605, followed by TTlvk0600,
PSuite03Ssap = (.), followed by TTeor,
PSuite03Ssap = (.), followed by TTlvk0600

Now you can notice that we need not be concerned by anything not
involving TTlvk0600 as the next expected token.

So, we can eliminate:
PSsap = TTlvp8104 (.) PSuite03Ssap PSuite04Ssap, followed by EOF,
[the (.) is followed by a production PSuite03Ssap, not TTlvk0600]

PSuite03Ssap = (.), followed by TTeor,
[the (.) is followed by TTeor, not TTlvk0600]

We can also merge 
PSuite03Ssap = (.) TTlvk0600 TTlvp8605, followed by TTeor,
PSuite03Ssap = (.) TTlvk0600 TTlvp8605, followed by TTlvk0600,
into
PSuite03Ssap = (.) TTlvk0600 TTlvp8605
[the token following the production is not relevant to our problem,
since the next expected token follows the (.) and is TTlvk0600]

Finally, we have:
PSuite03Ssap = (.) TTlvk0600 TTlvp8605
PSuite03Ssap = (.), followed by TTlvk0600

The parser has two choices, it can possibly 
(1) shift TTlvk0600 to the top of the stack (assuming that the input
will parse to "PSuite03Ssap = TTlvk0600 TTlvp8605;")
(2) reduce the top of the stack (empty in our case) to PSuite03Ssap
(assuming that the input will parse to "PSuite03Ssap = ;")

Since the parser is deterministic, it cannot guess in advance how the
input will be parse. This is the conflict.

What kind of input would cause this?

tlvp8104 tlvk0600

How?

intuition: (2 possibilities)
tlvp8104 tlvk0600 tlvp8604 EOF
tlvp8104 tlvk0600 tlvp8605 teor EOF
(Remember, the parser cannot see the token following tlvk0600.)

Initially the parser is in state:
PSsap = (.) TTlvp8104 PSuite03Ssap PSuite04Ssap, followed by EOF,

The parser reads tlvp8104. It is now in the state described in the error
message.
PSsap = TTlvp8104 (.) PSuite03Ssap PSuite04Ssap, followed by EOF,
...

To see it: tlvk0600 can either be:
(1) the first token of PSuite03Ssap, if PSuite03Ssap reduces to
[PSuite03Ssap = TTlvk0600 TTlvp8605;]
(2) the first token of PSuite04Ssap, if PSuite03Ssap reduces to
[PSuite03Ssap = ;]

I hope this helps.

(You can not that an LL(1) parser would have had the same problem. It
would not be able to determine which alternative of PSuite03Ssap to
pick).

I am sorry if this is a bit complicated. If you can grab any compiler
book that explains LR parsers, it could help you.

> Third problem:
> Suppress the comment on the line "//xsap = teor ; " and compile no error ?

Obvious. Your "main" production only expects teor.

> Fourth problem:
> With the comment //xsap, replace "| {x4}" in suite03_ssap by "| {x4} teor". You
> have no
> error ! Why ?

Obvious again. There is no ambiguity anymore. tlvk0600 is definitely the
first token of suite03_ssap if you see the following input:

tlvp8104 tlvk0600

> Happy New year.

Happy new year.

Etienne