编译原理(第二版)第3章文法和语法.ppt

第3章文法和语言,教学要求：本章是编译原理课程的理论基础，要求理解文法、语言、规范推导、规范归约和短语、简单短语、句柄的基本概念；掌握语言的求解方法、文法的二义性的判断方法及句型的分析方法。 教学重点：上下文无关文法，语言定义,一、语言,语言是由句子组成的集合，是由一组记号所构成的集合。,汉语-所有符合汉语语法的句子的全体 英语-所有符合英语语法的句子的全体 程序设计语言-所有该语言的程序的全体,“我是大学生”是否是该语言的句子？,句子:=主语谓语 主语:=代词|名词 代词:= 你 | 我 | 他 名词:= 王明 | 大学生 | 工人 | 英语 谓语:=动词直接宾语 动词:= 是 | 学习 直接宾语:=代词|名词,二、文法,一种语言描述工具，用来定义句子的结构，用有限的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。,句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,句子:=主语谓语 主语:=代词|名词 代词:= 你 | 我 | 他 名词:= 王明 | 大学生 | 工人 | 英语 谓语:=动词直接宾语 动词:= 是 | 学习 直接宾语:=代词|名词,三、符号和符号串,字母表：元素的非空有穷集合。（符号集） 符号：字母表中的元素。,例如： 汉语的字母表中包括汉字、数字及标点符号等。 C语言的字母表是由字母、数字、若干专用符号及IF、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 是固有尾；如果 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|=5 x = x= x,方幂：符号串x自身连接n次得到的符号串 xxxx(n个x)定义为 xn x0=, x1=x, x2=xx, 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,bd A=A=A(x=x=x) 使用*表示上的所有有穷长的串（包括）的集合。*称为的闭包。 从*中除去得到的集合记为+ 。 +称为的正闭包。,* = 0 1 2 n + = 1 2 n * = 0 + + = * = * + = * -,例：设=0,1，则 * =, 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 至少在一条规则中作为左部出现。 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,9 P= a, z 0, 9 S=,习惯上只将产生式写出。并有如下约定： 第一条产生式的左部是开始符号 用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符 G可写成GS，其中S是开始符号,例3.1 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,可写成： G：S0S1 S01,或写成： GS：S0S1 S01,Mini_C 介 绍 Mini_C语言是在C语言的基础上定义的一种语言（C语言的子集），它的文法定义如下： 1 := MAIN() 2 := | 语句串 3 := | 4 := ; 5 := int | char | real 6 := ;|; 7 := | | ,8 := = 9 := if () | if () else 10 := | 11 := while () 12 := for ( ; ; ) 13 := 14 := |=| := +| - |,3、推导的定义,1）直接推导“” 是文法G的产生式，,V*，若将作用于 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， S01 S 0S1 00S11 000S111 00001111,3）语言,由文法G产生的所有句子组成的集合叫做文法G所成描述的语言，记为L(G)。,例：G： S0S1， S01 L(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:ZAB AaAb|ab BeB|,4)文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。,如文法G1A：A0R 与 G2S：S0S1 等价 A01 S01 RA1,五 文法的类型,（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：SaSBE SaBE EBBE aBab bBbb bEbe eEee,例：2型（上下文无关）文法 文法GS：SaB|bA Aa|aS|bAA Bb|bS|aBB 文法GS：S0A|1B|0 A0A|1B|0S B1B|1|0,例：定义标识符的3型（正规）文法 文法GI：I lT I l T lT T dT T l T d,文法和语言,0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CFL ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言或正则（正规）语言（ RL ）,六 上下文无关文法及其语法树,上下文无关文法有足够的能力描述现今程序设计语言的语法结构。 算术表达式 语句 赋值语句 条件语句 循环语句 ,1、语法树与推导,用于描述上下文无关文法的句型推导的直观方法,例: GS: SaAS ASbA ASS Sa Aba,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,推导过程中施用产生式的顺序,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,2、最左（最右）推导： 在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换。 最右推导被称为规范推导。 由规范推导所得的句型称为规范句型。,SaASaAaaSbAaaSbbaaaabbaa（最右推导） SaASaSbASaabASaabbaSaabbaa（最左推导） SaASaSbASaSbAaaabAaaabbaa,例: GS:SaASASbAASS Sa Aba,问题：一个句型是否对应唯一的一棵语法树？,例：GE:E i E E+E E E*E E (E),句型 i*i+i 的两个不同的最左推导：,推导2：E E*E i*E i*E+E i*i+E i*i+i,推导1：E E+E E*E+E i*E+E i*i+E i*i+i,3、二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。 产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。,排除文法二义性的两种方法： （1）在语义上加些限制（如优先顺序和结合律）。 （2）重构无二义性的文法。,GE: E I E E+E E E*E E (E),GE: E T|E+T T F|T*F F （E）|i,练习：有文法GN： NSE|E S SD|D E 0|2|4|6|8|10 D 0|1|2|3|4|5|6|7|8|9 （1）证明此文法有二义性 （2）此文法描述的语言是什么？ （3）试写出另一文法，其产生的语言和GN产生的语言等价且是无二义性的。,七、句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。,1、自上而下的语法分析：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号串匹配的推导。,例：文法G：S cAd A ab A a识别输入串 w = cabd 是否该文法的句子,推导过程：,cabd,cAd,S,2、自下而上的语法分析：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,例：文法G：S cAd A ab A a识别输入串 w = cabd 是否该文法的句子,规约过程：,cabd,cAd,S,3、句型分析的有关问题,1）如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？ 2）如何识别可归约的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”（“句柄”）,4、短语、直接短语、句柄的定义： 文法GS，是G的一个句型，如果： S A且A 则称是句型相对于非终结符A的短语。 若有A 则称是句型相对于规则A的直接短语（或简单短语）。 一个句型的最左直接短语称为该句型的句柄。,* ,+ ,如何用语法树理解短语？ 1、语法树中一棵子树的所有叶子从左向右排列起来形成一个相对于子树根的短语。 2、只有父子两代的子树的叶子从左向右排列起来构成的短语称为直接短语。 3、最左直接短语称为句柄。,GE：EE+T|T TT*F|F F(E)|a 句型：a+a*F,短语：,句柄：,a1 。,直接短语：,a1,，a2,a1+ a2 * F，,a1,a2 *F,a2,八、有关文法实用中的一些说明,1、有关文法的实用限制 文法中不得含有有害规则和多余规则。 “有害规则”：形如UU的产生式。会引起文法的二义性。 “多余规则”：指文法中任何句子的推导都不会用到的规则。 1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达的。 2）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的。,化简文法,例：GS 1) SBe 2) BCe 3) BAf 4) AAe 5) Ae 6) CCf 7) Df,SBe BAf AAe Ae,C为不可终止,D为不可达到,2、上下文无关文法中的规则 具有形式A的规则称为规则，其中AVN 某些著作和讲义中限制这种规则的出现。因为规则会使有关文法的一些讨论和证明变得复杂 两种定义的唯一差别是句子在不在语言中。,