形式语言与自动机-第2章-语言与文法

1、1College of Computer Science : . ? ! “ ” ( ) - 汉字表汉字表 , 自自, , 动动 , , 机机, - 化学元素表化学元素表 H, He, Li, , - T = a, n, y, 任任,意意 5College of Computer Science 21College of Computer Science SSAS; S(S); A+; A; A*; A/; 31College of Computer Science & Technology, BUPT 第三节 Chomsky文法体系分类 n文法文法 G = (N,T,P,S)； P: 其中其

2、中 (NT)* N+ (NT)* (NT)* 属于属于Chomsky文法体系文法体系 n该体系对该体系对生成式（产生式）生成式（产生式）的形式做了一的形式做了一 些规定，分为四类，即些规定，分为四类，即0型、型、1型、型、2型、型、3 型文法型文法 n0型文法：无限制文法型文法：无限制文法 对应的语言：递归可枚举语言，与图灵机 等价。 32College of Computer Science & Technology, BUPT 1型文法 n也称上下文有关文法（也称上下文有关文法（CSG：Context- sensitive Grammar) 生成式的形式为生成式的形式为， 其中其中 | |

3、 ，(NT)+， (NT)* N+ (NT)* n对应的语言：上下文有关语言（对应的语言：上下文有关语言（CSL： Context-sensitive Language) n若不考虑若不考虑，与线性有界自动机（与线性有界自动机（LBA, Linear Bounded Automaton）等价。等价。 College of Computer Science & Technology, BUPT 1型文法 语言限定约束： n左部的长度小于右部左部的长度小于右部 n不含不含A-A- n实际程序语言中上下文有关的部分： n过程调用时形参与实参的一致性检查等。过程调用时形参与实参的一致性检查等。 34C

4、ollege of Computer Science & Technology, BUPT 2型文法 n也称上下文无关文法（也称上下文无关文法（CFG：Context-free Grammar) A , AN, 且且 (NT)* n对应的语言：上下文无关语言对应的语言：上下文无关语言 （CFL： Context-free Language)。 n对 应 的 自 动 机 ： 下 推 自 动 机 （对 应 的 自 动 机 ： 下 推 自 动 机 （ P D A ： Pushdown Automaton)。 College of Computer Science & Technology, BUPT

5、 n语言限定约束：语言限定约束： 左部是单个非终结符。 nCFL对实际语言结构的抽象：对实际语言结构的抽象： n表示句子的语法结构，如：表达式，嵌套结构 。 n目前的程序设计语言主要采用CFL描述语法结构 。 36College of Computer Science & Technology, BUPT 3型文法 也称正则文法也称正则文法 n右线性文法（右线性文法（Right-linear Grammar） AB 或或 A A、BN, T*。 n左线性文法（左线性文法（Left-linear Grammar）：）： AB 或或 A A、BN, T*。 n对应的语言：正则语言对应的语言：正则语

6、言 n对应的自动机：有限自动机对应的自动机：有限自动机(Finite Automaton)。 37College of Computer Science & Technology, BUPT 例例1： G = (A,B,C, a,b,d, P, A) P: AAB；ABCAAB；Ad；Ba；Cb 是是1型文法。型文法。 A=d A=AB =dB =da A=AB =ABB =dBB =daB =daa A=AB =CAAB =bAAB =bdAB =bdCAAB =bdbAAB =bdbdAB=bdbddB =bdbdda 38College of Computer Science & Tec

7、hnology, BUPT 例例2： G = (A,B,C, a,b,c, P, A) P: Aabc AaBbc BbbB BcCbcc bCCb aCaaB aCaa 是是1型文法。型文法。 其定义的其定义的 L = anbncn | n1 n A =abc n A =aBbc =abBc =abCbcc =aCbbcc =aabbcc =aaBbbcc 39College of Computer Science & Technology, BUPT 例例3： G = (S,B,C, a,b, P, S) P: SaC；SbB；BaS；BbBB Ba； CbS；CaCC；Cb 是是2型文法

8、型文法 n S =aC =ab nS = aC =aaCC nS =aC =abS =abaC =ababS =ababaC =ababab nS =bB =bbBB =bbaSB=bbaaCB =bbaabB =bbaaba 40College of Computer Science & Technology, BUPT 例例4： G = (A,B,C, a,b,c, P, A) P: ABa； Ac； BCb； Cc n左线性文法左线性文法 n L = c, cba 正则语言正则语言 n注意：已知语言求文法，文法不是唯一的，即可以注意：已知语言求文法，文法不是唯一的，即可以 有不同的表达方法有不同的表达方法。 41College of Computer Science & Technology, BUPT 四类文法之间的关系 n只是对生成式形式加以限制只是对生成式形式加以限制 n0型型 无限制无限制 n1型型 不允许不允许A形式形式 n2型型 (A 可作为特例可作为特例) n3型型 属于属于2型型 n不含不含A