Are lalr parse-tables viable?

"craig" <craig@small-pla.net>
11 Jun 2004 02:54:40 -0400

          From comp.compilers

Related articles
Are lalr parse-tables viable? craig@small-pla.net (craig) (2004-06-11)
Re: Are lalr parse-tables viable? torbenm@diku.dk (2004-06-12)
Re: Are lalr parse-tables viable? adrian@sartre.cs.rhbnc.ac.uk (A Johnstone) (2004-06-13)
Re: Are lalr parse-tables viable? cfc@shell01.TheWorld.com (Chris F Clark) (2004-06-13)
Re: Are lalr parse-tables viable? craig@small-pla.net (craig) (2004-06-21)
Re: Are lalr parse-tables viable? craig@small-pla.net (craig) (2004-06-25)
Re: Are lalr parse-tables viable? cfc@shell01.TheWorld.com (Chris F Clark) (2004-06-28)
| List of all articles for this month |

From: "craig" <craig@small-pla.net>
Newsgroups: comp.compilers
Date: 11 Jun 2004 02:54:40 -0400
Organization: 1&1 Internet AG
Keywords: parse, Basic, question, LALR
Posted-Date: 11 Jun 2004 02:54:40 EDT

I Am Building A Interpretor For A Basic-Type Language, And Require It Be
Able To Load One Of A Number Of "Dialects" Of The Language. (Eg. English,
German, Spanish, Etc.)


I Have Decided To Seperate The Parse-Table "Data" (Ie. States, Transitions,
Interpretor-Code, Etc.) For Each Dialect From The Actual Parser/Interpretor
Itself - But When I Generate The States And Transition Data From My Ebnf
(Using A Homebrew Analyser) It Finds An Enormous Number Of States And
Transitions.
Like In In The Order Of 327 Unique States And 16258 Transitions Between
These. (It Is A Little Less If I Use The Non-Lr-Free Version, But Then I Get
Loads Of Reduce-Reduce Conflicts).


I Find This Alarmingly Huge!


I Am Very New To Compiler/Interpretor Building, So I Am Unsure As To If This
Is About Right.
Even On A "Tiny" Version Of The Language, Which Basically Only Handles
Simple Arithmetic, It Has A Full 38 States And 323 Transitions. (And It Does
Actually Work!)


As I Recall, The "Dragon" Book (Aho, Sethi & Ullman) Doesn'T Say Too Much
About How Big These Get (I'M Sorry, I Don'T Have My Copy On Hand), And The
Book That I Have Mostly Worked From, The, Uh, "Tiger"(?) Book From Appel
Just Says That "LR(1) Parsing Tables Can Get Very Large, With Many States. A
Smaller Table Can Be Made [... And ] Is Called An LALR(1) Parser".
Mine Is The "Smaller" (LALR) Of These Two.


can anyone please advise me on whether these numbers seem reasonable? are
lalr tables for (say) BASIC or pascal usual this large?


much thanks for your response.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.