昨天和Sumtec談到自動機和語法分析，一下子腦子有點混亂，把一些概念搞混了，看了半天清華的編譯書也沒有整明白...今天早上起來看了《離散數學及其應用》里的自動機一部分，才厘清了頭緒。還是外國人的書講得清楚一點。

昨天主要是把NFA和語法分析中的LL(1) LR(1)搞混了。事實上LL(1)分析也好LR(1)分析也好，使用的是一個基于下推自動機的計算模型，而不是有限自動機。下推自動機的計算能力要比有限自動機強。

其次就是NFA和DFA的計算能力確實是等價的，也就是對于任意一個NFA都可以找到一個與之等價的DFA(可以使用子集法來構造這樣一個DFA)。

為了說明有限自動機與LL(1) LR(1)等分析法的關系，先概述一下文法的分類

文法分為四類：

(1)短語文法(0型文法)

(2)上下文相關文法(1型文法)

(3)上下文無關文法(2型文法)

(4)正規(則)文法(3型文法)

上面四種文法有包含的關系，1型文法是0型文法的一個子集，2型文法是1型文法的一個子集，,3型文法是2型文法的一個子集。

我們主要研究2型和3型方法。

3型文法(正則文法)與正則表達式(Regular Expression)是等價的，任意一個正則文法總是可以轉化成一個等價的正則表達式。同時正則表達式與有限自動機是等價的。一個能由有限自動機識別的語言，必然可以用正則表達式來表示，而一個用正則表達式表示的語言一定可以用一個有限自動機來識別。

但是正則文法不足以描述程序設計語言(比如，不能用正則表達式定義帶有括號的數學表達式)，現在流行的程序設計語言如C#, java等都是用2型文法，也就是上下文無關文法來定義的。因此有限自動機沒有能力來識別程序設計語言(最后我會舉個例子)。因此提出來下推自動機的模型。下推自動機具有限自動機的所有部件，如狀態、狀態轉移表等，同時它比有限自動機多一個堆棧，常稱為計算棧。下推自動機可以根據情況將終結符或者非終結符壓入棧，或者彈出棧。

而LL(1)，LR(1)等分析法就是用來分析上下文無關文法的，基于下推自動機的模型。這也是為什么介紹語法分析時，所有的書都會說一個基于LR(1)分析法的預測分析器，都會有三部分組成：狀態轉移表、控制器和計算棧。而所謂的移進與歸約就是入棧與出棧的問題。

最后，舉一個例子(好象大家都睡著了 -_-b)

先給出一個文法：

S->0S1 | 01

其中0、1是終結符。

這樣一個文法描述的語言其實就是n個0加上相等數量的n個1，這里n是某個整數。

這個文法是一個上下文無關文法，但不是一個正則文法。所以說我們沒辦法寫出一個正則表達式來描述這樣一個語言。等于一個能識別這個文法中的任意句子的NFA，我們總能找到這樣一個句子，它不是由該文法所定義的，卻能被這個NFA接受。換句話說，任意NFA都不能用來判斷某個句子是不是由以上這個文法所定義。說得實際一點，如果要求寫一個著色程序，輸入的文件是一串0、1組成的序列，要求把其中n個0加n個1的序列用紅色著色，而其它用黑色的話，我們就不能光用正則表達式匹配來完成這一任務了。

如果上面這個例子還比較抽象的話，那么對于“帶有括號的數學表達式”這樣一個語言，也是沒有辦法用正則表達式來進行匹配的。因為描述“帶有括號的數學表達式”的文法，也不是一個正則文法，因為其中帶有類似：

F->(E)

這樣的部分。

而正則文法要求所有的產生式都必須是A->aB或者A->a這樣的形式的(其中A、B是非終結符，a是終結符)