## LL(1) Grammars - Parsing Tables

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

#### WhiteRose

##### February 05, 2014, 11:40:05 pm
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

##### February 05, 2014, 11:58:16 pm #1
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 | 1S --> + S S | * S S | a  // no common left factor but common middle    S --> A B | a    A --> + | *    B -->  S SS --> 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

##### February 06, 2014, 12:10:42 am #2
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

##### February 06, 2014, 12:13:42 am #3
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

##### February 06, 2014, 12:30:24 am #4
*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

##### February 06, 2014, 01:57:14 am #5
This assignment is killing me.

*sobs*

I'm switching my major to drawing flowers.

#### Blizzard

##### February 06, 2014, 02:08:52 am #6
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

##### February 08, 2014, 09:21:16 pm #7
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 ). 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: Show

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 ). 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: Show

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