LL(1) Grammars - Parsing Tables

Started by WhiteRose, February 05, 2014, 11:40:05 pm

Previous topic - Next topic

WhiteRose

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? :(

Ryex

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 no longer keep up with posts in the forum very well. If you have a question or comment, about my work, or in general I welcome PM's. if you make a post in one of my threads and I don't reply with in a day or two feel free to PM me and point it out to me.<br /><br />DropBox, the best free file syncing service there is.<br />

WhiteRose

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.

Ryex

wow, I spent like 10 minutes on that after googleing what LL(1) grammars even were, glad it helped
I no longer keep up with posts in the forum very well. If you have a question or comment, about my work, or in general I welcome PM's. if you make a post in one of my threads and I don't reply with in a day or two feel free to PM me and point it out to me.<br /><br />DropBox, the best free file syncing service there is.<br />

KK20

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

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

WhiteRose

This assignment is killing me. :(

*head on desk*

*sobs*

I'm switching my major to drawing flowers. :'(

Blizzard

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.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

locowhiteknight

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.

Spoiler: ShowHide


Looks tough, but I'm sure you'll get it!



"Let's get down to brass tacks. How much for the ape?"

WhiteRose

February 08, 2014, 09:59:58 pm #8 Last Edit: February 09, 2014, 03:44:18 am by Ryex
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.

Spoiler: ShowHide


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