Re: Intricate problem with scannerless LALR(1) parser

glen herrmannsfeldt <gah@ugcs.caltech.edu>
Thu, 26 Jun 2008 12:56:47 -0800

          From comp.compilers

Related articles
Intricate problem with scannerless LALR(1) parser mailings@jmksf.com (2008-06-06)
Re: Intricate problem with scannerless LALR(1) parser kamalpr@hp.com (kamal) (2008-06-08)
Re: Intricate problem with scannerless LALR(1) parser GeniusVczh@gmail.com (vczh) (2008-06-09)
Re: Intricate problem with scannerless LALR(1) parser paul@paulbmann.com (Paul B Mann) (2008-06-25)
Re: Intricate problem with scannerless LALR(1) parser gah@ugcs.caltech.edu (glen herrmannsfeldt) (2008-06-26)
Re: Intricate problem with scannerless LALR(1) parser paul@paulbmann.com (Paul B Mann) (2008-06-26)
Re: Intricate problem with scannerless LALR(1) parser parsersinc@earthlink.net (SLK Mail) (2008-06-27)
| List of all articles for this month |

From: glen herrmannsfeldt <gah@ugcs.caltech.edu>
Newsgroups: comp.compilers
Date: Thu, 26 Jun 2008 12:56:47 -0800
Organization: Compilers Central
References: 08-06-010 08-06-063
Keywords: parse, LALR
Posted-Date: 26 Jun 2008 19:54:47 EDT

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]



Post a followup to this message

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