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-21 0:48

This is what I eventually did, I think it should work. Thanks for the help, those of you who actually helped me, haha.

>>11
Ya, I've been reading this page all day long. Finally done with the assignment. Just curious, are you a CS major, or just a guy that finds automata interesting?

The following rightmost derivation occurs:

S -> aSb -> aaSbb -> aaaSbbb -> aaabbb

It is safe to assume that any sentential form in a rightmost derivation looks like one of the following forms with n ≥ 0:

aSb, a^nSb^n, a^nb^n

To get to states aSb, and a^nSb^n, we don’t require any look ahead, however when getting to the final state, a^nb^n we require to look ahead one beyond the handle.

Sentential Form                    Handle             Lookahead
    aSb            (S -> aSb, 3)        0
    a^nSb^n            (S -> aSb, n+2)    0
    a^nb^n            (S -> ^, n+1)        1

Therefore, since the maximum required Lookahead is a single character, S is an LR(1) grammar.

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