Re: [Pyparsing] Operator Precedence and Associativity.

[Ralph C. <ra...@in...>]

Hi Paolo,

> Ralph Corderoy wrote:
> > whereas I'd like the left associativity explicit, i.e.
> > 
> >                          +
> >                         / \
> >     1 + 2 + 3    ==>   +   3
> >                       / \
> >                      1   2
> > 
> > I can achieve this with a right-associative operator, e.g. exponent, but
> > how do I do this for left-associative ones whilst avoiding endless
> > left-recursion?
> 
> I think you have no other choice but to rearrange ParseResults by
> setting a specific parse action for the expression:

OK, thanks.  I hadn't got that far, just been banging my head trying to
get the desired result naturally.

> > I wonder if PyParsing would benefit from being able to define operator
> > tables, similar to K&R's, giving the tokens, precedence, and
> > associativity, and being able to plumb that into the rest of the
> > recursive descent parser at some point?
> 
> It's not trivial at all.
> 
>  From http://en.wikipedia.org/wiki/Left_recursion
> 
> "A formal grammar that contains left recursion cannot be parsed by a 
> recursive descent parser"
> 
> PyParsing qualifies as recursive descent parser.

Yes, but I don't think the R.D. parser below, written by hand, not with
pyparsing, is left-recursive.  It can just support different
associativity depending on how the parse tree is built.

Cheers,


Ralph.


#! /usr/bin/python

def main():
    test('1', "'1'")
    test('1+2', "('1', '+', '2')")
    test('1+2+3', "(('1', '+', '2'), '+', '3')")
    test('1*2+3', "(('1', '*', '2'), '+', '3')")
    test('1+2*3', "('1', '+', ('2', '*', '3'))")
    test('1^2^3', "('1', '^', ('2', '^', '3'))")
    test('-3^2', "('-', ('3', '^', '2'))")
    test('-+-3^2', "('-', ('+', ('-', ('3', '^', '2'))))")
    test('1a+2b*3c', "(('1', 'a'), '+', (('2', 'b'), '*', ('3', 'c')))")
    test('5a>b', "(('5', 'a'), 'b')")

def test(s, e):
    r = repr(parse(s))
    if r == e:
        print 'pass: %s => %s' % (s, r)
    else:
        print 'FAIL: %s: want %s. got %s.' % (s, e, r)

def parse(s):
    l = list(s + ';')
    e = parse_statement(l)
    expect(l, ';')
    return e

def parse_statement(s):
    'statement := expr [">" unit]'
    e = parse_expr(s)
    if peek(s) == '>':
        consume(s)
        u = parse_unit(s)
        if not u:
            raise 'Expect unit after >.'
        return (e, u)
    return e

def parse_expr(s):
    'expr := term ["+" term]*'
    a = parse_term(s)
    while peek(s) == '+':
        op = consume(s)
        b = parse_term(s)
        a = (a, op, b)
    return a

def parse_term(s):
    'term := unary ["*" unary]*'
    a = parse_unary(s)
    while peek(s) == '*':
        op = consume(s)
        b = parse_unary(s)
        a = (a, op, b)
    return a

def parse_unary(s):
    'unary := ["+" | "-"] unary | factor'
    sign = '+'
    if peek(s) in '+-':
        sign = consume(s)
        a = parse_unary(s)
        return (sign, a)
    return parse_factor(s)

def parse_factor(s):
    'factor := number ["^" factor]'
    a = parse_number(s)
    while peek(s) == '^':
        op = consume(s)
        b = parse_factor(s)
        a = (a, op, b)
    return a

def parse_number(s):
    'number := "0" | "1" | ... unit'
    if not peek(s).isdigit():
        raise
    i = consume(s)
    u = parse_unit(s)
    if u:
        return (i, u)
    return i

def parse_unit(s):
    'unit := "a" | "b" | "c" | empty'
    if peek(s) not in 'abc':
        return None
    return consume(s)

def peek(s):
    return s[0]

def expect(s, t):
    c = consume(s)
    if c != t:
        raise 'Expected %s but got %s' % (t, c)
    return

def consume(s):
    return s.pop(0)

main()