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

Tony Finch <dot@dotat.at> wrote:
+---------------
| rpw3@rpw3.org (Rob Warnock) wrote:
| >The "trick" to hybridizing this with recursive descent is to assign
| >*very* high operator priorities to the start tokens of control expressions
| >[e.g., "keywords" such as BEGIN, IF, WHILE, etc.] and *very* low priorities
| >to the ends of expressions ["stoppers" such as END, ELSE, FI, right-paren,
| >right-bracket, comma, semicolon, &c]. This causes the simple operator
| >precedence parser to quite naturally behave as a recursive descent parser
| >when it encounters any of those constructs. ;-}
|
| This sounds a bit like the top-down operator precedence parser
| that Douglas Crockford is particularly fond of.
| http://javascript.crockford.com/tdop/tdop.html
+---------------


Quite a bit, yes [thanks for the pointer!], although Crockford's
realization does not use the explicit "SYM/DEL/FUTSYM/FUTDEL" 4-lexeme
window that the BLISS family of compilers used, which explicitly
separates "values" [including reduced expressions] and "operators"
at the lexeme level. If I'm reading him correctly, I suspect that's
why he had to distinguish between "NUDs" & "LEDs":


        The technique we will develop here uses token objects whose members
        include binding powers (or precedence levels), and simple methods
        called NUD (null denotation) and LED (left denotation). A NUD does
        not care about the tokens to the left. A LED does. A NUD method is
        used by values (such as variables and literals) and by prefix
        operators. A LED method is used by infix operators and suffix
        operators. A token may have both a NUD method and a LED method. For
        example, "-" might be both a prefix operator (negation) and an infix
        operator (subtraction), so it would have both NUD and LED methods.


whereas in BLISS (with a 4-lexeme window visible to reduction functions)
the disambiguation can be done because "-" will only appear in DEL
(or FUTDEL), and the reduction function can look in SYM to see if
there's a l.h.s. value (infix) or not (unary). [Actually, many of
my own uses of this style have gotten away with only a SYM & a DEL
(2-lexeme window), but the point still stands -- things are lot simpler
if you can distinguish "<op1> <op2>" from "<op1> <value> <op2>" at
the lexeme (token) level.]


-Rob


-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

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