It's about time this board got some use, right?
I took a class last semester that did a lot of stuff with parse tables and thought that I knew how they worked, but I'm trying to do a homework problem about them and I'm really confused.
Here's the problem:
Quote
For each of the following grammars, devise predictive parsers and show the parsing tables. You may left-factor and/or eliminate left-recursion form your grammars first if needed:
S --> 0 S 1 | 0 1
S --> + S S | * S S | a
S --> S ( S ) S | epsilon
It shouldn't be that hard, but for some reason I just can't get it.
To make a parse table, you put all of the non-terminals as row headers, and all of the terminals as column headers, and in the cross sections just put the rule that you would use to get that terminal, right? But I looked up an example problem and it's so different from what I thought. They keep splitting the grammars up (which is what I assume they mean by eliminating left-recursion,) but I can't figure out what they're doing in order to split them up like that.
Does anyone have any ideas? :(
suddenly I realize just how far behind I am I'll be learning this stuff next year. fuck it all.
anyway a quick google of the topic and I think I understand your question but I'm not sure this will answer it
S --> 0 S 1 | 0 1 // has common left factor
S --> 0 B
B --> S 1 | 1
S --> + S S | * S S | a // no common left factor but common middle
S --> A B | a
A --> + | *
B --> S S
S --> S ( S ) S | epsilon // no idea
that help at all?
I think so.... It's still confusing, but I think it's starting to come together a little more. I'll give it another try and see if I can figure it out with that. Thanks.
wow, I spent like 10 minutes on that after googleing what LL(1) grammars even were, glad it helped
*flips through Compiler textbook*
*stares*
*throws it on the ground*
I can't remember any of this.
I don't think the second one needs to be rewritten. It looks solvable as is.
This assignment is killing me. :(
*head on desk*
*sobs*
I'm switching my major to drawing flowers. :'(
Quote from: KK20 on February 06, 2014, 12:30:24 am
I can't remember any of this.
This. I know my way around regex, but I don't remember how you solve these problems. xD
There should be a few algorithms that you learned which can be used to simplify this. I remember that there was a small number of transformations that can be done in LL(1) grammar.
Not sure if it will help at all, but this presentation seemed to be fairly clear (in comparison to some of the other reference sources I found :haha:). Of course I've never had a class on compilers, so take that with a grain of salt. He touches on left-recursion grammar in modern programming languages towards the end of the video.
Looks tough, but I'm sure you'll get it!
Quote from: locowhiteknight on February 08, 2014, 09:21:16 pm
Not sure if it will help at all, but this presentation seemed to be fairly clear (in comparison to some of the other reference sources I found :haha:). Of course I've never had a class on compilers, so take that with a grain of salt. He touches on left-recursion grammar in modern programming languages towards the end of the video.
Looks tough, but I'm sure you'll get it!
That video is better than any of the ones that I've found. Thanks!
- pulled your message out of his quote before it go lost ~Ryex