Author Topic: LL(1) Grammars - Parsing Tables  (Read 8144 times)

Offline WhiteRose

  • Trying to code in Ruby
  • Moderator
  • Lexima Warrior
  • ***
  • Posts: 2341
  • LV: 127
  • Gender: Female
  • <3
    • View Profile
LL(1) Grammars - Parsing Tables
« on: February 06, 2014, 06:40:05 AM »
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? :(

Offline Ryex

  • Arctic Bird of Programming
  • Global Moderator
  • Chaos Ultimate
  • ****
  • Posts: 5131
  • LV: 197
  • Gender: Male
  • Wants to write a compiler for fun
    • View Profile
Re: LL(1) Grammars - Parsing Tables
« Reply #1 on: February 06, 2014, 06:58:16 AM »
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

Code: [Select]
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.

DropBox, the best free file syncing service there is.
(click to show/hide)

Offline WhiteRose

  • Trying to code in Ruby
  • Moderator
  • Lexima Warrior
  • ***
  • Posts: 2341
  • LV: 127
  • Gender: Female
  • <3
    • View Profile
Re: LL(1) Grammars - Parsing Tables
« Reply #2 on: February 06, 2014, 07:10:42 AM »
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.

Offline Ryex

  • Arctic Bird of Programming
  • Global Moderator
  • Chaos Ultimate
  • ****
  • Posts: 5131
  • LV: 197
  • Gender: Male
  • Wants to write a compiler for fun
    • View Profile
Re: LL(1) Grammars - Parsing Tables
« Reply #3 on: February 06, 2014, 07:13:42 AM »
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.

DropBox, the best free file syncing service there is.
(click to show/hide)

Online KK20

  • Master Scripter Fixer
  • Global Moderator
  • Guardian of Chaos
  • ****
  • Posts: 3038
  • LV: 372
  • Gender: Male
  • Bringer of Salt
    • View Profile
Re: LL(1) Grammars - Parsing Tables
« Reply #4 on: February 06, 2014, 07:30:24 AM »
*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 AceUpgrade RMXP to RMVXA performance!
XPA TilemapTilemap rewrite with many features, including custom resolution!


NNID: KK20-CP
Discord: KK20 Tyler#8901
Join the CP Discord Server

Offline WhiteRose

  • Trying to code in Ruby
  • Moderator
  • Lexima Warrior
  • ***
  • Posts: 2341
  • LV: 127
  • Gender: Female
  • <3
    • View Profile
Re: LL(1) Grammars - Parsing Tables
« Reply #5 on: February 06, 2014, 08:57:14 AM »
This assignment is killing me. :(

*head on desk*

*sobs*

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

Offline Blizzard

  • This sexy
  • Administrator
  • has over 9000 posts
  • *****
  • Posts: 19929
  • LV: 642
  • Gender: Male
  • Magic midgets.
    • View Profile
    • You're already on it. (-_-')
Re: LL(1) Grammars - Parsing Tables
« Reply #6 on: February 06, 2014, 09:08:52 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      King of Booze: Never Ever      Pet Bots
Drinking Game for Android      Never have I ever for Android      Pet Bots for Android
Drinking Game for iOS      Never have I ever for iOS      Pet Bots for iOS
Drinking Game on Steam


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

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

Offline locowhiteknight

  • Awakened Visionist
  • **
  • Posts: 91
  • LV: 5
  • Gender: Male
    • View Profile
Re: LL(1) Grammars - Parsing Tables
« Reply #7 on: February 09, 2014, 04:21:16 AM »
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.

(click to show/hide)

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



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

Offline WhiteRose

  • Trying to code in Ruby
  • Moderator
  • Lexima Warrior
  • ***
  • Posts: 2341
  • LV: 127
  • Gender: Female
  • <3
    • View Profile
Re: LL(1) Grammars - Parsing Tables
« Reply #8 on: February 09, 2014, 04:59:58 AM »
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.

(click to show/hide)

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
« Last Edit: February 09, 2014, 10:44:18 AM by Ryex »