编译原理 课件 第三章 语法分析1.ppt

1、1,第三章 语法分析(1),文法和语言的形式化定义 自上而下分析方法 自下而上分析方法,2,3.1 文法和语言,语言概述 文法概述 形式语言分类,3,3.1.1 语言概述,一、语言 某一字母表上符号串（句子）的集合。 语言研究的三个方面： 语法构成语言句子的各个记号之间的组合规 律。 语义按照各种表示方法所描述的各个记号的 特定的含义。 语用在各个记号所出现的行为中，它们的来 源、使用和影响。,4,例如： = 0，1 V = a, b,cz A=begin,if,real,end,什么是符号与字母表？,字母表：由若干元素（符号、字母）所组成的有限非空集合。常用大写英文字母A,B 或希腊字母 表

2、示。 符号：可以相互区别的记号（元素）。,5,二、形式语言,Chomsky于1956年提出了一种用来描述语言的数学系统。人们把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言。 形式语言，只是从语法上研究语言。它是抽象的数学系统，用于模拟程序设计语言的语法，或者是并不很成功地模拟自然语言如英语的语法。 形式语言理论是编译理论的重要基础，它主要研究组成符号语言的符号串的集合及它们的表示法、结构与特性。,6,三、语言的描述方法,形式化描述 指定有限个规则，用于产生所要描述的语言的全部句子， 这些规则构成了该语言的文法。 自动机方法 建立一种装置（算法或过程），

3、它以某字母表上的符号 串为输入，判别该符号串是否为其所描述的语言的句子， 此装置即为自动机。,7,3.1.1 文法概述,引例1： := := := := :=Peter | Berry | river :=swims :=in 注：为要定义的目标，称为识别符号或开始符号。,8,引例2 有如下规则： A B C 0 1,请问：该规则可以产生什么语言？,9,规则的非空有穷集合，用GS表示，G是文法名， S是识别符号。文法通常表示成四元组的形式： G=(VN,VT,P,S) 其中：VN非终结符，用来表示语法范畴。 VT 终结符，语言中不可再分的基本符号。 S 开始符号或识别符号，一个特殊的非终 结符

4、，表示所定义的最大的语法范畴。 P 规则,文法的形式化定义,10,形式为U:=u （或Uu） 其中UV+且至少包含一个非终结符； uV* ；且 V=VNVT。 U称为规则（产生式）左部，u称为规则（产生式）右部。 非终结符号：需要进一步定义的符号，不会出现在程序中。 终结符号：不需要再定义，会出现在程序中。,问题1：什么是规则（产生式）？,11,注意： 1、VNVT=，即文法中的任意一个符号要么是非终结符，要么是终结符。 2、只用一个产生式并不足以定义一个语法范畴，一般都需要几个产生式，特别是需要含有递归的产生式。 3、开始符号至少必须在某个产生式的左部出现一次。,12,例3.1 试构造产生标

5、识符的文法。,IL|LS S T|ST T L|D L a|b|c|d|z|A|B|Z|_ D 0|1|9,13,例3.2 写一文法，使其语言是奇数集合，但不 允许出现以0开头的奇数。,N A|MA M B|MD A 1|3|5|7|9 B 1|2|3|4|5|6|7|8|9 D 0|B,14,问题2：如何由文法产生语言？,基本思想是：从识别符号开始，把当前产生的符号串中的非终结符号替换为相应规则右部的符号串，直到最终全由终结符号组成。这种替换过程称为推导或产生句子的过程，每一步称为直接推导或直接产生。 注：语法上的正确性不能保证语义上的正确性。,15,直接推导“” 设 是文法G的产生式，若有

6、v,w满足： v=x y, w= x y, 其中xV*, yV*, V=VTVN 则称v直接推导到w, 记作：v w 或w直接归约到v 例：G： S0S1， S01,S,0S1,00S11,000S111,00001111,16,说明 （1）如果1可直接推导出2， 2可直接推导出3， n-1可直接推导出n,即存在一个推导序列： 1 2 3 n-1 n 则称1 可以推导出n，记做1 + n。 （2）如果1 经过0步或若干步可以推导出n，记做1 * n。,17,小结：文法和语言的关系,已知描述语言，可以写出（凑出）相应的文法。 （注意：该文法并不惟一。） 已知文法，可以得到由该文法产生的语言。 （

7、用推导的方法得到的所有句子的集合。）,18,句型和句子,设GS是一文法，如果符号串是从识别符号S推导所得的，即 S * , (VTVN)* 则称符号串是文法G的一个句型。 如果句型仅由终结符号组成，即 S * , VT* 则称是文法G的句子。,例1：G： S0S1， S01 S 0S1 00S11 000S111 00001111,19,语言的形式定义,语言 对于文法GS,它所描述的语言是该文法产生的一切句子的集合。记做L(G)，即 L(G)= | S + ，其中S为文法开始符号，且 VT*,例1：G： S0S1， S01 L(G)=0n1n|n1,20,例2： 文法GS： （1）SaSBE

