語法的正則表達式

Question

我正在閱讀有限自動機&語法來自Aho的編譯器構造，並且我被這種語法困住了這麼久。我沒有的我該怎麼形容它一個明確的看法：

考慮下面的語法：

的S - >（L）|一個L - > L，S | S

請注意，圓括號和逗號實際上是此 語言中的終端，並出現在此語法接受的語句中。嘗試 描述由此語法生成的語言。這是語法 含糊不清？

我在這裏關心的是：這個語法生成的語言可以被描述爲正則表達式嗎？我很困惑如何去做。任何幫助？

Answer 1

爲了顯示語法不明確，您需要能夠在解析相同的字符串時構造兩個不同的分析樹。您的字符串將由「（」，「）」，「，」和「a」組成，因爲這些是語法中唯一的終端符號。

嘗試用幾種方法安排這4個終端符號，並看看您是否能夠以example ambiguous grammar on Wikipedia的精神展示不同的成功解析。

立即左遞歸往往會導致一些解析器出現問題。看看「一，一，一個」不上什麼有趣的東西「L → L，S | S」 ...

我這裏關注的是這個語法是正則表達式生成的語言能不能描述...我很困惑怎麼辦

正則表達式不能完全描述語法。重寫語法的一部分將使這一更加明顯：

1. 小號→（L）
2. 小號→一個
3. 大號→ L，S
4. 大號→小號

注意＃1和＃4。 L可以產生S，S可以產生（L）。這意味着S可以產生（S），它可以產生（（S）），（（（S）））等。關鍵是那些括號是匹配的;有相同數量的「（」符號作爲「）」符號。

正則表達式不能這樣做。

正則表達式映射到有窮自動機。有限自動機不能計數。 A語言L ∈ {w：0 ^{n n}}不是常規的。 L ∈ {w：（ⁿ）ⁿ}，對於「1」僅僅是「（」代表「0」和「）」的替代品，也不是。請參閱：Regular Languages - Wikipedia下的第一個示例部分。 （符號注：■是S，S 是SS，...，S ^ñ是S重複n次。）

這意味着你不能使用正則表達式來描述部分的語言。這使其處於CFG，圖靈機和下推自動機的領域。

Answer 2

正則表達式（和解釋它們的庫）是識別上下文無關語法句子的一個糟糕工具。相反，你會想使用像yacc，bison或ANTLR這樣的解析器生成器。

我認爲Aho書中練習的要點是用文字描述語言，以便理解它是否含糊。一種方法來處理它：你能設計一個語法句子，可以用兩種不同的方式解析，給定語法的產生嗎？如果是這樣，語法是不明確的。