《编译原理及其习题解答(武汉大学出版社)课件chap2》由会员分享，可在线阅读，更多相关《编译原理及其习题解答(武汉大学出版社)课件chap2（84页珍藏版）》请在金锄头文库上搜索。
1、第二章 文法和语言 要点(本章是基础)1、概念:文法,推导,直接推导,最左(右)推导,产生 式,句型,短语,直接短语,句柄,语法树,规范推导,二 义文法等2、4种文法的定义、文法的构造和文法的推导3、语法树的构造和最左（右）推导；4、二义文法、二义性的证明；5、句型分析；1词法规则：自动机语法规则：上下文无关文法2引言语言包括语法和语义两方面。语法是一组规则，用以判断什么样的符号序列是合法的；语义指含义，如变量的类型、作用域是否符合正确的语法 。常把程序设计语言的语义分为二类：静态语义和动态语义 。静态语义是一系列限定规则，并确定哪些合乎语法的程序 是合适的；动态语义（或称运行语义、执行语义）
2、，表明程 序要做些什么，要计算什么。阐明语法的一个工具是文法，常采用上下文无关文法作 为程序设计语言语法的描述工具。3补充： 文法的直观概念(1/5)描述一种语言，无非是说明这种语言的句子。如 果该语言所含的句子是有限的，那么只要一一列举出 即可；若是无限的，则存在如何给出有穷表示的问题 。但无论如何，某语言的句子总是存在着一种组成结 构，即所谓的规则（或称文法）。文法：描述语言的语法结构的形式规则（即语法 规则）。4直观文法举例(2/5)例如：简单的汉语句子的构成规则 := := | := 我 | 你 | 他 :=王明| 大学生|工人|英语 := :=是 |学习 := | 则 “我是大学生”
3、是句子5“我是大学生”的推导过程：我 我 我是 我是 我是大学生 依次可以推导出句子“王明是大学生”、“我学习英语”等等推导过程(3/5)6程序设计语言对文法的要求 (4/5)这些规则必须是准确的，易于理解的 ，且应当有相当强的描述能力，足以描述 各种不同的结构。7文法作用(5/5)（1）定义句子的结构； （2）用适当条数的规则把语言的全部句子 描述出来，以有穷集合刻划无穷集合。82 符号串及其运算（1）符号串：由字母表中的符号组成的任何有穷序列。说明: 字母间的顺序 不同顺序组成的符号串是不同的；（2）符号串长度 符号串内所含符号的个数，若x=string,则 |x|=6; 其中不含任何符号
4、的符号串称为空符号串，长度| | 02.1 语言成分1 字母表（符号表）与符号元素（或称符号）的非空有穷集合，用符号表示。不同语言有不同的字母表。如汉语包括汉字、数字、标 点符号等；C语言包括字母、数字和保留字等等。9符号串的运算(1/3)符号串的头尾，固有头和固有尾：设 z=xy 是一个符号串，则x是z的头，y是z的尾。如果x是 非空的，那么y是是固有尾；如果y是非空的，那么x是固有头 。例：z=abc，则z的头：、a、ab、abc； 固有头： 、a、ab；z的尾：、c、bc、abc； 固有尾： 、c、bc；当我们对符号z=xy 的头感兴趣而对其余部分不感兴趣时 ，我们可以采用省略写法：z=
5、x。如果只是为了强调x在符 号串中的某处出现，则可表示为：z=x；符号t是符号串z 的第一个符号，则表示为：z=t。10(3)符号串的连接设x和y是符号串，它们的连接xy是把y的符号写在x的 符号之后得到的符号串。例如：x=abc，y=DEF，则xy=abcDEF；若| x | = n，| y |m，则| xy | = n+m 对任意的符号串x，有 x = x = x11（4） 符号串集合的乘积设A、B是两个符号串的集合，则AB表示A与B的乘 积，定义为：AB=xy|xA,yB如：若A=ab,c, B=d,efg,则AB=abd,abefg,cd,cefg特别地，有：A=A=A 空集 表示不含
6、任何元素的空集。有： A=A = 请区别： ，三种表示方法的含义12（5） 符号串的方幂同一符号串的连接可以写成方幂的形式。设x是符号串，把x自身连接n次得到的符号串z，即 z=xxxx，称为符号串x的方幂，记作z=xn，有：x0=x1= x x2= xxx3= xxx 当n0时， xn x xn-1 = xn-1 x13（6）符号串集合的方幂同一符号串集合的连接也可以写成方幂的形式。 设符号串集合为A，则有： A0= A1= A A2= AA A3= AAA 当n0时， An A An-1 = An-1 A例如：A=ab，c，则AA= AAA= 14（7）符号串集合的正闭包设符号串集合为A，
7、则A的正闭包记为A+ ，定义为 ： A+ = A1 A2 An 表示A上所有有穷长串的集合例如：A=ab，c，AA= ， AAA= （8）符号串集合的自反闭包设符号串集合为A，则A的自反闭包记为A* ，定义为： A* = A0 A1 A2 An 即A* = A0 A+ = A+例如： A= a,b，则 A*=, a, b, aa, ab, ba, bb, aaa, A+ = A* A = AA*152.2 产生式文法和语言2.2.1 文法的形式定义是一个四元组G =（VN，VT，P，S）VN 非终结符号集，非终结符号代表的是语法范畴，也就是它是 一类（或集合）的记号，而不是一个个体记号。如“表
8、达式”、“语句”、“分 程序”等等，都是表达一定的语法概念。因此，每个非终结符表示一定符 号串的集合（由终结符和非终结符 组成）；(如简单汉语句子中。）VT 终结符号集合，终结符是构成语言的基本符号，也就是说， 它是一个语言的不可再分的基本符号；P 产生式（或称规则,重写规则,生成式）集合。所谓产生式是定 义语法范畴的一种书写规则。一个产生式的形式是 （或:= )，其 中 “”读为“是”或“定义为”；产生式的左部 (VNVT )*且至少含有一个非终结符号，右部 (VNVT)* ,即由终结符或（与）非终结符组成的一符号串，允许是 空字 162.2 产生式文法和语言例如：简单的汉语句子的构成规则
9、:= := | := 我 | 你 | 他 :=王明| 大学生|工人|英语 := :=是 |学习 := | 则 “我是大学生”是句子17文法的形式定义S 开始符号，即文法的第一个非终结符。开始符号代表了所定义的语言中我们最感兴趣的语法范畴，如在程序 语言中，我们感兴趣的是“程序”注意：1、 VN VT 即不含公共元素 ；2 、产生式是有限的；3、开始符号S至少必须在某个产生式的左部出现一次； 4、为书写方便，若干个左部相同的产生式如：P1, P2，Pn 合并成： P1|2|n其中i称为P的一个候选式。18文法定义举例1例2.1 表示算术表达式的文法描述：G1 =（VN，VT，P，S ） 其中VN
10、EVT =i , +,*, ( , ) P=E i , E E + E , E E * E , E ( E ) S=E或者直接写为：G1 =(E, i , +,*, ( , ) , E i , E E + E , E E * E , E ( E ) , E )19文法定义举例2例2 文法G =（VN，VT，P，S）其中VN标识符，字母，数字，VT a, b, c, , x, y, z, 0,1, , 8, 9P= | | , a|b|c|x|y|z, 0|1|2|8|9S = 20用文法定义语言的中心思想是：从文法的开始符号出 发，反复连续使用产生式，对非终结符施行替换和展开 。例如文法G：E
11、 E+E | E*E | ( E ) | i，其中唯一非终 结符E可以看成是代表一类算术表达式。从E出发，进行一系列的推导，推出种种不同的算术 表达式。如根据上述规则可推出 ( i+i )：E = ( E )= ( E+E )= ( i+E )= ( i+i)我们称这样的一串替换是从E推出( i+i )的一个推导，这个 推导提供了一个证明，证明( i+i )是文法G所定义的一个 算术表达式。2.2.2 文法的推导21有关推导的定义定义2.3 直接推导 =若A直接推导出 ，即 A=，当且仅当A- 是一个产生式，且、(VNVT)*符号 =指推导一步，即推导每前进一步总是引用一 条规则（产生式）定义
12、2.4 长度为n（n1）的推导若存在直接推导序列a1= a2= =an，则称a1可推导出an。a1 an 表示：从a1出发经过一步或若干步，可推导出an 。定义2.5 长度为n（n0）的推导a1 an 表示：从a1出发经过0步（ a1 an ）或若干步，可推导出 an 。222.2.3 句型、句子、语言例1：证明终结符号串( i*i+i )是文法G：E E+E | E*E | (E)| i的一个句子证明： E =( E ) =(E+E)=(E*E+E) =(i*E+E) =(i*i+E)=(i*i+i) 是从开始符号E到( i*i+i )的一个推导。其中E、(E)、(E+E)、(E*E+E)、
13、 (i*E+E) 、 (i*i+E) 、 (i*i+i)都是这个文 法的一个句型1.句型：设GS是一个文法，S是它的开始符号，若S , 则称是文法GS的句型。2.句子：仅含终结符的句型是一个句子，即S ，VT*, 则是句子。3.语言：文法G所产生的句子的全体是一个语言，记作 L(G)L(G)=|S ,且VT*23语言的例子例2：文法G2 A ：A bA | cc，证明cc、bcc、bbcc属于L(G2)。证明： A=cc， A= Ba=bcc， A =bA =bbA = bbcc cc、bcc、bbcc、是属于L(G2)的例3：文法GS： (1) S0S1；(2) S01。GS的语言是什么？解
14、：对第一个产生式使用n-1次，然后使用第二个产生式一次，得到 ：S = 0S1 = 00S11= = 0n-1S1n-1 = 0n1n因此L(G)=0n1n|n 1 例4：下列文法的语言是什么？GS=（S, , S - , S ）GA=（A， ， ，A ）242.2.4 文法的等价若L(G1) = L(G2)，则称文法G1和G2是等价的例1：G1=(VN, VT, P, S)， VN =S， VT =0, 1，P由下列产生式组 成：(1) S0S1； (2) S01；G2=(VN, VT, P, A)， VN =A, R， VT =0, 1，P由下列产生式 组成：(1) A 0R ; (2) A 01; (3) R A125什么是递归文法？1.递归规则：规则右部有与左部相同的符号对于 U - xUy若x=,即U - Uy，左递归；若y=,即U - xU，右递归；2.递归文法：文法G，存在U VN若 U=U, 则G为递归文法；若 U=U, 则G为左递归文法；若 U=U, 则G为右递归文法；264. 递归文法的优点：可用有穷条规则，定义无穷语言例：对于前面给出的标识符的文法是有递归文法，用y 有限条规则就可以定义出所有的标识符。若不用递归文 法，那将要用多少条规则呢？!3. 左递归文法
