Pyparsing

Question

我正在搜索一些代数并尝试匹配以下形式的所有表达式：

(subexp)^C

其中 C 是一个整数，subexp 可以是以下两个之一：

a) 它可以是 (subexp)^C 形式的另一个表达式 b) 它可以是 var1 op var2 op var3 ... op varn

形式的表达式

其中 var 的形式为字母数字，例如 l2、cd3、hello53 等。 op 是 -、* 或 +。第二个选项也可以包含按括号分组的术语。

（没有空格，为了清楚起见，我只是在某些地方添加了空格）

因此，举个例子：

(a12 + c33 + d34)^2
(a12 * c33 +-d34)^2
((a12 * c33)^5 + c3)^2

等

这种形式的表达将嵌入一行文本中。我需要找到 (subexp)^C 的所有实例，并将它们替换为 pow(subexp, C)。简而言之，我正在尝试将一些计算机代数转换为可运行的 C 代码。

我最初是用正则表达式来做的，但后来意识到它不是正则表达式。对于非嵌套情况，正则表达式为：

line = re.sub(r'\(([a-zA-Z_]+[0-9]+\+?-?\*?)+\)\^[0-9]+', replace_with_pow, line)

这里的line是嵌入多项式的那一行，replace_with_pow是做替换的函数

不幸的是，当表达式可以嵌套时，它就是一个 CFG。

我研究了 pyparsing，但发现示例很难解析，而且缺少文档。不过，这似乎是推荐的库。

任何人都可以提供一个示例脚本来说明如何查找嵌套表达式并替换它们吗？（如果您希望我可以构建它，它可以用于简化问题）

编辑：更新：使用 pyparsing，我现在可以使用以下代码解析所有具有 { stuff ( ...)^C stuff } 形式的嵌套表达式：

closing = pyparsing.Word( ")^" + pyparsing.nums )
thecontent = pyparsing.Word(pyparsing.alphanums) | '+' | '-' | '*' | ',' 
parens     = pyparsing.nestedExpr( '(', closing, content=thecontent)

thecontent2 = thecontent | parens
parens2 = pyparsing.nestedExpr('{', '}', content=thecontent2)

res = parens2.parseString("{sdf(a + (a + b)^5 + c)asdf}")

这让我想到两个问题：

a) 当我匹配我的 ^5 时，解析器将使用它。我怎样才能提取^5？ b) 是否有快速/简单的方法来使用 pyparsing 进行替换？

Answer 1

解决几乎所有解析问题的第一步都是对要解析的语法进行精确定义。如果该语法是上下文无关的，那么上下文无关语法是描述它的绝佳方式，通常比非正式描述或示例目录要好得多。

在这个问题中，你的例子

a12 * c33 +-d34

不符合描述

var op var op var ... op var

因为它有两个并排的 op。在示例中

((a12 * c33)^5 + c3)^2

子表达式 (a12 * c33)^5 + c3 也不是 var op var；相反，它是 ( subexp ) op var。（我知道，您的文字提到 "terms can be grouped by parentheses"，但没有提到 "term" 实际上可以是 subexp，因为它可能是一个指数，如您的示例所示。）

更精确的语法可能是（如果我猜对的话），用 "yacc" 语法写成：

val : IDENTIFIER
    | '(' expr ')'
term: val
    | val '^' INTEGER
    | '-' val
prod: term
    | term '*' prod
expr: prod
    | expr '+' prod
    | expr '-' prod

以上不允许--var、var^I1^I2甚至-var^I。从你的描述中我不知道你是否希望这些工作，但修改起来很容易。另外，我原以为数字文字是可以接受的，而不仅仅是变量，但在你的问题描述中也没有提到（而且它只需要添加到 val）。

您实际上可能不需要如此精确地解析，因为您似乎只打算生成 C 代码，因此不需要处理运算符优先级。另一方面，您可能有一天希望进行代数变换，在这种情况下需要更精确的解析，而且无论如何都不会花费太多。