8、（2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee,L（G）= anbnen | n1 ,21,3.1.2 形式语言分类,Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类： 0型文法（PSG） 0型语言或短语结构语言 1型文法（CSG） 1型语言或上下文有关语言 2型文法（CFG） 2型语言或上下文无关语言 3型文法（RG）3型语言或正则（正规）语言,22,0型文法,如果对于某文法G，P中每个规则具有下列形式： 其中 V*VN V*， V*， V=VNVT 则该文法G为0型文法或短语结构文法，缩写为PSG。 相应的语言称为0型语言或短

9、语结构语言。 例文法GS： S0AB 1B0 BSA|01 A1SB1 A0S0B,23,1型文法,如果对于某文法G，P中每个规则具有下列形式： xAyxy 其中AVN，x, y V*， V+ ， 则该文法G为1型文法或上下文有关文法， 缩写为CSG。 例文法GS： SaSBE SaBE EBBE aBab bBbb bEbe eEee,24,2型文法,如果对于某文法G，P中每个规则具有下列形式： A 其中AVN， V* ， 则该文法G为2型文法或上下文无关文法，缩写为CFG。 例文法GE：E E+E|E*E|(E)|i 注意：程序设计语言的文法通常是上下文无关的。,25,3型文法（左线性文法

10、）,如果对于某文法G，P中每个规则具有下列形式： Aa 或 ABa 其中aVT*，A、BVN，则该文法G为3型文法或正则文法（正规文法），缩写为RG。 这种形式的正则文法称为左线性文法。 例文法GS：S Bc|Sc B Ab| Bb A Aa|a,26,3型文法（右线性文法）,如果对于某文法G，P中每个规则具有下列形式： Aa 或 AaB 其中aVT*，A、BVN，这种形式的正则文法称为右线性文法。 例文法GS： S lT S l T lT T dT T l T d,27,说明： （1）1型文法中不允许有形如“A”的产生式存在，而0、2、3型文法允许该种产生式存在。 （2）0、1型文法的产生式

11、左部存在含有终结符号的符号串或两个以上的非终结符，而2、3型文法的产生式左部只允许存在单个的非终结符号。 （3）0型文法的识别系统是图灵机；1型文法的识别系统是线性界限自动机；2型文法的识别系统是下推自动机；3型文法的识别系统是有限自动机。,28,（4）正规表达式可以转换为上下文无关文法，转换方法见课本P36。正规表达式也可以与正规文法之间进行转换。 （5）正规表达式用于描述程序语言的词法，上下文无关文法用于描述程序语言的语法。,为什么要用正规式定义词法 ？ 词法规则非常简单，不必用上下文无关文法。 对于词法记号，正规式描述简洁且易于理解。 从正规式构造出的词法分析器（有限自动机）效率高。,2

12、9,贯穿词法分析和语法分析的关键思想是： 1、语言的描述和语言的识别是表示语言的两个不同的侧面。 2、正规表达式适合于描述线性结构，如标识符、常数、注释等。 3、上下文无关文法适合于描述具有嵌套（层次）性质的非线性结构，如if、while语句等。,30,3.2 推导和语法树,推导、规范推导 短语、句柄、素短语 语法树 文法的二义性,31,【例】设有文法GN: N D|ND D0|1|2|3|4|5|6|7|8|9 则句子12可由三种不同的推导序列推导出来： (1) N ND N2 D2 12 (2) N ND DD 1D 12 (3) N ND DD D2 12,32,规范推导和规范归约 最左

13、推导和最右推导：对于一个推导序列中的每一步 直接推导，都是对最左（最右）非终结符进行替换。 最右推导也称规范推导，它的逆过程称为最左归约， 也称规范归约。,33,【例】文法GS: SAB AA0|1B B0|S1 请给出句子101001的最左和最右推导。,最左推导： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推导： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001,34,【例】有文法如下,GE：EE+T|T TT*F|F F(E)|i该文法的开始符号是？非终结符号集是？终结符号集是？如何得到句子i+i*i

14、?,EE+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*i,开始符号是E,非终结符号集是E、T、F,终结符号集是i、(、)、+、*,35,文法的递归性和等价性,文法的递归性定义：对于某文法，存在UVN， 如果U + U.， 则称该文法递归于U； 如果U + U，则称该文法左递归于U； 如果U + U，则称该文法右递归于U。 以上形式的规则（产生式）也称为递归规则。,36,【例】程序语言中， programdeclaration_list declaration_listdeclaration_list declaration | declaration,【例】程序语言

