解析器失败 - pyparsing

Question

我正在尝试创建一个将一些数学转换为 C 的解析器。这归结为必须找到 ...^x 形式的嵌套表达式，并将其替换为 pow(...,x) （这里 x 是一个数字）。

一些假设：

^只会出现在表示求幂的地方
"x" 将始终是 C
在指数 ^ 之前，... 将是某种变量、数字或括号中的分组表达式。变量将是带有（可能）下划线的字母数字字符串。

如果我遗漏了什么（尽管问），我可以澄清更多假设。

我的代码如下所示，还有一个失败的例子。为什么会失败？

代码：

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)

导致失败的字符串：

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

此处的指数未转换为 pow，整个输入表达式保持不变，没有任何变化。我的解析器有什么问题？

Answer 1

我认为您唯一缺少的是您没有处理前导一元“-”运算符。这很容易合并到您的 arithOperand 表达式中，使用：

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

进行此更改后，您的代码生成此输出（不包含“^”运算符）：

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)

编辑：（一些美容清理）

为了将您的操作数保持为单个可评估组，您可能最好使用以下方式定义：

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

此外，添加一元减号将允许您删除添加到实数和标识符的前导“-”。

关于 "does order matter" 的问题 - 是的。幸运的是，您已将 powerExpr 置于 groupedArithExpr 之前，这是仅有的两个可能导致问题的备选方案。如果这两个的顺序颠倒了，那么我认为 powerExprs 永远不会被正确评估，因为前导 ()-grouped 表达式将使用 groupedArithExpr 表达式进行解析，从而在 powerExpr 的以下 '^ 处留下解析错误' 特点。您可以更改“|”运算符 ("match first") 到 '^' 运算符 ("match longest")，这将强制评估所有备选方案并选择最长的匹配项。但是在递归语法中，"match longest" 可以运行非常慢，甚至永远递归，所以我鼓励人们为 "match first".

设计

编辑2：

不要管组，我忘了你只是在这里做 transformString - 坚持你原来的：

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

但仔细观察，我现在发现标识符确实过于宽泛，并且会匹配整数和标识符。最好在这里使用 2 参数 Word（不要担心速度 - Word 将在内部构建并使用正则表达式进行匹配）：

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

EDIT3：为方便起见，这是我编写的用于缩进示例的函数：

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

解析器失败 - pyparsing

Parser failing - pyparsing

python

parsing

pyparsing

context-free-grammar