Re: Intricate problem with scannerless LALR(1) parser

Paul B Mann wrote:


>>However, that keyword-feature has one side effect which I would
>>discuss on the mailing list. Given the following grammar:


>>start: a
>>a: b 'XX'
>>b: c | '[' b ']'
>>c: 'X' | c 'X'


>>[Your grammar is ambiguous. To see where, replace "XX" with xx and
>>define it like this: xx: "X" "X"
(snip)


> I agree with John.


> XX is valid, but ambiguous, either a keyword or two X's.


Are you sure it is ambiguous? Maybe it isn't LALR(1), though. Since
there is no a in b or c, it looks to me that it only matches strings
ending in 'XX'. If b is 'XX' then it still must be followed by
another 'XX'.


It looks to me that it matches 0 or more '['
followed by 1 or more 'X' followed by the same number
of ']' as there were '[', followed by 'XX'.


Looking again, though, it is ambiguous without enough
look ahead to see where the end is. You find out too
late that the last 'XX' are already gone. Easier to parse
from the end back to the start.


-- glen
[You're right. The grammar isn't really ambiguous, but it needs more than
one token of lookahead. -John]

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