编译原理知识点概述[11-4修订]

文法

方法是一个数学系统有几个基本成分：基本符号，形成规则，公理，推理规则。

文法G定义为四元组(V_n，V_T，P，S)。其中Vn为非终结符号(或语法实体，或变量)集，一般用大写字母表示；

V_T为终结符号集，一般用小写字母表示；

P为产生式(也称规则)的集合；V_n，V_T和 P是非空有穷集。

S 称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。

V_n和V_T不含公共的元素，即V_n∩V_T=φ

文法分类

1. 0型文法，又称短语文法。
   要求：产生式左边与右边都可以是非终结符与终结符，但左边至少有一个非终结符。
2. 1型文法，又称上下文有关文法。
   要求：1型文法在0型文法之上有所限制，即产生式左边的串长小于等于右边的串长。但有特例 α→ε，也属于1型文法。ε表示空。
3. 2型文法，又称上下文无关文法。
   要求： 2型文法在1型文法上又有限制，即产生式左边只有一个非终结符，而右边则任一。
4. 3型方法，又称正规文法。
   要求：3型文法从广义上讲包括左线形文法、右线形文法和正规文法
   
   • 左线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最左端。

   例如：A→α｜Bα

   • 右线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最右端
     例如：A→α｜α B
   • 正规文法是右线形文法的一个子集，其产生式右部只有三种情况：1）空串    2）只有一个终结符      3）只有一个终结符后接一个非终结符。

正规式与正规文法之间的转换

其变换规则三种：