《编译原理-第2章-文法和语言讲述》由会员分享，可在线阅读，更多相关《编译原理-第2章-文法和语言讲述（91页珍藏版）》请在金锄头文库上搜索。
1、第2章 文法和语言 n2.1 字母表和符号串 n2.2 文法 n2.3 推导 n2.4 句型和句子 n2.5 语言 n2.6 递归规则与递归文法 n2.7 短语、简单短语和句柄 n2.8 语法树 n2.9 子树与短语 n2.10 由树构造推导过程 n2.11 文法的二义性 n2.12 有关文法的实用限制 n2.13 文法和语言分类 学习重点 n1 文法的定义、分类和二义性 n2 最左推导、规范推导(或最右推导) n3 语言、句型和句子 n4 短语、简单短语(或直接短语)和句柄 n5 语法树 形式语言 n如果不考虑语义和语用，只从语法这一侧面来看 语言，它是由符合某种语法（用规则定义）的句 子构
2、成的集合，这种意义下的语言称作形式语言 。 n例 汉语：所有符合汉语语法的句子的全体 英语：所有符合英语语法的句子的全体 程序设计语言：所有符合该语言语法的程序的 全体 形式语言 n形式语言抽象地定义为一个数学系统，即能用 数学符号和规则描述的语言。形式语言理论是对 符号串集合的表示法、结构及其特性的研究。 这种理论对程序设计语言的设计和编译程序的 构造有着重大的作用。 2.1 字母表和符号串 n字母表 (或符号集) ：元素的非空有穷集合。 n例 二进制数语言的字母表=0,1 汉语的字母表中包括汉字、数字及标点符号等 PASCAL语言的字母表是由字母、数字、若干 专用符号及BEGIN、IF之类
3、的保留字组成 C语言的字母表由字母、数字、若干专用符号 以及if、else、while等关键字组成 2.1 字母表和符号串 n符号：字母表中的元素。 n例 =a,b,for,1，则a,b,for,1都是的符号。 n不要把符号理解成字符。 n典型的符号有字母、数字、各种标点符号和各 种运算符。 2.1 字母表和符号串 n符号串：由字母表上0个或多个符号所组成的任何 有穷序列。空符号串 也是字母表上的符号串，它由 0个符号组成。 n例 =0,1，则， 0，1，01，10，00，11，100， 0110，111110000等二进制数都是上的符号串 =a,b,c,+,*，则， a ， b ， c ，
4、+ ， *，aa，ab ，ac，a+，a*，ba，bb，bc，b+，b*，aaa，bbb等 都是上的符号串 n一个字母表上的全部符号串所组成的集合是无穷的 。 2.1 字母表和符号串 n符号串的长度：指符号串x中所含符号的个数， 记为|x|。特别地， |=0。 n例 =a,b,c,+,*， |abc|=3，|abc+*abc|=8 n符号串相等：若x、y是字母表上的两个符号串 ，那么当且仅当组成x的各符号与组成y的各符号 依次相等时，则符号串x与符号串y相等，记作x=y 。 n例 当x=abbc，y=abbc 时，则x=y 当x=ab，y=ba 时，则xy 2.1 字母表和符号串 n符号串的前
5、缀：指从符号串x的末尾删除0或多个符 号后得到的符号串。 n例 u、uni、university都是university的前缀 n符号串的后缀：指从符号串x的开头删除0或多个符 号后得到的符号串。 n例 ty、sity、university都是university的后缀 n符号串的子串：指从符号串x的开头和末尾删除0或 多个符号后得到的符号串， n例 ver是university的子串, 符号串的前缀、后缀都 是它的子串。 2.1 字母表和符号串 n符号串的连接：若x、y是两个符号串，则xy是 将符号串y连接在符号串x的后面。 n例 x=ab，y=ba，则 xy=abba n若x、y是字母表上
6、的两个符号串，则xy也是 字母表上的符号串。 n除x=x=x外，连接没有交换率， 即 xy yx 。 2.1 字母表和符号串 n集合的乘积运算：令A、B为两个符号串集合， AB=xy|xA ,yB 。对于空集合有，有 A=A =A 。 n例 A=a,b， B=c,d，则AB=ac,ad,bc,bd n符号串的幂运算：若x是符号串，则： x0=, x1=x ， x2=xx，xn=xxx=xxn-1=xn-1 x，其中 n0 。 n例 x=abc, x0=， x1=abc， x2=abcabc， 2.1 字母表和符号串 n集合的幂运算：设A为符号串集合，则： A0= A1=A A2=AA An=A
7、AA=AAn-1=An-1 A，其中 n0 n例 A =a，b，则 A0= A1=a,b A2=aa,ab,ba,bb 2.1 字母表和符号串 n集合的正闭包：设A为一个集合，则： A+ =A1A2.An n例 A =a,b，则A+ =a,b,aa,ab,ba,bb,aaa,aab, n集合的闭包：设A为一个集合，则： A* =A0 A+ n例 A =a,b，则A* =,a,b,aa,ab,ba,bb,aaa,aab, n一个集合的闭包比正闭包多个。 2.2 文法 n文法实际上就是描述语言语法结构的形式规则。 这些规则说明句子由主语 和谓语组成，主语由冠词和 名词等等，而冠词由the构成 ，名
8、词由banana或monkey构 成。在这个文法里，一共有8 条规则，每条规则中在:=左 边的符号起着语法成分的作 用，它们可用:=右边的符号 代替。而像the、ate、 banana这样的符号只在规则 中:=的右边出现，这些符号 不能用其它符号代替。 := := := := := := := := 例 描述句子“the monkey ate the banana”的文法如下： n文法G的形式定义：G=(Vn，Vt，P，Z) Vn(非终结符号集)是一个由非终结符号（一般是大写字 母或用）构成的非空有穷集合。 Vt (终结符号集)是一个由终结符号（如小写字母、数字 、标点符号等）构成的非空有穷集
9、合。 VtVn=， VtVn，V是该文法的字母表或词汇表。 P(产生式集)是一个由产生式或规则构成的非空有穷集 合。 产生式的形式为： 或:= 产生式的左部V+，即不能为空，产生式的右部 V*，“”或”“:=”含义相同，表示“定义为”或“由 组成”。 Z是文法的识别符号或开始符号， Z Vn，要求Z至少 必须在某个产生式的左部出现一次。 2.2 文法 n例2-1(P15) 文法 G1=(Vn，Vt，P，Z)，其中： Vn=， ， ， ， ， Vt= the，ate，banana， monkey P由下面8条规则组成: 识别符号： the ate banana monkey 2.2 文法 n例2
10、-1(P15) 文法 G1可以简化写成： G1 : the ate banana monkey the ate banana monkey 或 2.2 文法 n 例2-2) 有如下简化表示文 法，只给出规则集，写出该 文法的终结符号集合、非终 结符号集合和识别符号。 0 1 2 3 4 5 6 7 8 9 解：根据简化约定，可确定： Vn=, Vt=0,1,2,3,4,5,6,7,8,9 识别符号： 2.2 文法 n文法的EBNF表示：用一些特殊的元符号“|”、“”和 “”、“”、“（” 和“）”、“” 和“”来表示文法 。 n例2-3 对例2.2文法的13条规则可缩写成： := :=| :=
11、0|1|2|3|4|5|6|7|8|9 n“|”：表示“或” 。 对于具有相同左部的那些规则， 如 1， 2 ， n 缩写为: 1 |2 |n 2.2 文法 n“”：用于括起由中文字组成的非终结 符号或由多个字母组成的符号。 n例 （一般写成monkey ） 2.2 文法 n“”和“”：表示可重复连接，tkm表示符号串 t可重复连接k到m次，而t表示符号串t可重复 连接0到无穷次。 n例 13 等价于： | EE+T|T 与 ET+T 相同 字母打头、后面可跟字母或数字的不超过8个字符的标 识符文法则为： |07 2.2 文法 n“”和“ ”：表示括起来的内容可有可无。如t 表示符号串t可有可
12、无。 n例 IF THEN IF THEN ELSE 可写成： IF THEN ELSE 2.2 文法 n“（”和“）”：表示括号内的成分优先。常用 于在规则中提取公因子。 n例 Uxy|xw|xz 可写成： Ux（y|w|z） 2.2 文法 n 练习 已知文法 ET|E+T|E-T TF|T*F|T/F F(E)|i 写出该文法的开始符号、 Vn和Vt。 解：根据简化约定，可 确定： 开始符号：E Vn=E,T,F Vt=+,-,*,/,(,),i 2.13文法和语言分类 n 0型文法(或短语结构文法) 若文法中有如下形式的规则： 其中， V+ (即可以是V上的符号序列，但 不能为空)，V*
13、 (即是V上的符号序列，可以是) 。如果文法中有产生式的右部为，并且该产生式的 左部不是一个非终结符，则该文法一定是0型文法。 0型文法描述的语言为0型语言。 例 文法G1=(Vn,Vt,P,S)，其中：Vn=S,A,B,C,D,E ， Vt=a ，P=S:=ACaB,Ca:=aaC,CB:=DB,CB:=E, aD:=Da,AD:=AC,aE:= ，该文法是一个0型文法。 2.13文法和语言分类 n 1型文法(或上下文有关文法) 若文法中有如下形式的规则： Uu 其中， UVn，、V*，u V* ，即规则左部 可为符号序列，其中U为非终结符号且只有在左右为 和的环境下U可变为u。1型文法的产
14、生式左部的长度 小于等于其右部的长度，但S除外。1型文法描述的 语言为1型语言。 例 文法G2=(Vn,Vt,P,S) ，其中, Vn=S,A,B,C ， Vt=a,b,c ，P=S:=aSBC,S:=aBC,aB:=ab,bB:=bb, bC:=bc,CB:=BC,cC:=cc ，该文法是一个1型文法。 2.13文法和语言分类 n 2型文法(或上下文无关文法) 若文法中的规则都具有如下形式： Uu 其中， U Vn ， u V*，即2型文法中的规则左部 必须是一个非终结符号，规则右部u是V上的符号序列 。该文法相当于对1型文法中的规则形式加以限制，即 要求和必须为空。2型文法也称作上下文无关
15、文法， 描述的语言为2型语言。一般用2型文法来描述程序设计 语言的语法规则。 例 文法G3=(Vn,Vt,P,N) ，其中, Vn=N,D ，Vt=0,1,2, 3,4,5,6,7,8,9 ，P=N:=ND|D,D:=0|1|2|3|4|5|6|7|8|9 ， 该文法是一个2型文法。 2.13文法和语言分类 n 3型文法(或正规文法) 若文法中的规则都具有如下形式： Ua |Wa（左线性）或 Ua|aW（右线性） 其中， U，WVn，aVt ( a可为)。 3型文法中 的产生式全部是左线性产生式或全部是右线性产生式。 3型文法描述的语言为3型语言。用3型文法描述程序设 计语言的单词的构词规则，如标识符、无符号整数等。 n例 左线性3型文法： NN0|N1|N2|N3|N4|N5|N6|N7
