Re: Is that difficult to write a Shift-Reduce parser

kuangpma <kuangpma@gmail.com> wrote:
> Hi,
> I am learning compiler theory, several books teach how to write (even
> with source code) a Recursive Decent parser but not Shift Reduce
> parser, only tell the theroy behind it. Particularly the Louden book,
> it says that handcrafting a Shift Reduce parser is very difficult so
> it suggests to use tools such like yacc to generate the parser.


There are various shift/reduce stategies. Most modern texts probably
assume or are locked onto LR(k) or LALR as the only S/R method around.


Some old stuff is fairly easy to understand. E.g. the precedence
grammar idea or -- even more pedagogic -- operator precedence.


Usually S/R parsers have a fixed "engine" that is driven by tables.
Making the tables compact takes up a lot of the intelligibility bandwidth.
But some very old co-no ("current operator -- next operator") parsers(*)
were nothing more than a fancy 2-d switch statement.


> So my question is that why Shift Reduce parser is difficult to write?
> Is really impossible (well, relatively) to write it?


In the old days people (yes, actual people) used to create the tables for
S/R parsers by hand. So it can't be hard, can it?


Again, try Wikipedia for an introduction.


===
(*) Yes, John, I'm talking about compilers that took 80 column cards as input.
[Yes, I used them too. It sounds like you're talking about operator
precedence expression parsers, which are simpler than what we usually refer
to as shift/reduce. -John]

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