CODEWITHSUNDEEP
pythonparsingcontext-free-grammarpyparsing
user650261
user650261

Reputation: 2264

Parser failing - pyparsing

I am trying to create a parser which converts some math to C. This boils down to be having to find nested expressions of the form ...^x, and replace that with pow(...,x) (here x is a number).

A few assumptions:

I can clarify more assumptions if I missed something (just ask).

My code is shown below, along with a failed example. Why is this failing?

Code:

from pyparsing include *
def parse(s):
    identifier = Regex(r'-?[a-zA-Z0-9_]+')
    real = Regex(r'-?[0-9]+(\.?[0-9]+)?(e-?[0-9]+)?')
    oper = Regex(r'[\*\+/-]-?')
    #oper = oneOf("* + - /")

    # define arithOperand as a Forward, since it could contain nested power expression
    arithOperand = Forward()
    arithExpr = arithOperand + ZeroOrMore(oper + arithOperand)
    groupedArithExpr = '(' + arithExpr + ')'

    # define expression for x^y, where x could be any kind of arithmetic term
    powerOp = Literal('^')
    powerExpr = (groupedArithExpr|real|identifier) + powerOp + real #order matters?
    powerExpr.setParseAction(lambda tokens: 'pow(%s,%s)' % (tokens[0], tokens[2]))

    # now define the possible expressions for arithOperand, including a powerExpr
    arithOperand <<= powerExpr | real | identifier | groupedArithExpr

    # convert parsed list of strings to a single string
    groupedArithExpr.setParseAction(''.join)

    return arithExpr.transformString(s)

The string which is causing failure:

s = ((s9*(s4*s6+c4*c6*s5)-c5*c6*c9)*(-(c4*s6-c6*s4*s5)*(x1*(1.0/2.0)+BASE_ORIGIN_Z*(s4*s6+c4*c6*s5)+(c4*s6-c6*s4*s5)*(-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*(1.0/2.0)+LEG_LINK_EXTENTS_Y*(1.0/2.0))+BASE_ORIGIN_X*c5*c6)+(c4*c6+s4*s5*s6)*(x2*(1.0/2.0)-BASE_ORIGIN_Z*(c6*s4-c4*s5*s6)-(c4*c6+s4*s5*s6)*(-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*(1.0/2.0)+LEG_LINK_EXTENTS_Y*(1.0/2.0))+BASE_ORIGIN_X*c5*s6)+c5*s4*(x3*(1.0/2.0)-BASE_ORIGIN_X*s5+BASE_ORIGIN_Z*c4*c5-c5*s4*(-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*(1.0/2.0)+LEG_LINK_EXTENTS_Y*(1.0/2.0))))+(c4*s6-c6*s4*s5)*((c9*s5+c4*c5*s9)*(x3*(1.0/2.0)-BASE_ORIGIN_X*s5+BASE_ORIGIN_Z*c4*c5-c5*s4*(-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*(1.0/2.0)+LEG_LINK_EXTENTS_Y*(1.0/2.0)))+(s9*(s4*s6+c4*c6*s5)-c5*c6*c9)*(x1*(1.0/2.0)+BASE_ORIGIN_Z*(s4*s6+c4*c6*s5)+(c4*s6-c6*s4*s5)*(-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*(1.0/2.0)+LEG_LINK_EXTENTS_Y*(1.0/2.0))+BASE_ORIGIN_X*c5*c6)-(s9*(c6*s4-c4*s5*s6)+c5*c9*s6)*(x2*(1.0/2.0)-BASE_ORIGIN_Z*(c6*s4-c4*s5*s6)-(c4*c6+s4*s5*s6)*(-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*(1.0/2.0)+LEG_LINK_EXTENTS_Y*(1.0/2.0))+BASE_ORIGIN_X*c5*s6)))^2

The exponent here is not converted to a pow and the entire input expression remains intact with no changes. What is wrong with my parser?

Upvotes: 1

Views: 87

Answers (1)

PaulMcG
PaulMcG

Reputation: 63709

I think the only thing you are missing is that you are not handling the leading unary '-' operator. This is easily incorporated into your arithOperand expression using:

arithOperand <<= Optional('-') + (powerExpr | real | identifier | groupedArithExpr)

After making this change, your code generates this output (which contains no '^' operators):

