在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]

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

1. 我没有看到ACTION节点的意义，所以我只是在最后一条规则中传递语句本身。由于actions仅由ACTIONs组成，因此将列表中的每个元素标记为ACTION似乎是多余的。但如果你愿意，你可以放ACTION。)

2. 在上面的代码中，ACTIONS节点是一个列表，而不是元组；CCD_ 11函数故意不在每次添加新项目时创建新列表。这通常很好，并且节省了一堆元组创建和垃圾收集。它假设传递的值没有在其他地方使用，这里当然是这样，但可能并不总是正确的。然而，如果你真的想要元组，那不是问题：

   def p_actions(p):
   """actions : actions action"""
   p[0] = p[1] + (p[2],)
   

3. 请注意，没有必要将非终端的所有产品都放在同一个解析函数中。如果生产的操作相同，则可以将其分组为函数。总的来说，如果您发现自己试图弄清楚是哪种生产导致了动作函数被触发(例如，if len(p) == 3)，那么您可能需要考虑将生产划分为两个不同的函数，每个函数都有一个非条件动作。