2012年軟考系統(tǒng)分析師經(jīng)典教程：重點(diǎn)與難點(diǎn)

　　2.5.2 詞法分析

　　詞法分析的任務(wù)是把構(gòu)成源程序的字符串轉(zhuǎn)換成單詞符號串的中間程序。詞法規(guī)則可用3型文法(正規(guī)文法)或正規(guī)表達(dá)式描述。轉(zhuǎn)換方法有人工的狀態(tài)轉(zhuǎn)換圖方法和有限自動機(jī)的自動方法。

　　這部分主要涉及以下兩個方面的內(nèi)容。

　　● 正規(guī)表達(dá)式和正規(guī)集

　　正規(guī)表達(dá)式是一種極為有用的工具。

　　例如，對于正規(guī)文法

　　〈標(biāo)識符〉→〈標(biāo)識符〉字母

　　〈標(biāo)識符〉→〈標(biāo)識符〉數(shù)字

　　〈標(biāo)識符〉→字母(31)

　　所定義的語法范疇〈標(biāo)識符〉，我們可用如下的式子加以表述：

　　字母·(字母|數(shù)字)*(32)

　　這就是一個正規(guī)式。其中“·”，“|”及“*”分別為“連接”、“或”及“閉包”運(yùn)算符。上述正規(guī)式指明，語法范圍〈標(biāo)識符〉被定義為以字母開頭，且其后跟以由零個或多個字母和數(shù)字的任意序列。由這些序列所組成的集合，我們稱之為相應(yīng)于正規(guī)式(32)的正規(guī)集�？梢娬�(guī)式(32)也就刻畫了某種程序設(shè)計語言的標(biāo)識符的結(jié)構(gòu)。

　　如所周知，每一程序設(shè)計語言都有它自己的字符集Σ。語言中的每一單詞，或者是Σ上的單個字符 (如運(yùn)算符，分隔符等)，或者是Σ上的字符按一定方式組成的字符串 (如常數(shù)、關(guān)鍵字、標(biāo)識符以及關(guān)系運(yùn)算符等)。這里所說的“按一定方式組成”，也就是對字符或字符串進(jìn)行一定的“·”，“|”或者“*”運(yùn)算。因此，如果我們把每類單詞均視為一種語言，那么，每一類單詞都可用一個正規(guī)式來描述，而每一類單詞中的全體單詞也就組成了相應(yīng)的正規(guī)集。

　　設(shè)Σ為一字母表，則Σ上的正規(guī)式及其所表征的正規(guī)集可遞歸地定義如下。

　　1是一個正規(guī)式，相應(yīng)的正規(guī)集為空集。

　　2ε是一個正規(guī)式，相應(yīng)的正規(guī)集為{ε}。

　　3對于每一a∈Σ，a是一個正規(guī)式，相應(yīng)的正規(guī)集為{a}。

　　4若r,s是正規(guī)式，且相應(yīng)的正規(guī)集分別記為Lr及Ls，則

　　(1) (r)·(s)是正規(guī)式，相應(yīng)的正規(guī)集為LrLs;

　　(2) (r)|(s)是正規(guī)式，相應(yīng)的正規(guī)集為Lr∪Ls;

　　(3) (r)*是正規(guī)式，相應(yīng)的正規(guī)集為L*r。

　　需要注意的是，在上述定義中，圓括號并非正規(guī)式的運(yùn)算符，它們僅用于指示正規(guī)式中的子表達(dá)式。如果我們規(guī)定了上述運(yùn)算符的優(yōu)先順序： “*”最優(yōu)，“·”次之，最后是“|”，則在不產(chǎn)生混亂的情況下，可將正規(guī)式中的括號略去。例如，可將正規(guī)式((r·(s*))|r)寫成r·s*|r。另一方面，我們也可以在一個正規(guī)式中添加括號來改變原來的運(yùn)算順序，例如r·(s*|r)。顯然，在這種情況下，正規(guī)式中的括號不能隨便略去。此外，正規(guī)式中的連接運(yùn)算符“·”常被略去。如正規(guī)式r·s*|r和r·(s*|r)可分別寫為rs*|r和r(s*|r)。

　　● 有限自動機(jī)

　　有限自動機(jī)作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集。它分為兩類：確定的有限自動機(jī)(DFA)和不確定的有限自動機(jī)(NFA)。在有限自動機(jī)理論中，可以通過子集法的算法來實(shí)現(xiàn)NFA到DFA的轉(zhuǎn)換。

　　比如： ：所有與b為首后跟任意多個a的字

　　：所有與a為首的字;

　　：含有兩個相繼的a或兩個相繼的b的字。

　　(需要拷貝)語言L={ambn|m≥0，n≥1}的正規(guī)表達(dá)式是__A__。 (程序語言)

　　(1) A. a*bb*B. aa*bb*C. aa*b*D. a*b*

　　相關(guān)推薦：

　　2012年軟考系統(tǒng)分析師考試60天完美復(fù)習(xí)計劃

　　2012年軟件水平考試網(wǎng)絡(luò)工程師章節(jié)筆記講義匯總

　　2012年上半年軟件水平考試成績查詢匯總