具有縮進和回溯的遞歸下降解析器

Question

我一直在試圖找到一種遞歸下降解析器算法，該算法也適用於帶回溯的縮進。 但我一直讓自己找到這個麻煩的解決方案。

是否有任何資源可以處理縮進？

感謝

Answer 1

根據您的問題，我假設你正在寫自己的遞歸下降解析器的壓痕敏感的語言。

之前我已經嘗試過使用基於縮進的語言，並且我通過保持跟蹤當前縮進級別的狀態和兩個與縮進匹配的不同終端來解決問題。它們都匹配縮進單位（比如兩個空格或一個製表符）並對它們進行計數。我們調用匹配的縮進級別matched_indentation和當前縮進級別expected_indentation。

對於第一個，我們稱之爲indent：

• 如果matched_indentation < expected_indentation，這是一個dedent，而比賽是失敗的。
• if matched_indentation == expected_indentation，這場比賽是成功的。匹配器消耗縮進。
• 如果matched_indentation > expected_indentation，你有一個語法錯誤（從無處縮進的縮進），並應該像這樣處理它（拋出一個異常或其他東西）。

對於第二個，我們稱之爲dedent：

• 如果matched_indentation < expected_indentation，匹配成功。您將expected_indentation減1，但不會消耗輸入。這樣可以鏈接多個dedent終端以關閉多個範圍。

• 如果matched_indentation == expected_indentation，匹配成功，並且這次你消耗輸入（這是最後的dedent終端，所有範圍都關閉）。

  如果matched_indentation > expected_indentation，匹配只是失敗，您在這裏沒有dedent。

這些端子和非終端之後你希望增加縮進應該由一個增加expected_indentation。

比方說，要實現一個Python類if語句（我將使用EBNF般的符號），它會是這個樣子：

indented_statement : indent statement newline;  

if_statement : 'if' condition ':' newline indented_statement+ dedent ; 

現在讓我們來看看下面的一段碼，也假設一個if_statement是你statement規則的一部分：

1|if cond1:     <- expected_indentation = 0, matched_indentation = 0 
2| if cond2:    <- expected_indentation = 1, matched_indentation = 1 
3| statement1   <- expected_indentation = 2, matched_indentation = 2 
4| statement2   <- expected_indentation = 2, matched_indentation = 2 
5|       <- expected_indentation = 2, matched_indentation = 0 

• 在第一次四行，你會成功匹配indent終端
• 就上線，你會在那裏你把你的indent和dedent終端匹配兩個dedent終端，關閉這兩個範圍，並導致與expected_indentation = 0

有一件事你應該小心的是。在這種情況下，我們不需要if_statement規則中的一個規則，因爲它是statement，而indented_statement已經期望有一個縮進。

還要介意你如何對待換行符。一種選擇是將它們作爲一種語句終結符來使用，另一種是讓它們先於縮進，所以選擇最適合您的語言。