我正在為簡化的 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;
如何消除回溯領先的公共前綴"int"的program的所有樹的部分？我未能使用左因子分解來做到這一點。
uj5u.com熱心網友回復：
以下稍微有點反常的語法有效（我認為），但需要旋轉生成的決議樹，以便將型別和名稱與其對應的定義相關聯。（這類似于從代數運算式語法糾正決議樹所需的操作。）這里作業的基本原則是正則運算式(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];
要解決的主要并發癥是不必要的（恕我直言）堅持特定的宣告順序。相反，如果您允許自由散布宣告，那么您的任務會容易得多；您可以按照@500 - Internal Server Error的答案進行簡單的左因子分解，這不需要重新調整決議樹。這實質上是 C 標準中語法中使用的策略。
如果您堅持排序約束，則可以在關聯的語意操作中進行檢查，而不是依靠語法來拒絕不需要的宣告順序。這也將允許您發布更多資訊豐富的錯誤訊息。（“變數必須在函式之前宣告”而不是“意外的‘=’”。）
以上都與撰寫遞回下降決議器無關，除非您堅持遞回下降決議器嚴格遵循語法（可能是因為它是從語法中機器生成的）。
一個簡單的遞回下降決議器可能看起來像這樣（在最近的 Python 版本中，使用所謂的 walrus operator :=）。我使用的約定是，語法符號（終端或非終端）的決議函式要么在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
uj5u.com熱心網友回復：
如何消除程式所有樹部分的回溯引導公共前綴“int”？
唯一的方法是將公共前綴提升到共享產品中。順便說一句，我認為您不會讓決議器區分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眾所周知，家庭語法很難自上而下地決議。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/335603.html
下一篇：聚乙二醇|在決議器中實作變數