昨天和Sumtec談到自動機(jī)和語法分析，一下子腦子有點(diǎn)混亂，把一些概念搞混了，看了半天清華的編譯書也沒有整明白...今天早上起來看了《離散數(shù)學(xué)及其應(yīng)用》里的自動機(jī)一部分，才厘清了頭緒。還是外國人的書講得清楚一點(diǎn)。 
昨天主要是把NFA和語法分析中的LL(1) LR(1)搞混了。事實(shí)上LL(1)分析也好LR(1)分析也好，使用的是一個(gè)基于下推自動機(jī)的計(jì)算模型，而不是有限自動機(jī)。下推自動機(jī)的計(jì)算能力要比有限自動機(jī)強(qiáng)。
其次就是NFA和DFA的計(jì)算能力確實(shí)是等價(jià)的，也就是對于任意一個(gè)NFA都可以找到一個(gè)與之等價(jià)的DFA(可以使用子集法來構(gòu)造這樣一個(gè)DFA)。
為了說明有限自動機(jī)與LL(1) LR(1)等分析法的關(guān)系，先概述一下文法的分類
文法分為四類：
(1)短語文法(0型文法)
(2)上下文相關(guān)文法(1型文法)
(3)上下文無關(guān)文法(2型文法)
(4)正規(guī)(則)文法(3型文法)
上面四種文法有包含的關(guān)系，1型文法是0型文法的一個(gè)子集，2型文法是1型文法的一個(gè)子集，,3型文法是2型文法的一個(gè)子集。
我們主要研究2型和3型方法。
3型文法(正則文法)與正則表達(dá)式(Regular Expression)是等價(jià)的，任意一個(gè)正則文法總是可以轉(zhuǎn)化成一個(gè)等價(jià)的正則表達(dá)式。同時(shí)正則表達(dá)式與有限自動機(jī)是等價(jià)的。一個(gè)能由有限自動機(jī)識別的語言，必然可以用正則表達(dá)式來表示，而一個(gè)用正則表達(dá)式表示的語言一定可以用一個(gè)有限自動機(jī)來識別。
但是正則文法不足以描述程序設(shè)計(jì)語言(比如，不能用正則表達(dá)式定義帶有括號的數(shù)學(xué)表達(dá)式)，現(xiàn)在流行的程序設(shè)計(jì)語言如C#, java等都是用2型文法，也就是上下文無關(guān)文法來定義的。因此有限自動機(jī)沒有能力來識別程序設(shè)計(jì)語言(最后我會舉個(gè)例子)。因此提出來下推自動機(jī)的模型。下推自動機(jī)具有限自動機(jī)的所有部件，如狀態(tài)、狀態(tài)轉(zhuǎn)移表等，同時(shí)它比有限自動機(jī)多一個(gè)堆棧，常稱為計(jì)算棧。下推自動機(jī)可以根據(jù)情況將終結(jié)符或者非終結(jié)符壓入棧，或者彈出棧。
而LL(1)，LR(1)等分析法就是用來分析上下文無關(guān)文法的，基于下推自動機(jī)的模型。這也是為什么介紹語法分析時(shí)，所有的書都會說一個(gè)基于LR(1)分析法的預(yù)測分析器，都會有三部分組成：狀態(tài)轉(zhuǎn)移表、控制器和計(jì)算棧。而所謂的移進(jìn)與歸約就是入棧與出棧的問題。
最后，舉一個(gè)例子(好象大家都睡著了 -_-b)
先給出一個(gè)文法：
S->0S1 | 01
其中0、1是終結(jié)符。
這樣一個(gè)文法描述的語言其實(shí)就是n個(gè)0加上相等數(shù)量的n個(gè)1，這里n是某個(gè)整數(shù)。
這個(gè)文法是一個(gè)上下文無關(guān)文法，但不是一個(gè)正則文法。所以說我們沒辦法寫出一個(gè)正則表達(dá)式來描述這樣一個(gè)語言。等于一個(gè)能識別這個(gè)文法中的任意句子的NFA，我們總能找到這樣一個(gè)句子，它不是由該文法所定義的，卻能被這個(gè)NFA接受。換句話說，任意NFA都不能用來判斷某個(gè)句子是不是由以上這個(gè)文法所定義。說得實(shí)際一點(diǎn)，如果要求寫一個(gè)著色程序，輸入的文件是一串0、1組成的序列，要求把其中n個(gè)0加n個(gè)1的序列用紅色著色，而其它用黑色的話，我們就不能光用正則表達(dá)式匹配來完成這一任務(wù)了。
如果上面這個(gè)例子還比較抽象的話，那么對于“帶有括號的數(shù)學(xué)表達(dá)式”這樣一個(gè)語言，也是沒有辦法用正則表達(dá)式來進(jìn)行匹配的。因?yàn)槊枋觥皫в欣ㄌ柕臄?shù)學(xué)表達(dá)式”的文法，也不是一個(gè)正則文法，因?yàn)槠渲袔в蓄愃疲?span lang="EN-US">
F->(E)
這樣的部分。
而正則文法要求所有的產(chǎn)生式都必須是A->aB或者A->a這樣的形式的(其中A、B是非終結(jié)符，a是終結(jié)符)