15、中， D TL T int |long |short L id| L,id,37,注：1、描述程序设计语言的文法必定都是递归的。,2、递归规则的存在，使得能用有穷个规则来 定义无穷的语言（的句子）。,38,文法的等价性定义：两个文法的规则不同，但产生的 语言却有可能完全相同，即L（G1）=L（G2），则称 文法G1和G2是等价的。 【例】下列两个文法G1A与G2S等价 G1A：A0R G2S：S0S1 A01 S01 RA1 L(G1) = L(G2) = 0n1n|n1,39,句型分析的相关基本概念,短语、直接短语、句柄、素短语 句型和句子 语法树和文法的二义性,40,短语和直接短语,设GS

16、是一个文法， w= 是该文法的一个句型， 如果有S * A， AVN , 且 A + ,V+, 则称是句型w中相对于A的短语。 如果有S * A ， A, 则称是句型w中相对于A的直接短语。,41,句柄,句型的句柄：一个句型的最左直接短语。 任何句型的句柄总是存在，且惟一。,【例】对于文法GS：SAB A Aa|bB B a|Sb 求句型baSb的全部短语、直接短语和句柄？,该句型的短语有Sb、a、ba及自身baSb ； 直接短语有Sb、a； 其中a为句柄。,42,练习 设有文法GS： SaAcBe A Ab|b B d 1、考虑句型aAbcde，判断b是否为其一个短语？ 2、求句型aAbcd

17、e的短语、直接短语和句柄。,短语：Ab、d、aAbcde 直接短语： Ab、d 句柄： Ab,43,素短语,含有终结符的短语，如果它不存在也具有同样性质的真子串，则该短语为素短语。,44,语法 分析器 在编译 过程中 的位置,45,语法分析器,语法分析器的输入 Token序列：词法分析产生的输出，是各个单词都正确的源程序，是一个有限序列。 语法分析器的功能 按照语言的语法构成规则, 识别输入的Token序列能否构成一个句子。规则是用文法的产生式来定义的。 对给定的输入单词串，如何判定它是不是一个句子？ 语法分析器的输出 分析树（语法树）：如何表示和构造语法树？ 错误处理信息：定位、继续编译,4

18、6,语法树,给定文法G，G=(VN,VT,P,S)，对于G的任何句型都能构造与 之关联的语法树（推导树）。这棵树具有下列特征： 1、根结点的标记是开始符号S。 2、每个结点的标记都是V（=VNVT）中的一个符号。 3、内部结点（非树叶结点）一定是非终结符，如果某内部结点A有n个分支，它的所有子结点从左至右依次标记为x1、x2、xn，则A x1x2xn一定是文法GS的一条规则。 4、如果某结点记为，则它必为叶结点且是其父结点的惟一子结点。 5、若树的所有叶结点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。,47,问题1：如何用语法树求短语、句柄

19、,短语：子树的末端结点组成的符号串是相对于子树根的短语。 直接短语：简单子树的末端结点组成的符号串是相对于简单子树根的直接短语。 句柄：最左简单子树的末端结点组成的符号串是句柄。 素短语：子树的末端结点组成的符号串含有终结符，且在该子树中不再有包含有终结符的更小子树。,48,【例】对于文法GS：SAB A Aa|bB B a|Sb 求句型baSb的全部短语、直接短语和句柄？,S,A,B,b,a,b,S,B,baSb为句型baSb的相对于S的短语； ba为句型baSb的相对于A的短语； a为句型baSb的相对于B的短语,且为直接短语和句柄； Sb为句型baSb的相对于B的短语,且为直接短语。,4

20、9,问题：语法树的构造过程,【例】有文法GS： SAB A aAb|ab B cBd|cd 对句子abccdd构造语法树。,50,S,S,B,A,S,B,B,d,A,c,S,B,B,d,A,c,d,c,S,B,B,d,b,a,A,c,d,c,（1）,（2）,（3）,（5）,（4）,GS：SAB A aAb|ab B cBd|cd 句子为abccdd,51,给出句型 i*i+i 的最左推导：,【例】表达式文法GE:E i E E+E E E*E E (E),思考：一个句子是否对应唯一的一棵语法树？,推导1：E E+E E*E+E i*E+E i*i+E i*i+i,推导2：E E*E i*E i*E+E i*i+E i*i+i,52,文法的二义性,如果一个文法中存在某个句子，对应有两棵 不同的语法树，则说明这个文法是二义的。,问题：如何消除二义性文法？,、不改变文法中原有的语法规则，仅加进一些语法的非形式规定。 、构造一个等价的无二义性文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。,53,如上例中,若采用方法1,不改变已有的规则,仅加 进运算符的优先顺序和结合规则。即“*”优先 于“+”，且“