Re: Are lalr parse-tables viable?

"craig" <>
21 Jun 2004 23:39:04 -0400

          From comp.compilers

Related articles
Are lalr parse-tables viable? (craig) (2004-06-11)
Re: Are lalr parse-tables viable? (2004-06-12)
Re: Are lalr parse-tables viable? (A Johnstone) (2004-06-13)
Re: Are lalr parse-tables viable? (Chris F Clark) (2004-06-13)
Re: Are lalr parse-tables viable? (craig) (2004-06-21)
Re: Are lalr parse-tables viable? (craig) (2004-06-25)
Re: Are lalr parse-tables viable? (Chris F Clark) (2004-06-28)
| List of all articles for this month |

From: "craig" <>
Newsgroups: comp.compilers
Date: 21 Jun 2004 23:39:04 -0400
Organization: 1&1 Internet AG
References: 04-06-038
Keywords: parse, LALR
Posted-Date: 21 Jun 2004 23:39:04 EDT

Thanks For The Feedback - I Feel More Comfortable Knowing That This Is Not
Extraordinarily Large.

> LR parse tables do tend to be rather large, so some parser generators
> use various tricks to compress the table -- the number of states and
> transitions are not changed, but the data structure used to represent
> them is smaller than the obvious two-dimensional table will be.

yes, i did not think that the 2d-array approach would have worked optimally,
so i designed a slightly more complicated data-structure which suffers a
little performace loss against a huge space saving.

> Use operator precedence declarations to resolve ambiguities
> (instead of rewriting the grammar) whenever this is possible.

this advice sadly comes too late. i wrote the grammars upfront to be lr-free
(i assumed this would be beter than converting later). unless i am missing
something, there shouldn't be any ambiguities.

> Also, if the different dialects of your language only differ in the
> names of keywords, the allowed letters in variable names and similar
> lexical details, you need only change the lexer data for each dialect
> while sharing a single parse table.

the dialects of language are very natural- orientated, so there are
significant differences in syntax. i would have liked to just swap out a set
of keywords, but this leads to some dialects suffering stilted and unnatural

> Doesn't sound out of line to me. If you email me your grammar I will
> run it through our tools and explain some of the phenomena that govern
> table size to you.

sounds great - i post it through now.

> If you are parsing multiple dialects, it would not be
> surprising for the number of states to be more than that.

i am only parsing one dialect at a time. that is, the states/transitions
quoted were for the english implementation only.
the dutch and german implementations are of a very similiar order.
but only one language is loaded at a time - that is, if an "english" program
were to be parsed with the "dutch" parser, it would kick and scream errors.
(in dutch, of course...=)

much thanks for your feedback.

craig (at) small (minus) pla (dot) net

Post a followup to this message

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