编译原理1

 NFA&DFA

在正规式的等价证明可以借助正规集，也可以通过有限自动机DFA来证明等价，以下例题是针对DFA证明正规式的等价，主要步骤是①NFA；②状态转换表； ③状态转换矩阵； ④化简DFA；

文法和语言

文法通常表示成 四元组 G[S] = ( V T ， V N ， S ， ξ):

(1)   V T 为终结符号集 ，这是一个非空有限集，它的每个元素 称为 终结符号 。

(2)   V N 为非终结符号集 ，它也是一个非空有限集，每个元 素称为 非终结符号 ， 且有 V T ∩V N  = Φ ；

(3)  S 为文法开始符 ，是一个特殊的非终结符号，即 S ∈ V N ；

(4)   ξ /ksi/ 是产生式的非空有限集 ，其中每个产生式 ( 或称规 则 ) 是一序偶 (α ， β) ，通常写作

α → β 或 α ::= β

α 、 β 是由终结符和非终结 符组成的符号串， α ∈ (V T ∪ V N ) + 且至少有一个非终结符， 而 β ∈ (V T ∪ V N ) * 。

例：产生标识符的文法

例：奇数集合，不允许出现以0开头的奇数文法 

例：上下文无关文法描述正规表达式 

基本概念： 

① 句子仅含有终结符，是特殊的句型；

②文法开始符号一定是句型；

③文法产生的句子的全体为文法产生的语言；(标识符、表达式i+i*i都是语言，都由非终结符组成) 

④文法确定，则语言一定确定；反之，不一定可以由语言唯一确定文法；

⑤文法产生语言的过程中必须经过‘+’次推导(至少进行一次推导)；

形式语言分类：

(1) 0型文法与语言

对应图灵机； 

文法G[S]的每一个产生式 都有   α->β  

α 作为产生式左端，至少有一个非终结符

β 作为产生式右端，不做要求(甚至可以为空)； 

(2) 1型文法与语言

线性界限自动机，自然语言；

在0型文法的基础上要求文法产生式左端的长度要 小于等于 右端的长度；

 (3) 2型文法与语言

对应下推自动机，程序设计语言；

文法G[S]的每一个产生式 都有   A->α  

A∈非终结符

α∈(终结符和非终结符的闭包) 

(4) 3型文法与语言

对应有限自动机；

文法G[S]的每一个产生式 都有   A->α  或者  A->αB[右线性]  或者  A->Bα[左线性] 

A∈非终结符

α∈(终结符的闭包) 

关系和区别

① 1-3型文法属于 0 型文法；

② 2型 和 3型 文法不一定属于 1型 文法；

③ 1型文法 不允许有形如“”A->ε”, 2、3型文法允许；

④ 0、1型文法左边产生式 可以含有终结符或者两个以上终结符； 2、3型文法左端产生式要求单个非终结符(单非)；