为什么我的 PLY 解析器没有正确地将任何树节点分组在一起？

Question

我正在尝试在 Python 中构建一个 CAS，目前我坚持执行解析器，我将使用它从表达式字符串转到我最终可以操作和简化的 Anytree 树。问题似乎是，在解析时，yacc 没有使用我的解析器语法规范中定义的正确子节点来实现我的 GROUP 节点。我试过弄乱优先级和关联性，改变语法规则的顺序，但似乎没有什么能使它正确地成为节点的父节点。更奇怪的是，在 debug/verbose 模式下，它在模式匹配时为表达式创建一个节点，但它（出于某种原因）在识别时无法将它作为 GROUP 节点的父节点一个 LPAREN expression RPAREN 令牌

这是我的代码：

import ply.yacc as yacc
from anytree import Node, RenderTree
import ply.lex as lex

#init token names
tokens = (
    'INTEGER',
    'PLUS',
    'MINUS',
    'TIMES',
    'DIVIDE',
    'LPAREN',
    'RPAREN',
)

#init regex rules for said tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'

#init regex rule/function for integers
def t_INTEGER(t):
    r'\d+'
    t.value = int(t.value)
    return t

#ignoring whitespace
t_ignore = '\t'

#handling unknown characters (%s inserts whatever is past the second %)
def t_error(t):
    print("Illegal character '%s'" %t.value[0] )
    t.lexer.skip(1)

#building the lexer
lexer = lex.lex()


#parser grammar spec

#binary operators
def p_expression_binop(p):
    '''expression : expression PLUS expression
                  | expression MINUS expression
                  | expression TIMES expression
                  | expression DIVIDE expression '''
    p[0] = Node(p[2],children = [Node(p[1]),Node(p[3])])

#brackets/grouping
def p_expression_group(p):
    'expression : LPAREN expression RPAREN'
    p[0] = Node(p[1], children = [Node(p[2])])

#integers
def p_expression_number(p):
    'expression : INTEGER'
    p[0] = Node(p[1])


def p_error(p):
    print("Input syntax error ")

treeParser = yacc.yacc()

while True:
    try:
        s = input("Calculate this >")
    except EOFError:
        break
    if not s: break
    ParsTree = treeParser.parse(s)
    print(RenderTree(ParsTree))

示例输入：(2)+(2)

示例输出：

Calculate this >(2)+(2)
Node('/+')
├── Node("/+/Node('/GROUP')")
└── Node("/+/Node('/GROUP')")

如您所见，它仅创建 GROUP 个节点，并且不会在所述 GROUP 个节点下创建任何子整数节点

编辑：使代码独立并添加示例输入和输出以更好地解释问题

Answer 1

Node 的第一个参数应该是一个字符串。（事实上，它应该是一个标记节点的字符串，但我会在一分钟内回到它。）如果它不是一个字符串，它将被转换为一个。

考虑一下你的行动：

p[0] = Node(p[2],children = [Node(p[1]),Node(p[3])])

这里，p[2]是一个token，它的值是一个字符串（例子中的+）。但是p[1]和p[3]都是expression，表达式的值是Node，不是字符串。所以anytree将其转为字符串，如'Node("\GROUP")'.

实际上，当我尝试您粘贴的代码时，结果是 'Node("/(")'，因为 p_expression_group 的操作是：

p[0] = Node(p[1], children = [Node(p[2])])

我想在您的代码中运行，与您粘贴到问题中的代码不同，该规则为：

p[0] = Node("GROUP", children = [Node(p[2])])

或者您可能对 \( 有不同的词法作用。作为旁注，请始终验证您粘贴到问题中的相同输出确实是您粘贴的代码的输出，而不是相同代码的其他版本的输出，即使它们非常相似，以避免混淆.

所以解决方案是不要对已经 Nodes 的事物调用 Node。我把两个相关动作改成如下：

#binary operators
def p_expression_binop(p):
    '''expression : expression PLUS expression
                  | expression MINUS expression
                  | expression TIMES expression
                  | expression DIVIDE expression '''
    p[0] = Node(p[2],children = [p[1], p[3]])  # Removed Node calls

#brackets/grouping
def p_expression_group(p):
    'expression : LPAREN expression RPAREN'
    p[0] = Node(p[1], children = [p[2]])       # Removed Node call

然后得到“预期”的结果：

$ python3 parser.py<<<'(2)+(2)'
Generating LALR tables
WARNING: 16 shift/reduce conflicts
Calculate this >Node('/2')
Node('/2')
Node('/+')
├── Node('/+/(')
│   └── Node('/+/(/2')
└── Node('/+/(')
    └── Node('/+/(/2')

你可以在这里看到 anytree 对如何呈现节点的标签有自己的想法：它从父节点 g运行dparent 等生成标签的“路径” . 节点，使用 / 作为路径分隔符。这肯定会掩盖您对标签的使用，标签实际上是一个运算符名称或一个值。 AST 节点没有真正需要具有唯一的人类可读标签，这似乎是 anytree 模型。如果您想继续使用 anytree，您应该考虑添加其他属性，也许是一个 nodetype 属性和一个 value 或 operator 属性，以便您可以使用标签字段作为标签（如果你发现标签对某些东西很方便）。

另一方面，您可能会在较长的运行中发现 anytree 不适合您解析问题。（有父节点的树有很多奇怪的地方。例如，你只能把一个节点放在一个地方，所以你不能在不同的树之间共享它，或者在同一棵树中放置多个实例。所有这些用例将需要显式节点副本。）

为什么我的 PLY 解析器没有正确地将任何树节点分组在一起？

Why is my PLY parser not grouping anytree nodes together properly?

python

parsing

ply

anytree