0

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

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

4

1 回答 1

0

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

所以考虑你的行动：

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

这里，p[2]是一个标记，其值为字符串（+在示例中为 ）。但是p[1]andp[3]都是expression，并且表达式的值是 a 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])])

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

所以解决方案是不要调用Node已经存在的东西Nodes。我将两个相关操作更改如下：

#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它对如何呈现节点的标签有自己的想法：它从节点的父级、祖父级等生成标签的“路径”，/用作路径分隔符。这肯定会掩盖您对标签的使用，它实际上是一个运算符名称或一个值。AST 节点没有真正需要具有唯一的人类可读标签，这似乎是 anytree 模型。如果你想继续使用anytree，你应该考虑添加其他属性，也许是一个nodetype属性和一个value或operator属性，这样你就可以将标签字段用作标签（以防你发现标签方便一些东西）。

另一方面，从长远来看，您可能会发现它anytree不适合您的解析问题。（带有父节点的树有许多奇怪之处。例如，您只能将一个节点放在一个地方，因此您不能在不同的树之间共享它，或者在同一棵树中放置多个实例。所有这些用例将需要显式节点副本。）

于 2021-08-04T20:12:19.373 回答