CFG生產規則在代碼中的外觀如何？

那裏有這麼多的信息，但這不是真的有助於像我這樣的noob。我閱讀了許多關於上下文無關語言和下推自動化的文章。現在我試圖瞭解代碼中可能會看到某些東西。CFG生產規則在代碼中的外觀如何？

讓我們假設我們定義的語言，如：

L = {am bn | m >= n}

給我們以下的生產規則：

S -> B |^
B -> aBb | A 
A -> aA | a

正是這將如何看起來像僞代碼？我假定所有的生產規則都是1狀態定義爲S1或者都是單獨的狀態？無論哪種方式，我不知道，如果有人能幫助我理解這是如何工作的，這將是非常好的。

我知道我們分析了一個輸入的字符，並且取決於輸入的是什麼輸入，其中一個規則適用於將一個符號推入我們的PDA堆棧。

來源

2017-03-22 Asperger

什麼，具體來說，你想要你的代碼嗎？請明確點。 CFG描述語言。你想讓你的代碼輸出分析樹嗎？你想讓你的代碼識別語言中的字符串嗎？或者生成它們？如果生成它們，哪些？你沒有時間全部生成它們。 – Patrick87

您的生產規則僅生成m> n的字符串，這種平等是不可能的。正如帕特里克所說，如果你想要一個算法，你應該明確指出哪個問題。 –

@PeterLeupold好的我今天會更新我的問題。你是對的，很多信息都不見了，我會編輯我的例子。 – Asperger

有多種方法可以將CFG轉換爲實際解析的代碼片段，每種方法都有其優點和缺點。一些算法，如CYK算法，Unger算法和（我個人最喜歡的）Earley算法可以將任意CFG和一個字符串作爲輸入，然後使用動態編程爲該字符串確定一個分析樹（如果存在的話）。這些算法的操作與典型的下推自動機不相似，因爲它們一次處理一個字符時填寫值表。

一些解析算法，特別是LR（1）和LR解析器的一般系列，更直接地維護解析堆棧並使用有限狀態控制來驅動解析器。儘管LR（1）解析器不能處理所有可能的CFG，但它們只能處理確定性的CFG - 但像GLR解析器這樣的變體可以通過並行地運行多個堆棧來處理所有語法。編譯器生成工具bison和yacc在這個系列中生成解析器，如果你看看它們的輸入文件是如何工作的，你就會了解CFG是如何在軟件中編碼的。（1）解析器和簡單的回溯解析器自頂而下工作，通常使用堆棧（通常是運行時調用堆棧）解析輸入字符串。儘管如此，他們無法處理所有語法。 ANTLR解析器生成器在該系列中生成解析器。

Packrat解析器通過使用修改的CFG來編碼，該編碼使用什麼樣的順序來編碼優先級。使用這些解析器的代碼傾向於密切地反映語法的形狀。解析器組合器是另一種現代技術，解析邏輯看起來很像CFG。

如果您有興趣瞭解更多信息，我會建議您參加一個編譯器課程或者獲取Grune和Jacobs的「解析技巧：實用指南」的副本。

來源

2017-08-29 15:49:33 templatetypedef

CFG生產規則在代碼中的外觀如何？

回答

相關問題