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

　　2.5.2 詞法分析

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

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

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

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

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

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

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

　　〈標(biāo)識(shí)符〉→字母(3��1)

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

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

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

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

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

　　1�笔且粋�(gè)正規(guī)式，相應(yīng)的正規(guī)集為空集。

　　2�宝攀且粋�(gè)正規(guī)式，相應(yīng)的正規(guī)集為{ε}。

　　3�睂�(duì)于每一a∈Σ，a是一個(gè)正規(guī)式，相應(yīng)的正規(guī)集為{a}。

　　4�比魊,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。

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

　　● 有限自動(dòng)機(jī)

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

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

　　：所有與a為首的字;

　　：含有兩個(gè)相繼的a或兩個(gè)相繼的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í)計(jì)劃

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

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