Re: [Pyparsing] Operator Precedence and Associativity.

[Paul M. <pa...@al...>]

> -----Original Message-----
> From: pyp...@li... 
> [mailto:pyp...@li...] On 
> Behalf Of Ralph Corderoy
> Sent: Wednesday, September 13, 2006 7:23 AM
> To: Paolo Losi
> Cc: pyp...@li...
> Subject: Re: [Pyparsing] Operator Precedence and Associativity.
> 
> 
> Hi Paolo,
> 
> > Ralph Corderoy wrote:
<snip>
> 
> I guess I'd like to write
> 
>     number = Words(digit)
>     factor = Forward()
>     factor << RightBinOpSeq(number, expop, factor)
>     unary = OptRightUnaryOpSeq(signop, factor)
>     term = unary ^ LeftBinOpSeq(unary, multop, unary)
>     expr = term ^ LeftBinOpSeq(term, plusop, term)
>     statement = expr + semicolon
> 
> and have the /(Opt)?(Left|Right|Non)(Unary|Bin)OpSeq/ 
> routines do the Grouping implicitly so
> 
>     1+2*-3^4*5+-+-6
> 
> yeilds the tree
> 
>     (                                      , +,                 )
>      (1, +,                               )     (-,            )
>             (                      , *, 5)          (+,       )
>              (2, *,               )                     (-, 6)
>                     (-,          )
>                         (3, ^, 4)
> 
> Although, something like
> 
>     expop = Literal('^')
>     signop = OneOf('+ -')
>     multop = Literal('*')
>     plusop = Literal('+')
> 
>     expr = Forward()
>     term = Forward()
>     unary = Forward()
>     factor = Forward()
> 
>     expr = OperatorGrammar( \
>         expop, 2, 'R',
>         signop, 1, 'R',
>         multop, 2, 'L',
>         plusop, 2, 'L',
>     ''')
> 
> also seems attractive, and simpler to specify.
> 

Well, why not?!  Check this out!

-- Paul


from pyparsing import *

def operatorGrammar( baseExpr, opList ):
    ret = Forward()
    lastExpr = baseExpr | ( Suppress('(') + ret + Suppress(')') )
    i = 0
    for opExpr,arity,rightLeftAssoc in opList:
        thisExpr = Forward()
        thisExpr.setName("expr%d" % i)#.setDebug()
        if rightLeftAssoc == 'L':
            if arity == 1:
                thisExpr << ( Group( lastExpr + opExpr ) | lastExpr )
            else:
                thisExpr << ( Group( lastExpr + OneOrMore( opExpr + lastExpr
) ) | lastExpr )
        else:
            if arity == 1:
                # try to avoid LR with this extra test
                if isinstance(opExpr, Optional):
                    thisExpr << (( FollowedBy(opExpr.expr + thisExpr) +
Group( opExpr + thisExpr )) | lastExpr )
                else:
                    thisExpr << ( opExpr + thisExpr )
            else:
                thisExpr << ( Group( lastExpr + OneOrMore( opExpr + thisExpr
) ) | lastExpr )
        lastExpr = thisExpr
        thisExpr = Forward()
        i += 1
    ret << lastExpr
    return ret


number = Word(nums).setParseAction(lambda t:int(t[0]))
variable = Word(alphas,exact=1)
operand = number | variable

expop = Literal('^')
signop = Optional( oneOf('+ -') )
multop = oneOf('* /')
plusop = oneOf('+ -')
factop = Literal('!')

expr = operatorGrammar( operand,
    [(factop, 1, 'L'),
     (expop, 2, 'R'),
     (signop, 1, 'R'),
     (multop, 2, 'L'),
     (plusop, 2, 'L'),]
    )

test = ["9 + 2 * 3",
        "(9 + 2) * 3",
        "(9 + -2) * 3",
        "(9 + -2) * 3^2^2",
        "(9! + -2) * 3^2^2",
        "M*X + B",
        "1+2*-3^4*5+-+-6",]
for t in test:
    print t
    print expr.parseString(t)
    print 

Gives the following:
9 + 2 * 3
[[9, '+', [2, '*', 3]]]

(9 + 2) * 3
[[[9, '+', 2], '*', 3]]

(9 + -2) * 3
[[[9, '+', ['-', 2]], '*', 3]]

(9 + -2) * 3^2^2
[[[9, '+', ['-', 2]], '*', [3, '^', [2, '^', 2]]]]

(9! + -2) * 3^2^2
[[[[9, '!'], '+', ['-', 2]], '*', [3, '^', [2, '^', 2]]]]

M*X + B
[[['M', '*', 'X'], '+', 'B']]

1+2*-3^4*5+-+-6
[[1, '+', [2, '*', ['-', [3, '^', 4]], '*', 5], '+', ['-', ['+', ['-',
6]]]]]