pow
  (
    (
      (s9*
        (s4*s6+c4*c6*s5)
      -c5*c6*c9)
    *
      (-
        (c4*s6-c6*s4*s5)
      *
        (x1*pow
          (
            (1.0/2.0)
          ,3)
        +BASE_ORIGIN_Z*
          (s4*s6+c4*c6*s5)
        +
          (c4*s6-c6*s4*s5)
        *
          (-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*
            (1.0/2.0)
          +LEG_LINK_EXTENTS_Y*
            (1.0/2.0)
          )
        +BASE_ORIGIN_X*c5*c6)
      +
        (c4*c6+s4*s5*s6)
      *
        (x2*
          (1.0/2.0)
        -BASE_ORIGIN_Z*
          (c6*s4-c4*s5*s6)
        -
          (c4*c6+s4*s5*s6)
        *
          (-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*
            (1.0/2.0)
          +LEG_LINK_EXTENTS_Y*
            (1.0/2.0)
          )
        +BASE_ORIGIN_X*c5*s6)
      +c5*s4*
        (x3*
          (1.0/2.0)
        -BASE_ORIGIN_X*s5+BASE_ORIGIN_Z*c4*c5-c5*s4*
          (-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*
            (1.0/2.0)
          +LEG_LINK_EXTENTS_Y*
            (1.0/2.0)
          )
        )
      )
    +
      (c4*s6-c6*s4*s5)
    *
      (
        (c9*s5+c4*c5*s9)
      *
        (x3*
          (1.0/2.0)
        -BASE_ORIGIN_X*s5+BASE_ORIGIN_Z*c4*c5-c5*s4*
          (-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*
            (1.0/2.0)
          +LEG_LINK_EXTENTS_Y*
            (1.0/2.0)
          )
        )
      +
        (s9*
          (s4*s6+c4*c6*s5)
        -c5*c6*c9)
      *
        (x1*
          (1.0/2.0)
        +BASE_ORIGIN_Z*
          (s4*s6+c4*c6*s5)
        +
          (c4*s6-c6*s4*s5)
        *
          (-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*
            (1.0/2.0)
          +LEG_LINK_EXTENTS_Y*
            (1.0/2.0)
          )
        +BASE_ORIGIN_X*c5*c6)
      -
        (s9*
          (c6*s4-c4*s5*s6)
        +c5*c9*s6)
      *
        (x2*
          (1.0/2.0)
        -BASE_ORIGIN_Z*
          (c6*s4-c4*s5*s6)
        -
          (c4*c6+s4*s5*s6)
        *
          (-BASE_ORIGIN_Y+BASE_LINK_EXTENTS_Y*
            (1.0/2.0)
          +LEG_LINK_EXTENTS_Y*
            (1.0/2.0)
          )
        +BASE_ORIGIN_X*c5*s6)
      )
    )
  ,2)

EDIT: (some cosmetic cleanup)

In order to keep your operands as single evaluatable groups, you probably would do best to define using:

baseArithOperand = powerExpr | real | identifier | groupedArithExpr
arithOperand <<= Group('-' + baseArithOperand) | baseArithOperand

Also, adding the unary minus will allow you to drop the leading '-' that you added to real and identifier.

To your question about "does order matter" - yes it does. Fortunately, you have put powerExpr ahead of groupedArithExpr, which are the only two alternatives that could cause a problem. If the order of these two were reversed, then I don't think powerExprs would ever be evaluated correctly, as the leading ()-grouped expression would be parsed with the groupedArithExpr expression, leaving you with a parse error at the powerExpr's following '^' character. You could change from the '|' operator ("match first") to the '^' operator ("match longest"), which would force all alternatives to be evaluated and the longest match chosen. But in recursive grammars, "match longest" can run very slowly, or even recurse forever, so I encourage people to design for "match first".

EDIT2:

Never mind about Group, I forgot that you were just doing transformString here - just stick with your original:

arithOperand <<= Optional('-') + (powerExpr | real | identifier | groupedArithExpr)

But looking closer, I see now that identifier really is overly broad, and will match integers as well as identifiers. Better to use the 2-argument Word here (and don't worry about speed - Word will internally build and use a regex for matching):

identifier = Word(alphas, alphanums+'_') # not Regex(r'[a-zA-Z0-9_]+')
real = Regex(r'\d+(\.\d*)?([Ee][+-]?\d+)?')
oper = oneOf("* + - /")

EDIT3: for your convenience, here is the function I wrote to indent your monstrosity of an example:

def output_nested_parens(s):
    out = ''
    indent = ''
    for c in s:
        if c == '(':
            indent += '  '
            out += '\n' + indent
            out += c
        elif c == ')':
            indent = indent[2:]
            out += c
            out += '\n' + indent
        else:
            out += c
    return out

Upvotes: 1

Related Questions