如何消除像{a, b}， a, c这样的代码中导致回溯的通用前缀?

Question

我正在为简化的C语言编写递归解析器。我遇到的第一个规则(在EBNF中，非常简化)是

program = {declaration}, {function_definition}, main_function_definition;
declaration = "int", identifier, ["=", init_value], ";";
function_definition = "int", identifier, "(", [formal_params], ")", block;
main_function_definition = "int", "main", "(", ")", block;

如何消除program的所有树部分的向后引导的公共前缀"int"?

Answer 1

下面的语法稍微有点反常(我认为)，但是生成的解析树需要旋转，以便将类型和名称与其相应的定义关联起来。(这类似于从代数表达式语法中纠正解析树所需要做的事情。)这里的基本原理是正则表达式(a b)* a c可以重写为a (b a)* c，这实际上是一种左因式分解。在此语法中，该转换有效地完成了两次，并对main:

进行了小调整。

program = "int", [decls], "main", "(", ")", body;
decls = identifier, {var-decl}, {func-decl};
func-decl = "(", ")", [formal-params], body, "int", [identifier];
var-decl = ["=", expr], ";", "int", [identifier];

要解决的主要复杂性是不必要的(IMHO)坚持特定的声明顺序。如果您允许声明自由地穿插，您的任务会容易得多;您可以做一个简单的左分解，就像@500 - Internal Server Error的答案一样，它不需要重新调整解析树。这实际上是C标准语法中使用的策略。

如果坚持排序约束，则可以在相关的语义操作中执行检查，而不是依赖语法来拒绝不希望的声明顺序。这还允许您发出更多信息丰富的错误消息。变量必须在函数之前声明。而不是"Unexpected '='")

以上内容都与编写递归下降解析器无关，除非你坚持递归下降解析器严格遵循语法(可能是因为它是由语法机器生成的)。

一个简单的递归下降解析器可能看起来像这样(在最近的Python版本中，带有所谓的海象操作符:=)。我使用这样的约定:语法符号(终端或非终端)的解析函数要么在不使用输入的情况下返回False，要么返回与该符号相关的语义值，该值不能是False。

def parse_program():
defs = []
if not typ := parse_type():
return False
if not id := parse_IDENTIFIER():
return parse_main(defs, typ)
while True:
if parse_EQUAL():
if not value := parse_expression():
# Signal error
if not parse_SEMI():
# Signal error
defs.append(make_var(id, typ, value))
elif parse_SEMI():
defs.append(make_var(id, typ, UNINITIALISED))
else:
break
if not typ := parse_type():
# signal error
if not id := parse_IDENTIFIER():
return parse_main(defs, typ)
# Now expecting only function definitions
while parse_OPEN_PAREN():
params = parse_identifier_list()
if not params:
params = []
if not parse_CLOSE_PAREN():
# signal error
if not body := parse_body():
# signal error
defs.append(make_function(id, typ, params, body))
if not typ := parse_type():
# signal error
if not id := parse_IDENTIFIER():
return parse_main(defs, typ)
# If we get here, main wasn't detected
# Signal error

def parse_main(defs, typ):
if not parse_MAIN():
return False
if not parse_OPEN():
# Signal error
if not parse_CLOSE():
# Signal error
if not body := parse_body():
# Signal error
if typ != TYPE_INT:
# Signal error
defs.append(make_main_function(body))
return defs

Answer 2

如何消除回溯引导的通用前缀" into "程序的所有树形部分?

唯一的方法是将公共前缀提升到共享的产品中。顺便说一句，我不认为您会让解析器区分main和任何其他函数声明—这可以在语义分析阶段完成，因此您可以将其取出，这样做:

program = {declaration}, function_definition, {function_definition};
decl_or_funcdef_prefix = "int", identifier;
declaration =  decl_or_funcdef_prefix, ["=", init_value], ";";
function_definition = decl_or_funcdef_prefix, "(", [formal_params], ")", block;

当然，对于一个现实的语法来说，这可能很快就会变得混乱——c系列语法是出了名的难以自顶向下解析的。