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

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

其次就是NFA和DFA的計(jì)算能力確實(shí)是等價(jià)的，也就是對(duì)于任意一個(gè)NFA都可以找到一個(gè)與之等價(jià)的DFA(可以使用子集法來構(gòu)造這樣一個(gè)DFA),。

為了說明有限自動(dòng)機(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á)式與有限自動(dòng)機(jī)是等價(jià)的,。一個(gè)能由有限自動(dòng)機(jī)識(shí)別的語言,，必然可以用正則表達(dá)式來表示，而一個(gè)用正則表達(dá)式表示的語言一定可以用一個(gè)有限自動(dòng)機(jī)來識(shí)別,。

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

而LL(1),，LR(1)等分析法就是用來分析上下文無關(guān)文法的，基于下推自動(dòng)機(jī)的模型,。這也是為什么介紹語法分析時(shí),，所有的書都會(huì)說一個(gè)基于LR(1)分析法的預(yù)測(cè)分析器，都會(huì)有三部分組成：狀態(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è)能識(shí)別這個(gè)文法中的任意句子的NFA，我們總能找到這樣一個(gè)句子,，它不是由該文法所定義的,，卻能被這個(gè)NFA接受。換句話說,，任意NFA都不能用來判斷某個(gè)句子是不是由以上這個(gè)文法所定義,。說得實(shí)際一點(diǎn)，如果要求寫一個(gè)著色程序,，輸入的文件是一串0,、1組成的序列，要求把其中n個(gè)0加n個(gè)1的序列用紅色著色,，而其它用黑色的話,，我們就不能光用正則表達(dá)式匹配來完成這一任務(wù)了。

如果上面這個(gè)例子還比較抽象的話,，那么對(duì)于“帶有括號(hào)的數(shù)學(xué)表達(dá)式”這樣一個(gè)語言,，也是沒有辦法用正則表達(dá)式來進(jìn)行匹配的。因?yàn)槊枋?#8220;帶有括號(hào)的數(shù)學(xué)表達(dá)式”的文法,，也不是一個(gè)正則文法，因?yàn)槠渲袔в蓄愃疲?/P>

F->(E)

這樣的部分,。

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