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页）；

　　◎ 规范推导（最右推导）：总是对句型的最右端的非终结符进行置换；

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

　　◎ 素短语：至少含有一个终结符，除本身外不含更小的素短语

　　◎ 规范归约

　　◎ 语法树和文法的二义性

　　对于上面的术语，一定要知道其意义，还要知道其具体的做法。