将伪代数字符串解析为命令
Parsing pseudo-algebraic string into command
我有一个包含对象列表的字典
objects = {'A1': obj_1,
'A2': obj_2,
}
然后我有一个字符串作为
cmd = '(1.3A1 + 2(A2 + 0.7A3)) or 2(A4 to A6)'
我想将其转换为命令
max( 1.3*objects['A1'] + 2*(objects['A2'] + 0.73*objects['A3']), 2*max(objects['A4'], objects['A5'], objects['A6']))
我的尝试
由于找不到更好的选择，我开始从零开始编写解析器。
个人说明：我不认为将 150 行代码附加到 SO 问题是一个好习惯，因为这意味着 reader 应该阅读并理解它，这是一项艰巨的任务。尽管如此，我之前的问题还是被否决了，因为我没有提出我的解决方案。所以你在这里...
import re
from more_itertools import stagger
def comb_to_py(string, objects):
# Split the line
toks = split_comb_string(string)
# Escape for empty string
if toks[0] == 'none':
return []
# initialize iterator
# I could use a deque here. Let's see what works the best
iterator = stagger(toks, offsets=range(2), longest=True)
return comb_it_to_py(iterator, objects)
def split_comb_string(string):
# Add whitespaces between tokes when they could be implicit to allow string
# splitting i.e. before/after plus (+), minus and closed bracket
string = re.sub(r' ?([\+\-)]) ?', r' ', string)
# remove double spaces
string = re.sub(' +', ' ', string)
# Avoid situations as 'A1 + - 2A2' and replace them with 'A1 - 2A2'
string = re.sub(r'\+ *\-', r'-', string)
# Avoid situations as 'A1 - - 2A2' and replace them with 'A1 + 2A2'
string = re.sub(r'\- *\-', r'+', string)
# Add whitespace after "(" (we do not want to add it in front of it)
string = re.sub(r'\( ?', r'( ', string)
return string.strip().split(' ')
def comb_it_to_py(iterator, objects):
for items in iterator:
# item[0] is a case token (e.g. 1.2A3)
# This should occur only with the first element
if re.fullmatch(r'([\d.]*)([a-zA-Z(]+\d*)', items[0]) is not None:
res = parse_case(items[0], objects, iterator)
elif items[0] == ')' or items[0] is None:
return res
# plus (+)
elif items[0] == '+':
# skip one position
skip_next(iterator)
# add following item
res += parse_case(items[1], objects, iterator)
# minus (-)
elif items[0] == '-':
# skip one position
skip_next(iterator)
# add following item
res -= parse_case(items[1], objects, iterator)
else:
raise(ValueError(f'Invalid or misplaced token {items[0]}'))
return res
def parse_case(tok, objects, iterator):
# Translate a case string into an object.
# It handles also brackets as "cases" calling comb_it_to_py recursively
res = re.match(r'([\d.]*)(\S*)', tok)
if res[1] == '':
mult = 1
else:
mult = float(res[1])
if res[2] == '(':
return mult * comb_it_to_py(iterator, objects)
else:
return mult * objects[res[2]]
def skip_next(iterator):
try:
next(iterator)
except StopIteration:
pass
if __name__ == '__main__':
from numpy import isclose
def test(string, expected_result):
try:
res = comb_to_py(string, objects)
except Exception as e:
print(f"Error during test on '{string}'")
raise e
assert isclose(res.value, expected_result), f"Failed test on '{string}'"
objects = {'A1': 1, 'A2':2, 'A10':3}
test('A2', 2)
test('1.3A2', 2.6)
test('1.3A2 + 3A1', 5.6)
test('1.3A2+ 3A1', 5.6)
test('1.3A2 +3A1', 5.6)
test('1.3A2+3A1', 5.6)
test('1.3A2 - 3A1', -0.4)
test('1.3A2 -3A1', -0.4)
test('1.3A2- 3A1', -0.4)
test('1.3A2-3A1', -0.4)
test('1.3A2 + -3A1', -0.4)
test('1.3A2 +-3A1', -0.4)
test('1.3A2 - -3A1', 5.6)
test('A1 + 2(A2+A10)', 25)
test('A1 - 2(A2+A10)', -23)
test('2(A2+A10) + A1', 25)
test('2(A2+A10) - A1', 23)
test('2(A2+A10) - -A1', 25)
test('2(A2+A10) - -2A1', 26)
这段代码不仅冗长，而且非常容易破解。整个代码基于字符串的正确拆分，正则表达式部分只是为了确保字符串被正确拆分，这完全取决于字符串中空格的位置，即使 - 在这种特定语法中 - 大多数空格根本不应该被解析。
此外，此代码仍未处理 or 关键字（其中 A or B 应转换为 max(A,B) 和 to 关键字（其中 A1 to A9 应该翻译成 max([Ai for Ai in range(A1, A9)])).
问题
这是最好的方法还是对于此类任务有更可靠的方法？
备注
我看了一眼pyparsing。它看起来是一种可能性，但是，如果我理解得很好，它应该用作更强大的“行分割”，而令牌仍然必须手动一个一个地转换为操作。这是正确的吗？
正则表达式本质上不适合涉及嵌套分组括号的任务——您的伪代数语言 (PAL) 不是 regular language. An actual parser such as PyParsing (a PEG parser) 应该改用。
虽然这仍然需要将源代码转换为操作，但这可以在解析期间直接执行。
我们需要一些直接翻译成 Python 原语的语言元素：
- 数字文字，例如
1.3，如 int/float 文字或 fractions.Fraction.
- 名称引用，例如
A3，作为 objects 命名空间的键。
- 括号，例如
(...)，通过括号分组：
- 变体，例如
(1.3 or A3)，作为 max 调用。
- 名称范围，例如
A4 to A6，如 max 调用
+二元运算符，作为+二元运算符。
- 隐式乘法，如
2(...)，如2 * (...)。
这种简单的语言同样适用于转译器或解释器——没有副作用或内省，因此没有 first-class 对象、中间表示或 AST 的简单翻译就可以了。
对于转译器，我们需要将 PAL 源代码转换为 Python 源代码。我们可以使用pyparsing直接读取 PAL，然后使用parse动作emit Python.
原始表达式
最简单的情况是数字——PAL 和 Python 来源是相同的。这是查看转译的一般结构的理想选择：
import pyparsing as pp
# PAL grammar rule: one "word" of sign, digits, dot, digits
NUMBER = pp.Regex(r"-?\d+\.?\d*")
# PAL -> Python transformation: Compute appropriate Python code
@NUMBER.setParseAction
def translate(result: pp.ParseResults) -> str:
return result[0]
请注意，setParseAction 通常与 lambda 一起使用，而不是修饰 def。然而，较长的变体更容易comment/annotate。
名称引用类似于解析，但需要对 Python 进行一些小的转换。我们仍然可以使用正则表达式，因为这里也没有嵌套。所有名称都将是我们任意调用的单个全局名称空间的键 objects.
NAME = pp.Regex(r"\w+\d+")
@NAME.setParseAction
def translate(result: pp.ParseResults) -> str:
return f'objects["{result[0]}"]' # interpolate key into namespace
两个语法部分已经独立工作以进行转译。例如，NAME.parseString("A3") 提供源代码 objects["A3"].
复合表达式
与 terminal/primitive 语法表达式不同，复合表达式必须引用其他表达式，可能是它们自身（此时，正则表达式失效）。 PyParsing 使用 Forward 表达式使这变得简单——这些是稍后定义的占位符。
# placeholder for any valid PAL grammar element
EXPRESSION = pp.Forward()
没有运算符优先级，仅通过 (...) 进行分组，所有 +、or 和 to 的工作方式相似。我们选择 or 作为示范。
现在的语法变得更复杂了：我们使用pp.Suppress来匹配但丢弃了纯句法的(/)和or。我们使用 +/- 组合几个语法表达式（- 表示解析时没有替代项）。最后，我们使用前向引用 EXPRESSION 来引用每个其他 和这个 表达式。
SOME_OR = pp.Suppress("(") + EXPRESSION + pp.OneOrMore(pp.Suppress("or") - EXPRESSION) - pp.Suppress(")")
@SOME_OR.setParseAction
def translate(result: pp.ParseResults) -> str:
elements = ', '.join(result)
return f"max({elements})"
名称范围和添加的工作原理基本相同，只是分隔符和输出格式发生了变化。隐式乘法更简单，因为它仅适用于一对表达式。
此时，我们为每个 kind 语言元素都有一个转译器。可以使用相同的方法创建缺失的规则。现在，我们需要实际阅读源代码和运行转译后的代码。
我们首先将已有的部分放在一起：将所有语法元素插入到前向引用中。我们还提供了一个方便的函数来抽象掉 PyParsing。
EXPRESSION << (NAME | NUMBER | SOME_OR)
def transpile(pal: str) -> str:
"""Transpile PAL source code to Python source code"""
return EXPRESSION.parseString(pal, parseAll=True)[0]
为了 运行 一些代码，我们需要转译 PAL 代码 和 评估带有一些命名空间的 Python 代码。由于我们的语法只允许安全输入，所以我们可以直接使用eval：
def execute(pal, **objects):
"""Execute PAL source code given some object values"""
code = transpile(pal)
return eval(code, {"objects": objects})
此函数可以 运行 使用给定的 PAL 源和名称值来评估等效的 Python 值：
>>> execute("(A4 or A3 or 13)", A3=42, A4=7)
42
为了完全支持 PAL，请定义缺少的复合规则并将它们与其他规则一起添加到 EXPRESSION。
我有一个包含对象列表的字典
objects = {'A1': obj_1,
'A2': obj_2,
}
然后我有一个字符串作为
cmd = '(1.3A1 + 2(A2 + 0.7A3)) or 2(A4 to A6)'
我想将其转换为命令
max( 1.3*objects['A1'] + 2*(objects['A2'] + 0.73*objects['A3']), 2*max(objects['A4'], objects['A5'], objects['A6']))
我的尝试
由于找不到更好的选择，我开始从零开始编写解析器。
个人说明：我不认为将 150 行代码附加到 SO 问题是一个好习惯，因为这意味着 reader 应该阅读并理解它，这是一项艰巨的任务。尽管如此，我之前的问题还是被否决了，因为我没有提出我的解决方案。所以你在这里...
import re
from more_itertools import stagger
def comb_to_py(string, objects):
# Split the line
toks = split_comb_string(string)
# Escape for empty string
if toks[0] == 'none':
return []
# initialize iterator
# I could use a deque here. Let's see what works the best
iterator = stagger(toks, offsets=range(2), longest=True)
return comb_it_to_py(iterator, objects)
def split_comb_string(string):
# Add whitespaces between tokes when they could be implicit to allow string
# splitting i.e. before/after plus (+), minus and closed bracket
string = re.sub(r' ?([\+\-)]) ?', r' ', string)
# remove double spaces
string = re.sub(' +', ' ', string)
# Avoid situations as 'A1 + - 2A2' and replace them with 'A1 - 2A2'
string = re.sub(r'\+ *\-', r'-', string)
# Avoid situations as 'A1 - - 2A2' and replace them with 'A1 + 2A2'
string = re.sub(r'\- *\-', r'+', string)
# Add whitespace after "(" (we do not want to add it in front of it)
string = re.sub(r'\( ?', r'( ', string)
return string.strip().split(' ')
def comb_it_to_py(iterator, objects):
for items in iterator:
# item[0] is a case token (e.g. 1.2A3)
# This should occur only with the first element
if re.fullmatch(r'([\d.]*)([a-zA-Z(]+\d*)', items[0]) is not None:
res = parse_case(items[0], objects, iterator)
elif items[0] == ')' or items[0] is None:
return res
# plus (+)
elif items[0] == '+':
# skip one position
skip_next(iterator)
# add following item
res += parse_case(items[1], objects, iterator)
# minus (-)
elif items[0] == '-':
# skip one position
skip_next(iterator)
# add following item
res -= parse_case(items[1], objects, iterator)
else:
raise(ValueError(f'Invalid or misplaced token {items[0]}'))
return res
def parse_case(tok, objects, iterator):
# Translate a case string into an object.
# It handles also brackets as "cases" calling comb_it_to_py recursively
res = re.match(r'([\d.]*)(\S*)', tok)
if res[1] == '':
mult = 1
else:
mult = float(res[1])
if res[2] == '(':
return mult * comb_it_to_py(iterator, objects)
else:
return mult * objects[res[2]]
def skip_next(iterator):
try:
next(iterator)
except StopIteration:
pass
if __name__ == '__main__':
from numpy import isclose
def test(string, expected_result):
try:
res = comb_to_py(string, objects)
except Exception as e:
print(f"Error during test on '{string}'")
raise e
assert isclose(res.value, expected_result), f"Failed test on '{string}'"
objects = {'A1': 1, 'A2':2, 'A10':3}
test('A2', 2)
test('1.3A2', 2.6)
test('1.3A2 + 3A1', 5.6)
test('1.3A2+ 3A1', 5.6)
test('1.3A2 +3A1', 5.6)
test('1.3A2+3A1', 5.6)
test('1.3A2 - 3A1', -0.4)
test('1.3A2 -3A1', -0.4)
test('1.3A2- 3A1', -0.4)
test('1.3A2-3A1', -0.4)
test('1.3A2 + -3A1', -0.4)
test('1.3A2 +-3A1', -0.4)
test('1.3A2 - -3A1', 5.6)
test('A1 + 2(A2+A10)', 25)
test('A1 - 2(A2+A10)', -23)
test('2(A2+A10) + A1', 25)
test('2(A2+A10) - A1', 23)
test('2(A2+A10) - -A1', 25)
test('2(A2+A10) - -2A1', 26)
这段代码不仅冗长，而且非常容易破解。整个代码基于字符串的正确拆分，正则表达式部分只是为了确保字符串被正确拆分，这完全取决于字符串中空格的位置，即使 - 在这种特定语法中 - 大多数空格根本不应该被解析。
此外，此代码仍未处理 or 关键字（其中 A or B 应转换为 max(A,B) 和 to 关键字（其中 A1 to A9 应该翻译成 max([Ai for Ai in range(A1, A9)])).
问题
这是最好的方法还是对于此类任务有更可靠的方法？
备注
我看了一眼pyparsing。它看起来是一种可能性，但是，如果我理解得很好，它应该用作更强大的“行分割”，而令牌仍然必须手动一个一个地转换为操作。这是正确的吗？
正则表达式本质上不适合涉及嵌套分组括号的任务——您的伪代数语言 (PAL) 不是 regular language. An actual parser such as PyParsing (a PEG parser) 应该改用。
虽然这仍然需要将源代码转换为操作，但这可以在解析期间直接执行。
我们需要一些直接翻译成 Python 原语的语言元素：
- 数字文字，例如
1.3，如int/float文字或fractions.Fraction. - 名称引用，例如
A3，作为objects命名空间的键。 - 括号，例如
(...)，通过括号分组：- 变体，例如
(1.3 or A3)，作为max调用。 - 名称范围，例如
A4 to A6，如max调用 +二元运算符，作为+二元运算符。
- 变体，例如
- 隐式乘法，如
2(...)，如2 * (...)。
这种简单的语言同样适用于转译器或解释器——没有副作用或内省，因此没有 first-class 对象、中间表示或 AST 的简单翻译就可以了。
对于转译器，我们需要将 PAL 源代码转换为 Python 源代码。我们可以使用pyparsing直接读取 PAL，然后使用parse动作emit Python.
原始表达式
最简单的情况是数字——PAL 和 Python 来源是相同的。这是查看转译的一般结构的理想选择：
import pyparsing as pp
# PAL grammar rule: one "word" of sign, digits, dot, digits
NUMBER = pp.Regex(r"-?\d+\.?\d*")
# PAL -> Python transformation: Compute appropriate Python code
@NUMBER.setParseAction
def translate(result: pp.ParseResults) -> str:
return result[0]
请注意，setParseAction 通常与 lambda 一起使用，而不是修饰 def。然而，较长的变体更容易comment/annotate。
名称引用类似于解析，但需要对 Python 进行一些小的转换。我们仍然可以使用正则表达式，因为这里也没有嵌套。所有名称都将是我们任意调用的单个全局名称空间的键 objects.
NAME = pp.Regex(r"\w+\d+")
@NAME.setParseAction
def translate(result: pp.ParseResults) -> str:
return f'objects["{result[0]}"]' # interpolate key into namespace
两个语法部分已经独立工作以进行转译。例如，NAME.parseString("A3") 提供源代码 objects["A3"].
复合表达式
与 terminal/primitive 语法表达式不同，复合表达式必须引用其他表达式，可能是它们自身（此时，正则表达式失效）。 PyParsing 使用 Forward 表达式使这变得简单——这些是稍后定义的占位符。
# placeholder for any valid PAL grammar element
EXPRESSION = pp.Forward()
没有运算符优先级，仅通过 (...) 进行分组，所有 +、or 和 to 的工作方式相似。我们选择 or 作为示范。
现在的语法变得更复杂了：我们使用pp.Suppress来匹配但丢弃了纯句法的(/)和or。我们使用 +/- 组合几个语法表达式（- 表示解析时没有替代项）。最后，我们使用前向引用 EXPRESSION 来引用每个其他 和这个 表达式。
SOME_OR = pp.Suppress("(") + EXPRESSION + pp.OneOrMore(pp.Suppress("or") - EXPRESSION) - pp.Suppress(")")
@SOME_OR.setParseAction
def translate(result: pp.ParseResults) -> str:
elements = ', '.join(result)
return f"max({elements})"
名称范围和添加的工作原理基本相同，只是分隔符和输出格式发生了变化。隐式乘法更简单，因为它仅适用于一对表达式。
此时，我们为每个 kind 语言元素都有一个转译器。可以使用相同的方法创建缺失的规则。现在，我们需要实际阅读源代码和运行转译后的代码。
我们首先将已有的部分放在一起：将所有语法元素插入到前向引用中。我们还提供了一个方便的函数来抽象掉 PyParsing。
EXPRESSION << (NAME | NUMBER | SOME_OR)
def transpile(pal: str) -> str:
"""Transpile PAL source code to Python source code"""
return EXPRESSION.parseString(pal, parseAll=True)[0]
为了 运行 一些代码，我们需要转译 PAL 代码 和 评估带有一些命名空间的 Python 代码。由于我们的语法只允许安全输入，所以我们可以直接使用eval：
def execute(pal, **objects):
"""Execute PAL source code given some object values"""
code = transpile(pal)
return eval(code, {"objects": objects})
此函数可以 运行 使用给定的 PAL 源和名称值来评估等效的 Python 值：
>>> execute("(A4 or A3 or 13)", A3=42, A4=7)
42
为了完全支持 PAL，请定义缺少的复合规则并将它们与其他规则一起添加到 EXPRESSION。