Proving that a grammar is LR(1)

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

I would really like to talk about this if it wasn't your homework. Sorry.

>> 2

Yes, it is my homework. I'm not asking you to give me the answer, but maybe help lead me to the conclusion so I can remember it in the future. Isn't the point of taking a class to learn the subject? Not trying to get easy points or anything.

>>3
Isn't the point of taking a class to learn the subject?
Maybe, but /prog/ isn't your classroom.

ooohh wait, if I make a dfa for the grammar, that would prove that it's LR(1) right?

>>4

well, prog is everyone's classroom, where everyone is a teacher, student, and autist.

>>3

alright how do you define a LR(1) grammar?

>>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.

Sorry I keep forgetting to sage btw

>>8
Sage if you have nothing useful to contribute. Bump whenever you have a relevant post.

>>9
In other words, always sage.

>>7

cool, you are probably more familiar with this than i am. Do you think you could produce a rightmost derivation for any string in that language using that grammar, where the only information you have available is where you are in the string, the one character that is ahead of where you are in the string, and terminals/non-terminals behind you, on the stack?

the wikipedia page is actually pretty complete:

http://en.wikipedia.org/wiki/LR(1)_grammar

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.

Whenever I would get stuck in university, I would read the textbook.

Seriously, the textbooks will explain everything. Students these days, thinking they can get a free ride and take shortcuts.

>>12

I've been exposed to automata in the past, so there's enough context there for me to follow up on it a bit.

I'm a bit sketchy on some of the terms, and how a look ahead functions when making a derivation. I suppose the look ahead is the is terminal symbol immediately after the rightmost Non Terminal symbol in the sentential form?

I've always thought about it more like a your this machine that has a stack, a state, and your are reading from a string. So if was going to try to parse dat shit:


S -> aSb
S -> --empty-string--

I'd be all like:


|.aaaaaabbbbbb$  push dat a bro
|a.aaaaabbbbbb$  push dat a bro
|aa.aaaabbbbbb$  push dat a bro
|aaa.aaabbbbbb$  push dat a bro
|aaaa.aabbbbbb$  push dat a bro
|aaaaa.abbbbbb$  push dat a bro
|aaaaaa.bbbbbb$  wo shit! we got a a before a b, lets reduce an |S from da muthafucking empty string bro!
|aaaaaaS.bbbbbb$  lets push dat b bro
|aaaaaaSb.bbbbb$  lets reduce dat aSb bro
|aaaaaS.bbbbb$  lets reduce dat aSb bro
|aaaaaSb.bbbb$  lets push dat b bro
|aaaaaSb.bbbb$  lets reduce dat aSb bro
|aaaaS.bbbb$  lets push dat b bro
|aaaaSb.bbb$  lets reduce dat aSb bro
|aaaS.bbb$  lets push dat b bro
|aaaSb.bb$  lets reduce dat aSb bro
|aaS.bb$  lets push dat b bro
|aaSb.b$  lets reduce dat aSb bro
|aS.b$  lets push dat b bro
|aSb.$  lets reduce dat aSb bro
|S.$  whoa shit bro! We're done bro!
|S$.  lets reduce dat shit to da super start symbol yo
Y.  fuck yea

>>13
I'd read text books that were printed in the seventies and fifties. Good times.

>>15
What the fuck are you talking about?

>>16

it doesn't concern you