ee163ahp@sdccs7.UUCP (05/26/84)
Most of the people I have talked to recommend I write my PLX compiler (for my micro) using an LR(1) parsing method. I argued that it was to tedious to construct the parse tables by hand, but, there were a lot of people who said otherwise. Anyways, all I have to say is "The principle drawback of the method is that it is too much work to implement an LR parser by hand for a typical programming language grammmar" I still believe that recursive descent is the only feasible parsing technique for small micros, unless a parser generator exists for such -"..but there ain't no such animal" (for the apple that is.) Send flames to Alfred V. Aho and Jeffrey D. Ullman. It is their quote from "Principles of Compiler Design" Oh yes. one more thing. I recieved so many flames on the "ease" of constructing the sets of items for a language, that I am going to go ahead and construct the sets of a small grammar for you all to see how fun it it. E->E+T T->T*F|F F->(E) F->id I0: E->_E E->_E+T E->_T T->_T*F T->_F F->_(E) F->_ID I1: E->E_ E->E_+T I2: E->T_ T->T_*F I3: T->F_ I4: F->(_E) E->_E+T E->_T T->_T*F T->_F F->_(E) F->ID I5: F->ID_ I6: E->E+_T T->_T*F T->_F F->_(E) F->_ID I7: T->T*_F F->_(E) F->_ID I8: F->(E_) E->E_+T I9: E->E+T_ T->T_*F I10: T->T*F_ I11: F->(E)_ (TAKEN FROM AHO & ULMAN PRIN. OF COMP. DESIGN. P. 208) Well there you have it. Maybe, I should post the set of items for a language like C. I'm sorry I sound so sarcastic, but getting burned(by flames) too many times will do that to you. The point is that each unique item corressponds to a state and there are too many, and recursive descent is easier.
johnl@haddock.UUCP (05/30/84)
#R:sdccs7:-124000:haddock:12300002:000:1236 haddock!johnl May 28 22:52:00 1984 Anybody who says that creating LR(1) parse tables by hand is easy has a different understanding of "easy" than the rest of us do. However, there's no need to do it by hand. If you're using a UN*X system, you have yacc handy. Run your grammar through yacc, which creates a parser consisting mostly of tables and partly of a C program to interpret them. Discard the C code (since it belongs to AT&T, and you're probably not programming your micro in C anyway) and use the tables. Read Aho & Ullman and the C code you just discarded to figure out what the tables mean. The big advantages of LR(1) parsing are that the tables can be constructed mechanically from the grammar, which makes subsequent tweaks to the grammar easy, and that it detects an error quickly -- as soon as it sees a symbol that can't be part of a legal piece of syntax. The disadvantage is that the tables can be kind of large. If you're tight on space and your language isn't too big or wierd, you might consider doing what Ritchie's original compiler (which had two passes, each of which fit in 12K) does, operator precedence for the expressions and recursive descent for everything else. Much smaller and not all that hard to write. John Levine, ima!johnl
lee@west44.UUCP (Lee McLoughlin) (06/01/84)
I have used an LR(1) (well actually an LALR(1)) parser generator to generate a compiler for an 8 bit machine. The parser generator was none other than YACC! It generated a parser in pascal which was efficient, fast, reasonably short (it was a one pass compiler so it had to be). Why bother with LL when you don't have ABSOLUTELY have to? -- "The wizard of OS" Lee McLoughlin ....!ukc!root44!west44!lee ....!ukc!lmcl
mauney@ncsu.UUCP (Jon Mauney) (06/01/84)
> Why bother with LL when you don't have to?
On the contrary, given that LL(1) tables are generally smaller,
LL parsers are simpler, LL lets you put semantic actions anywhere you like,
LL parser generators are available from several sources,
and LL is nearly as powerful as LALR,
Why bother with bottom-up parsing if you don't have to?
--
_Doctor_ Jon Mauney, mcnc!ncsu!mauney
\__Mu__/ North Carolina State Universitykurt@fluke.UUCP (Kurt Guntheroth) (06/05/84)
-----
I wrote a compiler using an LR parser on a miserable little microcomputer a
few years ago. I generated LR tables by hand and added them to the machine
code parser.
1. It is possible to construct a working compiler in this way. In fact, I
had pretty good results, especially nice was the fact that I could do things
on shift as well as reduce operations. I could also take extra shortcuts
you couldn't take if you weren't intimately involved in the tables.
2. I would never do it again. It is quite easy to miss a transition when
building the LR tables. Then you get occaisional statement forms that can't
be parsed. What a hassle.
3. If I had to do it again, I'd run yacc (or some such) and get a list of
the LR(0) states, then hand craft the tables.
--
Kurt Guntheroth
John Fluke Mfg. Co., Inc.
{uw-beaver,decvax!microsof,ucbvax!lbl-csam,allegra,ssc-vax}!fluke!kurt