掌握语法后，您可以使用 ply（例如）将其转换为可执行的解析器。

(这是我拼凑的 ply 文件。但样式不是很好 :( )

from ply import lex, yacc
class Lexer(object):
  tokens = ('INTEGER', 'IDENTIFIER')
  literals = '+ - * ( ) ^'.split()
  t_ignore = ' \t\n'
  t_INTEGER = r'[1-9][0-9]*'
  t_IDENTIFIER = r'[a-z]+[0-9]+'

  def t_error(self, t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1)

  def build(self, **kwargs):
    self.lexer = lex.lex(module=self)

# Parser starts here

tokens = Lexer.tokens
start = 'expr'

def p_unit(p):
  '''val  : IDENTIFIER 
     term : val      
     prod : term    
     expr : prod   
  '''
  p[0] = p[1]

def p_paren(p):
  '''val  : '(' expr ')' '''
  p[0] = p[2]

def p_binary(p):
  '''expr : expr '+' prod
     expr : expr '-' prod
     prod : term '*' prod
  '''
  p[0] = '(%s%s%s)' %(p[1], p[2], p[3])

def p_pow(p):
  '''term : val '^' INTEGER'''
  p[0] = 'pow(%s, %s)' % (p[1], p[3])

def p_unary(p):
  '''term : '-' val'''
  p[0] = '(-%s)' % p[2]

parser = yacc.yacc()
lexer = Lexer().build()
def parse(text):
  return parser.parse(text, lexer=lexer)

if __name__ == '__main__':
  from sys import argv
  for text in argv[1:]:
    print(text + ' => ' + parse(text))

快速测试：

$ python exp.py '(a12 + c33 + d34)^2' '(a12 * c33 +-d34)^2'
(a12 + c33 + d34)^2 => pow(((a12+c33)+d34), 2)
(a12 * c33 +-d34)^2 => pow(((a12*c33)+(-d34)), 2)
$ python exp.py '((a12 * c33)^5 + c3)^2'
((a12 * c33)^5 + c3)^2 => pow((pow((a12*c33), 5)+c3), 2)

Answer 2

nestedExpr 并不是真正的方法，当嵌套标点符号内的项目定义不太明确时，pyparsing 中的那个方法就在那里。在您的情况下，您最好使用 pyparsing Forward()s 定义自己的嵌套。见下文：

from pyparsing import *

# define arithmetic items
identifier = Word(alphas, alphanums+'_')
integer = Word(nums)
real = Regex(r'\d+\.\d*')
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|integer|identifier) + powerOp + integer
powerExpr.setParseAction(lambda tokens: 'pow(%s,%s)' % (tokens[0], tokens[2]))

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

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

# show how transform string will apply parse actions as transforms
print arithOperand.transformString("x = (4*(1 + 3^2) * a)^10")
print

打印x = pow((4*(1+pow(3,2))*a),10)

arithExpr.runTests("""\
    (a12 + c33 + d34)^2
    (a12 * c33 +-d34)^2
    (a12 * (c33 + c3))^2
    (a12 * (c33 + c3)^4)^2
    ((a12 * c33 + 12)^5 + c3)^2""")

打印

(a12 + c33 + d34)^2
['pow((a12+c33+d34),2)']

(a12 * c33 +-d34)^2
       ^
Expected ")" (at char 11), (line:1, col:12)

(a12 * (c33 + c3))^2
['pow((a12*(c33+c3)),2)']

(a12 * (c33 + c3)^4)^2
['pow((a12*pow((c33+c3),4)),2)']

((a12 * c33 + 12)^5 + c3)^2
['pow((pow((a12*c33+12),5)+c3),2)']

请注意上面 transformString 的使用 - 这将在您的源代码中搜索匹配项并将修改后的代码拼接回找到匹配项的位置。

Pyparsing - 查找嵌套多项式

Pyparsing - Finding Nested Polynomials

python

regex

context-free-grammar