编译原理：文法和语言.ppt

1,第二章 文法和语言,2.1 文法的直观表示 2.2 符号和符号串 2.3 文法和语言的形式定义 2.4文法的类型 2.5 上下文无关文法及语法树 2.6 句型分析 2.7 文法的实用限制,2,第2章 文法和语言,【学习目标】 本章是为语言的语法描述寻求工具 掌握对程序设计语言给出精确、无二义（严谨、易读）的语法描述的手段之一文法。 对形式语言的理论有一个初步基础 根据文法的特点指导语法分析过程,3,2.1 文法的直观表示,文法：阐明语法的一个工具，也可以说是以有穷的集合刻画无穷的集合的一个工具。 语言：程序设计语言。 一、语言概述 语言是由符合语法的句子组成的集合。 汉语-所有符合汉语语法的句子的全体 英语-所有符合英语语法的句子的全体 程序设计语言-所有该语言的程序的全体 每个句子构成的规律语法 研究语言 每个句子的含义 语义 每个句子和使用者的关系语用,4,形式语言：只考虑语法而不考虑语义的符号语言。 每种语言具有两个可识别的特性 语言的形式 与该形式相关联的意义 “形式”指语言的所有规则，描述出现什么符号串 语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。 形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。,5,表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述 例：汉语句子的构成规则： 句子=主语谓语 主语=代词|名词 代词= 我 | 你 | 他 名词= 王明 | 大学生 | 工人 | 英语 谓语=动词直接宾语 动词= 是 | 学习 直接宾语=代词|名词,二、文法的直观概念,6,推导：“我是大学生” 是汉语的一个句子 句子 主语 谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,7,2.2 符号与符号串,一、相关概念 程序设计语言是由程序构成的集合，程序是由基本符号按照一定的规则构成的集合。 1. 符号、字母表和符号串 基本符号：可以相互区别的基本元素，如字母，数字，标点符号。 字母表：基本符号的非空有穷集合，常用表示。例： =0,1， =a, b, c, , x,y, z,8,符号串：由字母表中的符号构成的任何有穷序列称为符号串。符号串中的符号是有顺序的。,例如 =0,1上的符号串0, 1, 00, 01, 11, 10 注意：表示空符号串,它表示不包含任何符号串，不是空格符。,符号串集合：字母表上若干个符号串组成的集合. 例：字母表=0,1 的符号串集合A=1, 00, 01; 约定：小写字母 a,b,r表示符号. 小写字母 s,t,z表示符号串;,9,符号串s的头（前缀）和尾（后缀） ： 如果s=xy是一符号串，那么x是s的头，y是s的尾。若x是非空，则y是固有尾；若y非空，则x是固有头。 前缀：移走符号串s尾部的零个或多个符号得到的串。 如：设s=abc,那么s的前缀是，a，ab，abc 后缀：移走符号串s头部的零个或多个符号得到的串。 如：s =abc的后缀是，c，bc，abc，s的固有尾是，c，bc。,10,符号串s的子串： 从s中删去任何前缀或后缀得到的串. 如:bc是符号串abc的一个子串. 对符号串s， s和两者都是符号串s的前缀、后缀和子串。 符号串s的真前缀，真后缀，真子串： 任何非空符号串 x，是s的前缀，后缀或子串，并且 s x,11,2.符号串的运算 (1)符号串相等： 符号串x，y，如果两者诸符号依次相等，则两符号串相等。 (2)符号串的长度：符号串中包含符号的个数。 |abc|=3；| |=0； (3)符号串的连结： x=abc，y=def 则xy=abcdef；yx=defabc； xy yx x=x =x；,12,(4)符号串集合的乘积： 设A、B为两个符号串集合，其乘积为AB=xy|x A，yB； 例：A=aa，bb，B=cc，dd，则 AB=aacc，aadd，bbcc，bbdd A=A =A； (5)空集： 不含任何元素的集合称为空集。记为； 对任何集合A：A = A= ; 注意： ,13,(6)符号串的方幂： x是字母表上的符号串，则x的幂运算为： x0= ; x1= x; x2= xx; xn= xn-1x=x xn-1 (n0) xn表示n个x相连结。 eg：x=ok；则 x0= ; x1= ok; x2= okok; (7)符号串集合的方幂： A为符号串集合，则A的幂运算为： A0=; A1=A; A2=AA;. An= An-1A=AAn-1;(n0) A=aa，bb，则A0=； A1=aa，bb； A2=AA=aaaa，aabb，bbaa，bbbb;.,14,(8)符号串集合的闭包和正闭包 集合A的闭包表示为A*（亦称为自反闭包或星闭包）定义为： A*=A0 A1 A2 A3 =Ak， k0 正闭包表示为A+具体定义为 A+=A1 A2 A3 =Ak， k1 由定义可以看到A*= A0 A+,例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,15,3、语言 (1)由一组符号所构成的集合。即： 字母表上的每个语言是*的一个子集。 例如：字母表=a,b，*=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,aaabbb,anbn, 或表示为w|w*且w=anbn,n1为字母表上的一个语言。 集合a,aa,aaa, 或表示为w|w*，且w=an，n1 为字母表上的一个语言。 (2) 是一个语言。 (3) 即 是一个语言。,16,2.3 文法和语言的形式定义,如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途径：,生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一个任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去。）,17,一、规则（重写规则、产生式或生成式）,规则是形如或=的(，)有序对， 其中 V+， V*中的一个符号 称为规则的左部 称作规则的右部。 例： 文法可利用规则来描述。,18,二、文法的定义,1、文法G定义为四元组(VN，VT，P，S )其中VN ：非终结符号；VT：终结符号集；P：规则集合；VN，VT和P是非空有穷集。 S：开始符或识别符，是一个非终结符，至少要在一条规则的左部出现。 VN VT = ，V=VN VT ，V称为文法G的字母表,例1：文法G = (VN，VT，P，S)， 其中 VN=S， VT=0，1， P=S0S1，S01。,19,文法G习惯上只将规则写出。 如例1还可以写成： G：S0S1 S01 或GS：S0S1 S01 或GS：S0S1 | S01,20,总结一个文法的几种写法 G=(S,A，a,b，P，S) 其中P：SaAb Aab AaAb A G：SaAb Aab AaAb A GS： S aAb Aab AaAb A GS： SaAb Aab |aAb |,21,三、推导的定义,用文法定义语言的中心思想是：从文法的开始符号出发，反复使用合适规则，对非终结符施行替换和展开。 1、直接推导： 是文法G的产生式，若有v，w满足：v =，w = , 其中V*,V*。则称v直接推导到w,或w直接归约到v记作 vw， 2、推导：如果存在直接推导的序列：v=W0 W1 W2 Wn=w,(n0)；称v推导出w(推导长度为n)，或称w归约到v。 记作v w。 若有v w，或v=w，则记作v w ，(n=0),*,22,例3：G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1 00S11 000S111 00001111 S 00001111 S S 00S11 00S11,+,*,*,23,3、规范推导 最左(最右)推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换 最右推导被称为规范推导。 例4：GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a（最左推导） EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a （最右推导）,24,四、句型、句子和语言的定义,1.句型:文法GS，若S x，则称x是G的句型。 2.句子:文法GS，若S x，且xVT*，则称x是G的句子。句子是句型的特殊，只包含终结符。 例5：G：S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型S, 0S1 ,00S11 ,000S111,00001111 G的句子00001111 3.语言:文法G的一切句子的集合, 记为L(G)，,*,*,25,例 6 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee SanBnEn anbnen 则 L（G）= anbnen | n1 因为San-1S（BE）n-1 an（BE）n ，继续推导时，将用规则(3)(7)替换,*,*,26,S a S BE (SaSBE) a aBEBE (SaBE) aabEBE ( aBab ) aabBEE ( EBBE ) aabbEE （bBbb) aabbeE （bEbe) aabbee （eEee) G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成,27,五、语言和文法,给定一个文法，能从结构上唯一确定其语言 给定一个语言，不能唯一确定其文法，即一个语言可有多个文法与之对应 已知语言描述，写出文法，应满足： 所描述的语言的任何句子都能由该文法产生 该文法推导不出不是已知语言的任何句子 已知文法，写出语言描述，应满足： 该文法能推导出的任何句子都包含在所描述的语言中 描述的语言中不包含该文法推导不出的句子,28,六、文法的等价,若L（G1）=L（G2），称文法G1和G2是等价的 如文法G1A：A0R 与G2S：S0S1 等价 A01 S01 RA1 作业：P47:1，4，5,29,2.4 文 法 的 类 型,一、文法分类 通过对产生式施加不同的限制，将文法分为四类 设有文法G=(VN，VT，P，S); 0型文法：（短语结构文法）图灵机 对任一产生式，都有(VNVT)+，且至少包含一个非终结符，(VNVT)* 1型文法：（上下文有关文法） 对任一产生式，都有|， 仅仅 S除外。,30,文法GS是1型文法 SaSBC| aBC CB DB DB DC DCBC aBab bBbb bCbc cCcc SaSBC aaBCBC aabCBC aabbcc,*,31,2型文法：（上下文无关文法） 对任一产生式，都有VN ，(VNVT)* 设文法G(VN,VT,P,S)是一个2型文法， VN S,A,B, VT a,b 其中P为: (0) S aB (1) S bA (2) A a (3) A aS | bAA (4) B b (5) B bS | aBB,32,3型文法：（正规文法） 右线性文法 任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT(a可为) 左线性文法 任一产生式的形式都为ABa或Aa，其中AVN ，BVN ，aVT(a可为),33,例：GE： EE+T|T TT*F|F F(E)|a G是上下文无关文法。 例文法G=(S,A,B,0,1,P,S)，其中P由下列产生式组成： S0A A1B S1B B1B S0 B1 A0A B0 A0S G是正规文法。,34,二、四类文法之间的关系,四种文法之间的逐级“包含”关系,35,2.5 上下文无关文法及其语法树,上下文无关文法有足够的能力描述程序设计语言的语法结构 例:文法GE：Ea|E+E|E*E|(E) E表示算术表达式, a表示程序的“变量”， 该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构,句型推导的直观表示-语法树,36,设G为一上下文无关文法，若一棵树满足下列4个条件，则称作G的语法树(推导树，派生树） 1. 每个结点都有一个标记，此标记是V的一个符号 2. 根的标记是 文法开始符号S 3. 如果结点n至少有一个除自己外的子孙并有标记A，则肯定AVN 4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式 语法树的结果： 从左到右读出叶子的标记而构成的行,一、语法树,37,GE： EE+T|T TT*F|F F(E)|a EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,E,E,+,T,E,E,+,T,T,E,E,+,T,T,F,E,E,+,T,T,F,a,T,*,F,F,a,a,给定文法G=(VN, VT, P, S)，对于G的任何句型都能构造与之关联的语法树(推导树),38,用于描述上下文无关文法句型推导的直观方法,叶子结点：树中没有子孙的结点。 从左到右读出推导树的叶子标记连接成的文法符号串，为GS的句型。该推导树称为该句型的语法树。,用于描述上下文无关文法句型推导的直观方法,用于描述上下文无关文法句型推导的直观方法,例: GS: SaAS ASbA ASS Sa Aba,用于描述上下文无关文法句型推导的直观方法,句型aabbaa的语法树（推导树）,39,推导过程中施用产生式的顺序,例: GS: SaAS ASbA ASS Sa Aba,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,40,例：GE： EE+T|T TT*F|F F(E)|a 试给出表达式a+a*a的推导，并画出语法树。 左: EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a 右: EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a 混合: EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a,41,例如，有一个2型文法 G= (S,A,B,a,b,P,S), 其中P: (0) S aB|bA (1)A a|aS|bAA (2)B b|bS|aBB 采用最左推导产生句子aabbab: S aB aaBB aabSB aabbAB aabbaB aabbab,一棵语法树表示了一个句型的种种可能的不同推导过程，一个句型是否只对应唯一的一棵语法树呢? 是否只有唯一的一个最左(最右)推导呢?,42,语法树 其中P: (0) S aB|bA (1)A a|aS|bAA (2)B b|bS|aBB 分析句子aabbab,43,例：GE: E a E E+E E E*E E (E),句型 a*a+a 的两个不同的最左推导： (1)EE+EE*E+E a*E+E a*a+E a*a+a (2)E E*E a*E a*E+E a*a+E a*a+a,44,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的 文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。,45,如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。 二义文法改造为无二义文法 GE: E a GE：E T|E+T E E+E T F|T*F E E*E F （E）|a E (E) 规定优先顺序和结合律,46,2.6 句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语言的编译实现中，完成句型分析的程序称为分析程序或识别程序。分析算法称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,47,一、句型的分析算法分类,分析算法可分为： 自上而下分析法： 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。 自下而上分析法： 从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 两种方法反映了两种不同的语法树的构造过程。,48,1、自上而下的语法分析,例：文法G：S cAd A ab A a 识别输入串w=cabd是否为该文法的句子,49,2、自下而上的语法分析,例：文法G： S cAd A ab A a 识别输入串w=cabd是否该文法的句子,S A A c a b d c a b d c a b d 规约过程构造的推导： cAd cabd S cAd,50,3、句型分析的有关问题,1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符是B，且有n条规则：BA1|A2|An，如何确定用哪个右部去替代B？ 2）自下而上分析法中，分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符，该子串称为“可归约串”,如何识别可归约串？ 3）存在确定和不确定分析，本课只讨论确定分析,51,4、短语、直接短语、句柄的定义,对于文法GS （1）句型的短语: S = A且 A =，则称是句型相对于非终结符A的短语。 （2）句型的直接短语：若有A ，则称是句型相对于非终结符A 的直接短语。 （3）句型的句柄：一个句型的最左直接短语称为该句型的句柄。,*,+,52,语法树子树分析法： 短语：任意一颗子树的叶子结点从左至右顺序排列的字符串（按给定句型排除）。 直接短语：只有父子两层的子树的叶子结点从左至右顺序排列的字符串。 句柄：最左最下的只有父子两层的子