這些模式可以通過正則表達式或上下文無關語法來匹配嗎？

Question

這是編譯器的練習。我們問，如果有可能，以配合正則表達式或上下文無關文法以下模式：

1. N「a」後跟N「B」，像「AABB」
2. 迴文，像「abbccbba」
3. N '一'，則n 'b'，則n 'C'，像 '爲aabbcc'

注意，N可以是任何正整數。 （否則它太簡單了）

只有3個字符'abc'可以出現在文本中解析。

我很困惑，因爲據我所知，這些模式中的非模式可以用正則表達式和上下文無關文法來描述。

Answer 1

關鍵的問題是：有多少和什麼樣的內存你需要？

在問題1的情況下，您需要以某種方式跟蹤a終端的數量，因爲您正在解析b終端。既然你知道你需要一對一，堆棧顯然是足夠的（你可以把a放在堆棧上，每彈出一個b）。由於下推自動機相當於表現力的CFG，因此您可以爲問題1創建CFG。

對於問題2，PDA在問題1中使用的技術應該暗示您可以使用某種技術用於問題2.PDA可以構建輸入的前半部分的堆棧，然後在其反向進入時彈出它。

在問題3的情況下，如果使用堆棧技術來計數a終端和b終端，這一切都很好，但是堆棧內存發生了什麼變化？足夠了嗎？不，你需要在其他地方存儲a的數量，所以CFG不能表達這種語法。

Answer 2

這裏有一個簡單的CFG的問題2（它證明了一個空的輸入，但你的想法）嘗試：

S -> a S a 
S -> b S b 
S -> c S c 
S -> ɛ