《编译原理(第二版)第3章 文法和语法》由会员分享，可在线阅读，更多相关《编译原理(第二版)第3章 文法和语法（49页珍藏版）》请在金锄头文库上搜索。
1、第3章 文法和语言,教学要求：本章是编译原理课程的理论基础，要求理解文法、语言、规范推导、规范归约和短语、简单短语、句柄的基本概念；掌握语言的求解方法、文法的二义性的判断方法及句型的分析方法。 教学重点：上下文无关文法，语言定义,一、语言,语言是由句子组成的集合，是由一组记号所构成的集合。,汉语-所有符合汉语语法的句子的全体 英语-所有符合英语语法的句子的全体 程序设计语言-所有该语言的程序的全体,“我是大学生”是否是该语言的句子？,句子:=主语谓语 主语:=代词|名词 代词:= 你 | 我 | 他 名词:= 王明 | 大学生 | 工人 | 英语 谓语:=动词直接宾语 动词:= 是 | 学习
2、直接宾语:=代词|名词,二、文法,一种语言描述工具，用来定义句子的结构，用有限的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。,句子 主语谓语代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,句子:=主语谓语 主语:=代词|名词 代词:= 你 | 我 | 他 名词:= 王明 | 大学生 | 工人 | 英语 谓语:=动词直接宾语 动词:= 是 | 学习 直接宾语:=代词|名词,三、符号和符号串,字母表：元素的非空有穷集合。（符号集） 符号：字母表中的元素。,例如： 汉语的字母表中包括汉字、数字及标点符号等。 C语言的字母表是由字母、数字、若干专用符号及IF
3、、FOR之类的保留字组成。,任何一种语言可看成是某个符号集上定义的，按一定规则构成的一切基本符号串组成的集合。,符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。 形式定义: 1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3.y是上的符号串,当且仅当它可以由1和2导出。 例如： =a,b ,a,b,aa,ab,aabba,都是上的符号串 注意： 符号串中的符号排列是有顺序的。常用大写字母表示符号串，如 x=aaca,如果 z = xy 是一符号串，那么： 1、x 是 z 的头，y 是 z 的尾； 2、如果 x 非空，那么 y
4、 是固有尾；如果 y 非空，那么 x 是固有头。,例： 设 z = abc, 那么 z 的头是： ,a ,ab , abc（除 abc 外都是固有头） z 的尾是： ,c ,bc , abc（除 abc 外都是固有尾）,4、符号串的运算 符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 的长度为0 符号串的连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 例 x=ST,y=abu 则 xy=STabu |x|=2,|y|=3,|xy|=5x = x= x,方幂：符号串x自身连接n次得到的符号串 xxxx(n个x)定义为 xn x0=, x1=x, x2=xx,
5、 x3=xxx x=AB, 则 x0=, x1=AB, x2=ABAB, x3=ABABAB 对于 n0, xn = xxn-1 = xn-1x,5、符号串集合若集合A中一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 两个符号串集合A和B的乘积定义为 AB=xy|xA且yB若集合A=a,b B=c,d则 AB=ac,ad,bc,bdA=A=A(x=x=x) 使用*表示上的所有有穷长的串（包括）的集合。*称为的闭包。 从*中除去得到的集合记为+ 。 +称为的正闭包。,* = 0 1 2 n + = 1 2 n * = 0 + + = * = * + = * -,例：设=0,1，则
6、 * =, 0, 1, 00, 01, 10, 11, 000, 001, 010, 例：设=a,b，则*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,四、文法和语言的形式定义,1、文法的形式定义 1）规则（重写规则、产生式或生成式）：是一个有序对（，）。记为或=，其中V+，V* 。 称为规则的左部(或生成式的左部)。 称为规则的右部(或生成式的右部)。,2）文法GS：文法为四元组（VN，VT，P，S）VN ：非终结符集VT ：终结符集P：产生式（规则）集合S：开始符号（识别符号） VN、VT 和 P 是非空有穷集。S 至少在一条规则中
7、作为左部出现。 VNVT=， SVN V=VNVT，称为文法G的字母表（字汇表）,例3.1 文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,例3.2 文法G=（VN，VT，P，S）VN =标识符，字母，数字VT =a,b,c,x,y,z,0,1,9P=a, z0, 9S=,习惯上只将产生式写出。并有如下约定： 第一条产生式的左部是开始符号 用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符 G可写成GS，其中S是开始符号,例3.1 文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P
8、= S0S1, S01 S为开始符号,可写成：G：S0S1S01,或写成：GS：S0S1S01,Mini_C 介 绍Mini_C语言是在C语言的基础上定义的一种语言（C语言的子集），它的文法定义如下：1 := MAIN() 2 := | 语句串 3 := | 4 := ; 5 := int | char | real 6 := ;|; 7 := | | ,8 := =9 := if () | if () else10 := | 11 := while ()12 := for ( ; ; )13 := 14 := |=| := +| - |,3、推导的定义,1）直接推导“”是文法G的产生式，,V
9、*，若将作用于 v=得到 w=,则记作 vw，读作v（应用规则）直接产生w（w是v的直接推导或w直接归约到v）,例：G：S0S1，S01 直接推导： 0S10011（v=0S1，w=0011，使用规则S01，=0，=1） S0S1（v=S，w=0S1，使用规则S0S1，=，=） 0S100S11（v=0S1，w=00S11，使用规则S0S1，=0，=1）,2）长度为n的推导（有限次推导）若存在v =w0 w1 . wn=w, (n0)，则称v推导出w（或w归约到v）. 记作 v w。 3）若有v w，或v=w，则记为v w,+ ,+ ,* ,4、文法的句型、句子的定义,例：G： S0S1， S
10、01S 0S1 00S11 000S111 00001111,3）语言,由文法G产生的所有句子组成的集合叫做文法G所成描述的语言，记为L(G)。,例：G： S0S1， S01L(G)=0n1n|n1注：产生式中含有递归式，产生的句子是无穷的,例3.3 文法GS：（1）SdAB（2）AaA（3）Aa（4）BBb（5）B,L（G）=?,G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成,例：构造生成语言L= 的文法。,分析：n1，所以必须用递归规则。a和b的个数 一样多，但c的个数不同，所以将生成含 a,b的部分与生成含e的部分分开，A生成 ab，B生成e.GZ:ZABAaAb|abB
11、eB|,4)文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。,如文法G1A：A0R 与 G2S：S0S1 等价A01 S01RA1,五 文法的类型,（1）0型文法(短语文法）：对任一产生式，都有(VNVT)+， (VNVT)*（2）1型文法(上下文有关文法)：对任一产生式，都有|， 仅仅 S除外。即1A212(A在VN中，其他在V*中，) （3）2型文法（上下文无关文法）：对任一产生式，都有VN ， (VNVT)*即A(A在VN中，在V*中，) （4）3型文法（正规文法）：任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT,例：1型（上下文有关）文法文法GS：
12、SaSBESaBEEBBEaBabbBbbbEbeeEee,例：2型（上下文无关）文法文法GS： SaB|bAAa|aS|bAABb|bS|aBB文法GS： S0A|1B|0A0A|1B|0SB1B|1|0,例：定义标识符的3型（正规）文法文法GI： I lTI lT lTT dTT lT d,文法和语言,0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CFL ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言或正则（正规）语言（
13、 RL ）,六 上下文无关文法及其语法树,上下文无关文法有足够的能力描述现今程序设计语言的语法结构。 算术表达式 语句 赋值语句 条件语句 循环语句 ,1、语法树与推导,用于描述上下文无关文法的句型推导的直观方法,例: GS:SaASASbAASSSaAba,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。 从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,推导过程中施用产生式的顺序,例: GS:SaASASbAASSSaAba,Sa A SS b A aa b a,句型aabbaa的语法树（推导树）,SaASaAaaSbAaaSbba
14、aaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,2、最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换。 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型。,SaASaAaaSbAaaSbbaaaabbaa（最右推导） SaASaSbASaabASaabbaSaabbaa（最左推导） SaASaSbASaSbAaaabAaaabbaa,例: GS: SaAS ASbA ASSSa Aba,问题：一个句型是否对应唯一的一棵语法树？,例：GE: E iE E+EE E*EE (E),句型 i*i+i 的两个不同的最左推导：,推导2：E E*E i*E i*E+E i*i+E i*i+i,
