2.5 重點與難點

　　2.5.1 文法及語言形式描述：

　　本部分的內(nèi)容難點是編譯原理。與程序員級別的要求一樣，這部分的內(nèi)容比較復(fù)雜，不易理解�？梢詮南旅鎺讉�知識點來掌握：

　　文法和語言形式描述

　　這一部分主要是需要搞清楚一些基本概念和基本原理，這也是編譯原理的最基本的知識。

　　基本定義：包括字母表、字符、字、字長度、空字、字運算等等。

　　文法的定義：描述語言的語法結(jié)構(gòu)的形式規(guī)則稱為文法。

　　文法G是一個四元組，可表示為G(VT, VN, S, P)。

　　VT是一個非空有限集，每個元素稱為終結(jié)符。

　　VN是一個非空有限集，每個元素稱為非終結(jié)符。

　　P是一個非終結(jié)符，稱為開始符號;它至少要在一條產(chǎn)生式中作為左部出現(xiàn)。

　　S是一個產(chǎn)生式集合(有限)。

　　句子和語言：

　　主要涉及幾個概念。

　　I. 直接推導(dǎo)與推導(dǎo)(區(qū)別是否直接導(dǎo)出)

　　II. 直接歸約與歸約(直接推導(dǎo)和推導(dǎo)的逆過程)

　　III. 句型和句子(由開始符號推導(dǎo)出的稱為句型，僅含終結(jié)符的句型稱為句子)

　　IV. 語言(句子的全體)

　　文法的分類：

　　文法根據(jù)對產(chǎn)生式施加不同的限制，分成4種類型，即0型、1型、2型和3型。下表列出了這幾種文法的特點和區(qū)別。

　　2型文法(上下文無關(guān)文法)：

　　如今程序語言基本都可以用它來描述。重點涉及幾個概念，對于這幾個概念可以根據(jù)書上的例子來理解和掌握。在復(fù)習(xí)資料上有例題，可以找一個分析一下(99頁);

　　◎ 規(guī)范推導(dǎo)(最右推導(dǎo))：總是對句型的最右端的非終結(jié)符進行置換;

　　◎ 短語、直接短語和句柄(句柄：最左直接短語)

　　◎ 素短語：至少含有一個終結(jié)符，除本身外不含更小的素短語

　　◎ 規(guī)范歸約

　　◎ 語法樹和文法的二義性

　　對于上面的術(shù)語，一定要知道其意義，還要知道其具體的做法。

　　相關(guān)推薦：

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

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

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