2.5 重點與難點

　　2.5.1 文法及語言形式描述：

　　本部分的內容難點是編譯原理。與程序員級別的要求一樣，這部分的內容比較復雜，不易理解。可以從下面幾個知識點來掌握：

　　文法和語言形式描述

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

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

　　文法的定義：描述語言的語法結構的形式規則稱為文法。

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

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

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

　　P是一個非終結符，稱為開始符號;它至少要在一條產生式中作為左部出現。

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

　　句子和語言：

　　主要涉及幾個概念。

　　I. 直接推導與推導(區別是否直接導出)

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

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

　　IV. 語言(句子的全體)

　　文法的分類：

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

　　2型文法(上下文無關文法)：

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

　　◎ 規范推導(最右推導)：總是對句型的最右端的非終結符進行置換;

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

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

　　◎ 規范歸約

　　◎ 語法樹和文法的二義性

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

　　相關推薦：

　　2012年軟考系統分析師考試60天完美復習計劃

　　2012年軟件水平考試網絡工程師章節筆記講義匯總

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