Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Proving that a grammar is LR(1)

Name: Anonymous 2011-11-20 18:34

Hey /prog/, I was wondering if somebody could help me with this. I need to prove that the following grammar is an LR(1) grammar:

S -> aSb | ^ (note ^ = empty string)

I'm having trouble figuring out how exactly I go about proving this. I think I would need to show that I only need to peak one character ahead of the handle, but I'm not aware of what that would entail.

Thanks in advance for any help

Name: Anonymous 2011-11-20 20:48

>>6

As far as I understand, and LR(1) grammar is a left-to-right scan of the input, with a rightmost derivation in reverse. When parsing with one, you go bottom up. Starting with the terminals, and deriving the non terminals, until you get to the S. If you get there, then the string is accepted by the grammar. The 1 just mean that you can look one character ahead of the current handle. I'm a but fuzzy on the handle's, but it is essentially a pair, first part is the rule that is being applied, and the second part is the position in the string.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List