使用EBNF或BNF編寫遞歸下降解析器會更容易嗎？

Question

我有一個語法的BNF和EBNF。 BNF顯然比較冗長。就使用BNF構建遞歸下降解析器而言，我有一個相當不錯的主意;有很多這方面的資源。我無法找到資源將EBNF轉換爲遞歸下降解析器。這是因爲它更難嗎？我回想起我的CS理論課，我們討論了EBNF，但我們沒有將它們轉換成遞歸下降解析器。我們做去BNF的轉換爲遞歸下降解析器。

我問的原因是因爲EBNF更緊湊。

從查看EBNF的一般情況來看，我注意到在{和}之間的術語可以轉換爲while循環。還有其他的指導方針或規則嗎？

Answer 1

兩者都不比其他更難。迭代實現和遞歸實現的區別實際上是不同的。在BNF中，一切都是遞歸的。在EBNF中，一些遞歸是迭代表達的。 EBNF語法有不同的變化，所以我只會使用英語......「零個或多個」是一個簡單的while循環，就像你發現的那樣。 「一個或多個」與「零個或多個」後跟一個相同。 「零次或一次」是一個簡單的if語句。這應該涵蓋大部分情況。

Answer 2

您應該調查所謂的metacompilers，它實質上是將EBNF編譯爲遞歸下降解析器。他們如何做到這一點正是你的問題的答案。 （它很漂亮，但很好理解細節）。

一篇非常精彩的論文是Val Schorre的「MetaII」論文。這是從誠實到神的1964年的元編譯器技術。在10頁中，他向您展示瞭如何構建一個meta編譯器，並且提供了不僅如此，而且還提供了另一個編譯器以及兩者的輸出！有一個驚人的時刻，如果你去構建其中一個，你會發現如何使用自己的語法編譯自己的元編譯器。這一刻讓我想起了1970年代當我第一次翻閱這篇論文的時候，編譯器已經迷上了編譯器。這是那些計算機科學論文之一，每個人在軟件業務應該閱讀。

James Neighbors（軟件工程中術語「域」的發明者，以及第一個程序轉換系統的構建者[基於這些元編譯器]有一個偉大的在線MetaII tutorial，對於那些不想做的人-IT-從劃傷的經驗。（我什麼都沒有做這個，除了鄰居和我在大學時）。

這兩種方法都瞭解從EBNF metacompilers和生成語法分析器的好方法。

關鍵的想法是，規則的左側創建一個函數來分析非終結符，如果匹配並推進輸入流，則返回true;如果不匹配，則返回false並且輸入流不前進。 該功能的內容由右側確定。文字標記直接匹配。 非終結者會調用爲其他規則生成的其他函數。 Kleene *映射到while循環，變換映射到條件分支。 EBNF沒有解決的問題是， 和元編譯器是做什麼的，除了說「匹配」還是沒有，解析是如何做的？ 祕訣在於將輸出操作編織到EBNF中。 MetaII紙使所有這些晶瑩剔透。

Answer 3

早期的meta編譯器META II和TREEMETA及其親屬並不完全是遞歸體面的解析器。他們被描述爲使用遞歸函數。這意味着他們可以稱他們爲自己。

我們不稱C爲遞歸語言。 C或C++函數是遞歸的，就像早期的元編譯器遞歸一樣。

可以使用遞歸。他們是編程語言。遞歸通常只在分析nexted語言結構時使用。例如加括號的表達式和nexted塊。

更多的LR遞歸體面組合。 CWIC最後記錄的一個有廣泛的回溯和展望功能。 ' - '不是操作符可以匹配任何語言結構。並將其倒置成功或失敗。例如，如果一個術語匹配，則該術語失敗。輸入永遠不會提前。 '？'向前看並匹配任何語言結構？例如，expr會嘗試解析expr。展望未來'？'匹配的結構不被保留或者是輸入先進的。