在 PLY Python 3 中循环解析步骤

Question

我目前正在使用 python 3 来解析我正在制作的编程语言。我想知道如何使解析规则循环。

这可能不清楚，所以这里有一个例子。

我有代码：

def c_parse():
    def p_program(p):
        "program : actions"
        p[0] = ("PROGRAM", p[1])

    def p_actions(p):
        """actions : action
                   | actions action"""
        if len(p) == 3:
            p[0] = ("ACTIONS", p[1], p[2])
        elif len(p) == 2:
            p[0] = ("ACTION", p[1])

    def p_action(p):
        """action : function_call ';'
                  | variable_dec ';'
                  | if_statement ';'"""
        p[0] = ("ACTION_STATEMENT", p[1])

    ...

给定输入：

x = "HELLO WORLD";
print(x);
print(x);

这会输出这个 AST：

('PROGRAM', ('ACTIONS', ('ACTIONS', ('ACTION', ('ACTION_STATEMENT', 
('VARIABLE_DEC', ... ))), 
('ACTION_STATEMENT', ('FUNCTION_CALL', ... ))), ('ACTION_STATEMENT', 
('FUNCTION_CALL', ... ))))

注意 ACTIONS 和 ACTION_STATEMENT 是多么的混乱。这是因为 p_actions() 函数中定义的递归规则。有没有办法让我像这样得到一个漂亮干净的 AST：

(PROGRAM, (ACTION, (VARIABLE_DEC, ... )), (ACTION, (FUNCTION_CALL, ... )),
(ACTION, (FUNCTION_CALL, ...)))

换句话说，我可以让 p_actions() 函数能够在不使用递归的情况下解析无限数量的 ACTION 节点吗？这可能吗？

顺便说一句，如果重要的话，我正在使用 macOS。

Answer 1

如果您使用的是上下文无关文法，则不使用递归就无法解析无限长度的输入，因为递归是您在上下文无关文法中表示无限重复的方式。这会影响正式语法树，但绝对没有理由让您的抽象语法树 (AST) 需要保留解析的每个细节。

AST 之所以被称为抽象，正是因为它抽象掉了一些对语义分析不是很有用的语法细节。您可以按照自己喜欢的任何方式自由创建 AST；没有任意规则。（有一个启发式：AST 应该保留对您有用的解析树的那些特征，仅此而已。）

从 AST 中删除单元产生式特别常见。（单元产生式是右侧仅由单个非终结符组成的产生式，例如 actions: action）当它们不添加任何有用信息时。有时，右侧只有一个非终结符的产生式将从 AST 中删除，即使严格来说它不是单元规则。这将取决于产生式是否具有语义意义。例如，expression: '(' expression ')' 可能会被省略，尽管 expression: '-' expression 不是。

在 Ply 术语中，省略产生式只是简单地传递右侧的值。例如，您可能有：

def unit_rule(p):
  """actions : action
     program : actions
  """
  p[0] = p[1]   # Pass through the non-terminal's value

def parens(p):
  """expr : LPAREN expr RPAREN"""
  p[0] = p[2]   # Pass through the non-terminal's value

您也不仅限于创建忠实模仿语法结构的语法节点。如果你想让一个列表在 AST 中表示为一个列表，那很好。 Python 的 append 操作对此非常有用。

因此，获得您似乎想要的 AST 的一种可能方法是：

start = 'program'

def p_actions(p):
    """actions : actions action"""
    p[1].append(p[2])
    p[0] = p[1]       

def p_actions1(p):
    """actions : action"""
    p[0] = ["ACTIONS", p[1]]

def p_unit(p):
    """program : actions"
       action  : function_call ';'
               | variable_dec ';'
               | if_statement ';'
    """
    p[0] = p[1]

关于上述代码的一些注意事项：

我没有看到 ACTION 个节点的意义，所以我只是在最后一条规则中通过了语句本身。由于 actions 仅由 ACTION 组成，因此将列表中的每个元素标记为 ACTION 似乎是多余的。但如果你愿意，你可以输入 ACTION。）
在上面的代码中，一个ACTIONS节点是一个列表，而不是一个元组； p_actions 函数故意不在每次添加新项目时都创建新列表。这通常很好，并且节省了一堆元组创建和垃圾收集。它假定传递的值未在其他任何地方使用，这里确实是这种情况，但可能并不总是如此。然而，如果你真的想要元组，那不是问题：
```
def p_actions(p):
    """actions : actions action"""
    p[0] = p[1] + (p[2],)
```
请注意，不必将非终结符的所有产生式都放在同一个解析函数中。如果产生式的动作相同，则可以将它们分组为函数。总的来说，如果您发现自己试图弄清楚是哪个产生式导致动作函数被触发（例如 if len(p) == 3），那么您可能需要考虑将产生式分成两个不同的函数，每个函数有一个无条件的动作。

在 PLY Python 3 中循环解析步骤

Looping a Parsing Step in PLY Python 3

parsing

ply

python-3.x