Re: [Pyparsing] Operator Precedence and Associativity.

[Paolo L. <p....@hy...>]

Ralph Corderoy wrote:
>> "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.

It is not left-recursive, of course.
In your example you basically build the tree in the correct way
instead of rearranging it. But please note that in my example I could 
not add a parse action to ZeroOrMore but to expr.
Simply modifing or parametrizing the current tree building policy
in one of the existing tokens is not enough.

a new token as the ones that I suggested could maybe provide a solution
(similar to your parse_term or parse_expr in how the tree is built).

Translating a set of operator precedence and associativity rules in 
order to adapt parse behaviour could be a step further but, in terms
of interface, I'd prefer using the one the I suggested...

If you think that could be a solution, I could try to provide an 
implementation...

	Ciao
	Paolo

> 
> 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()
>