遞歸下降解析器容易獲得解釋

Question

有人可以用簡單的術語解釋我的遞歸下降解析器是什麼？

我被困在試圖得到它。這在wikipedia中解釋得非常模糊。

遞歸下降解析器是一種自頂向下的解析器，構建爲一組遞歸過程，每個過程都實現語法的生成規則。

那麼，我能理解它嗎？解析器是一個按預定義順序逐一執行命令的程序，每次執行命令時都具有相同的含義，但它會根據輸入以某種方式調整輸出，這意味着每次輸入時調整可能會不同被改變。

而我仍然不明白爲什麼在這裏使用遞歸這個詞。

Answer 1

首先，一堆術語。

A 解析器是一種軟件，它可以根據某些語法檢查文本輸入在語法上是否正確。解析器也可能將文本輸入轉換爲另一種表示，這對其他軟件來說更容易使用。

A 語法是一種語言的語法定義。 A language是一組（可能是無限的）所有句法上正確的「句子」。句子是一系列符號。

語法是用一組產品來描述的。 製作是規則，告訴你如何可以替代符號序列與符號

的其他序列現在我們可以讓這個更具體的一個例子：平衡括號的所有可能的序列的簡單的語言。例如，字符串「（）」將是該語言的成員，「（）（）（）」和「（（（）））」也是。我們的語言不會包含一串不平衡的括號：「（」和「（））」不是我們語言的一部分。

此語言語法可以寫成如下：

S ::= "" 
S ::= '(' S ')' S 

這裏，S是非末端符號，並且具體地，起始碼元。每一行表示語法中的一個生產。更有趣的語言有更多的非終端符號和更多的作品。

如果您希望爲我們的語言生成有效的字符串，請以字符串S開頭，然後迭代應用生產規則以用新序列替換字符串中的任何非終端符號。

所以我們從S開始，並選擇其中一個生產規則來應用。假設我們選擇第二個，我們得到(S) S。由於字符串中仍然有非終端，所以我們必須繼續。如果我們再次用第二條規則替換第一條S，我們得到((S) S) S。現在讓我們開始選擇第一條規則，其中說我們可以用空字符串替代S。 （我把它寫成""，但有時候你會看到人們爲此使用了希臘字母epsilon。）如果我們將此規則應用於字符串中所有剩餘的S es，我們最終將得到(())，這是該語言中的有效序列。

好的，但現在我們想走另一條路。我們得到一個字符串作爲輸入，並想知道它是否屬於該語言。這是解析器的工作。

對於很多（但不是全部）語法，您可以使用一種稱爲遞歸下降解析器的特定樣式的解析器實現。基本思想是編寫與語法中的產品相對應的函數。每個函數都可以調用其他函數來檢查子字符串。他們甚至可以自稱（這是「遞歸」起作用的地方）。

讓我們重新寫我們的語法有點不同：

S ::= '(' P | "" 
P ::= S ')' S 

豎線表示「或」。所以S可以用空字符串替換爲(P或。

現在假設我們寫了兩個函數ParseS和ParseP。這些函數可以看到輸入字符串的其餘部分，如果字符串的下一位與相應的生產相匹配，則返回true。在僞代碼：

bool ParseS() { 
    if next character is '(' { 
    skip the `(` 
    return ParseP() 
    } 
    return true; // handles the empty string 
} 

bool ParseP() { 
    if ParseS() and the next character is `)` { 
    skip the ')' 
    return ParseS(); 
    } 
    return false; 
} 

總之，這些功能構成了我們的語言遞歸下降解析器[*]他們告訴我們輸入的字符串是否是由語法定義的語言，這是基本的定義。解析器。它是遞歸的，因爲ParseS可以調用ParseP，它可以調用ParseS。

[*]好吧，差不多。它實際上有點過於簡化了。一個正確的解析器會在返回最終真值之前檢查以確保沒有更多輸入。正如所寫的，這個接受任何字符串的前綴是該語言的成員。這在實踐中很容易解決，但它會將分散注意力的細節引入已經太長的答案中。