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

rpw3@rpw3.org (Rob Warnock)
Sun, 09 May 2010 07:59:05 -0500

          From comp.compilers

Related articles
Is that difficult to write a Shift-Reduce parser kuangpma@gmail.com (kuangpma) (2010-04-29)
Re: Is that difficult to write a Shift-Reduce parser kym@sdf.lonestar.org (russell kym horsell) (2010-05-01)
Is that difficult to write a Shift-Reduce parser chakaram@auth.gr (Chariton Karamitas) (2010-05-02)
Re: Is that difficult to write a Shift-Reduce parser rpw3@rpw3.org (2010-05-01)
Re: Is that difficult to write a Shift-Reduce parser cfc@shell01.TheWorld.com (Chris F Clark) (2010-05-02)
Re: Is that difficult to write a Shift-Reduce parser dot@dotat.at (Tony Finch) (2010-05-04)
Re: Is that difficult to write a Shift-Reduce parser sh006d3592@blueyonder.co.uk (Stephen Horne) (2010-05-07)
Re: Is that difficult to write a Shift-Reduce parser rpw3@rpw3.org (2010-05-09)
| List of all articles for this month |

From: rpw3@rpw3.org (Rob Warnock)
Newsgroups: comp.compilers
Date: Sun, 09 May 2010 07:59:05 -0500
Organization: Rob Warnock, Consulting Systems Architect
References: 10-04-072 10-05-003 10-05-014 10-05-023
Keywords: parse, LR(1), LL(1)
Posted-Date: 09 May 2010 12:27:38 EDT

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



Post a followup to this message

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