第2章 文法及语言.ppt

2.1 基本概念 2.1.1 字母表与符号串 ① 字母表:元素的非空有穷集合，习惯上用大写字母表示，如∑={a，b} 。 ② 符号：字母表中的每一个元素，如a，b 。 ③ 符号串：字母表中的符号的有穷序列，如a，b ，aa，bb…。 ④ 空符号串：不含任何符号的符号串，记为ε。 ⑤ 符号串集合：字母表Σ上的符号串组成的集合。 2.2 文法 语言是特定字母表上具有一定语法结构的符号串的集合。若用L表示语言，用Σ表示字母表，则 L∈Σ＊ 文法(Grammar)是定义或描述语言的语法结构的一组形式规则(即语法规则)。一个程序语言的文法的目的就是用适当条数的规则把该程序语言全部成分描述出来。 2、文法和字汇表 文法可以定义成一个四元组G[S]=(VN，VT，S，P)。 其中，VT:非空有限的终结符号集； VN:非空有限的非终结符号集； S:开始符号，是文法G规定的最终目标； P:产生式的集合。 V=VN∪VT称为文法G[S]的字汇表。 VN∩VT= ?，S?VN。 为了方便，表示文法时只列出产生式，而不以4元组显示地表示出来。 2.2.5 文法等价变换 1 、有害规则 定义:文法中形如 U→U 的规则就称为有害规则。 如果文法中含有有害规则,它除了造成文法的二义性以外，对定义语言则是没有任何的意义。 2 、多余规则 定义: 设文法中某一规则，其左部的非终结符号为U,若满足下列条件之一,则称该规则为多余规则。 ① U (除文法的开始符号)不出现在该文法的任何其它规则的右部； ②若在规则中采用该规则，则不能由U推出终结符号串。 2.2.2 文法和语言的分类 0型文法与0型语言 1型文法与1型语言 2型文法与2型语言 3型文法与3型语言 0型文法 0型文法(无限制的文法)。其产生式具有以下形式： ?→? 其中，??V+，且至少含有一个非终结符；??V* 1型文法（上下文有关文法） 定义：1型文法G的产生式具有以下形式： xUy→xuy 其中x,y?V*;U?VN; u?V+。 例如：1型文法G[S] =(VN，VT，P，S) 其中， VN={S，X，Y，Z} VT=（x，y，z） P={S→xYZ, xY→xy，yY→yy, yZ→yz ZY→YZ, zZ→zz} 2型文法（上下文无关文法） 定义：在1型文法的产生式中上下文x和y用空符号串?代替，则有以下形式的产生式称为2型文法： U→u 其中，U?VN，u?V* 。 例如：2型文法G[E] =(VN，VT，P，E) 其中， VN={E，T，F} VT={+，*，(，)，i } P={E→E+T?T，T→T?F?F，F→(E) ?i } 3型文法（正规文法） 定义1：如果的产生式只含有下面的两种形式： U→a 或 U→aB 其中U，B?VN，a?VT*，则称该文法为右线性文法； 定义2：如果文法的产生式只含有下面的两种形式： U→a或U→Ba 其中U，B?VN，a?VT* ，则称该文法为左线性文法； 例如：右线性文法G[S]=(VN，VT，P，S) 其中， VN={S，A，B} VT={0, 1 } P={S→0?1?1A?0B，A→1A?0B，B→0?1?0B } 例如：DFA M=({0，1，2，3}，{a，b}，f，0，{3})， 其中：f定义如下： f(0，a)=1 f(0，b)=2 f(1，a)=3 f(1，b)=2 f(2，a)=1 f(2，b)=3 f(3，a)=3 f(3，b)=3 2.3.2 非确定有限自动机(NFA) 定义：一个非确定有限自动机(NFA) M是一个五元式M=(S, ?, f, S0, F)，其中： 1 S: 有穷状态集； 2 ? ：输入字母表(有穷)； 3 f: 状态转换函数，它是一个从S??到S的子集的映射(非单值)； 4 S0?S是非空的初态集； 5 F ?S ：终态集。 1. 假定NFA M=S, ?, ?, S0, F，我们对M的状态转换图进行以下改造： 1) 引进新的初态结点X和终态结点Y，X,Y?S，从X到S0中任意状态结点连一条?箭弧， 从F中任意状态结点连一条?箭弧到Y。 2) 对M的状态转换图进一步施行替换，其中k是新引入的状态。 例：识别所有含相继两个a或相继两个b的字 2. 把上述NFA确定化——采用子集法. 设a