《【考研计算机专业课】天津大学编译原理PPT课件Part4语法分析》由会员分享，可在线阅读，更多相关《【考研计算机专业课】天津大学编译原理PPT课件Part4语法分析（41页珍藏版）》请在金锄头文库上搜索。
1、Part4语法分析,语法分析器的作用,以语法分析器为核心的编译器模型,语法分析器的作用,接收词法分析器提供的记号串 检查记号串是否能由源程序语言的文法产生 用易于理解的方式提示语法错误信息，并能从常见的错误中恢复过来,语法分析器工作原理,语言的结构是用上下文无关文法描述的，因此，语法分析器的工作本质上就是按照文法的产生式，识别输入符号串是否为一个句子。 语法分析器是从左向右的扫描输入字符串，每次读入一个符号，并判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串匹配的语法分析树。 语法分析器分类 通用的语法分析方法，用来分析任何文法，生成编译器时效率太低
2、 编译器使用的语法分析方法处理文法的一些子类 自顶向下（建立分析树）LL文法，其分析器常用手工实现 自底向上（建立分析树）LR文法，其分析器常利用自动生成工具构造,自顶向下分析面临的困难,自顶向下分析面临的困难,自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法的开始符号（根结）出发，自顶向下的为输入串建立一棵语法树。 或者说，为输入串寻找一个最左推导。 这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 自顶向下分析的一般方法是带“回溯”的。,自顶向下分析的简单例子,假定文法GS，以及输入串x*y（记为）。 SxAy A*|* 初始化：第一步扩展,S,
3、x*y,IP,S,x*y,IP,y,A,x,自顶向下分析的简单例子,假定文法GS，以及输入串x*y（记为）。 SxAy A*|* 第二步扩展：回溯,x*y,IP,S,x*y,IP,y,A,x,*,*,S,y,A,x,*,自顶向下分析面临的困难,文法的左递归性问题。含有左递归的文法将使上述的自顶向下的分析过程陷入无限循环。因此，我们要使用自顶向下分析法必须要消除文法的左递归。 由于回溯，就碰到一大堆的麻烦事情。如果我们走了一大段错路，最后必须回头，那么，就应把已经作的一大堆语义工作（指中间代码生成工作和各种表格的簿记工作）推倒重来。这些事情既麻烦又费时间，所以，最好设法消除回溯。 在上述的自顶向
4、下分析过程中，当一个非终结符用某一候选 匹配成功时，这种成功可能是暂时的。 当最终报告分析不成功时，难于知道输入串出错的确切位置。 由于带回溯的自顶向下分析方法实际上采用了一种穷尽一切可能的试探法，因此效率很低。,LL(1)分析法,消除左递归,直接左递归的消除,PP | ,PP PP | ,EE+T | TTT*F | FF(E) | i,ETE E+TE | ,TFT T*FT | ,F(E) | i,消除左递归的算法,如果一个文法不含回路（形如P=+P的推导），也不含以为右部的产生式，那么执行下述算法将保证消除左递归（但改写后的文法可能含有为右部的产生式）。 把文法G的所有非终结符按任一种
5、顺序排列成P1,P2,Pn；按此顺序执行： FOR i := 1 TO n DOBEGINFOR j:= 1 TO i-1 DO把所有形如PiPj的规则改写为：Pi1 | 2| | k。其中Pj1 | 2 | | k是关于Pj的所有规则；消除关于Pi的直接左递归END 化简由第2步得到的文法。即去除那些从开始符号出发永远无法到达的非终结符的产生式规则。,消除左递归的例子,SQc | c QRb | b RSa |a,RSa |a,QSab | ab | b,SSabc | abc | bc | c,SabcS | bcS | cS SabcS | ,RSa |a,QSab | ab | b,S
6、abcS | bcS | cS SabcS | ,SQc | c QRb | b RbcaR |caR | aR RbcaR | ,消除回溯、提取左因子,为了消除回溯就必须保证： 对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应该是确信无疑的。 也就是说，若此候选获得成功匹配，那么这种匹配决不会是虚假的；若此候选无法完成匹配任务，则任何其他候选也肯定无法完成。 假定现在轮到非终结符A区执行匹配（或称识别）任务，A共有n个候选1, 2, , n，即A1 | 2 | | n。 A所面临的第一个输入符号为a，如果A能够根据
7、不同的输入符号指派相应的候选i作为全权代表去执行任务，那就肯定无需回溯。 在这里已不再是让某个候选去试探性的执行任务，而是根据所面临的输入符号准并的指派唯一的一个候选。,消除回溯、提取左因子,令是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST()为： FIRST()=a | =*a, aVT 若=*，则规定FIRST() FIRST()是的所有可能推导的开头终结符或可能的 如果非终结符的所有候选首符集两两不相交，即的任何两个不同候选i和 FIRST(i) FIRST(j)= 那么当要求匹配输入串时，就能根据它所面临的第一个输入符号，准确的指派某一个候选前去执行任
8、务。这个候选就是那个终结首符集含的。,消除回溯、提取左因子,提取左因子的方法 假定的规则是：1 |2 | |n |1 |2 | |m（其中，每个不以开头） 那么这些规则可以改写为：AA |1 |2 | |mA1 |2 | |n 经过反复提取左因子，就能够把每个非终结符（包括新引进者）的所有候选首符集便成为两两不相交。我们为此要付出的代价是大量引进新的非终结符和产生式。,LL(1)分析条件,ETE E+TE | TFT T*FT | F(E) | i,对输入串i+i进行自顶向下分析,E,i + i,IP,T,E,iFIRST(TE),E,i + i,IP,T,E,iFIRST(FT),F,T,E
9、,i + i,IP,T,E,iFIRST(i),F,T,i,LL(1)分析条件,ETE E+TE | TFT T*FT | F(E) | i,对输入串i+i进行自顶向下分析,E,i + i,IP,T,E,+不属于T的任一候选式的首符集,F,T,i,E,T,E,F,T,i,+,T,E,F,T,i,LL(1)分析条件,只有当a是允许在文法的某个句型中跟在A后面的终结符时，才可能允许A自动匹配成功，否则，a在这里的出现就是一种语法错误。 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义 FOLLOW(A)=a | S=*Aa，aVT 特别是，若S=*A，则规定#FOLLOW(A)。换句话说
10、，FOLLOW(A)是所有句型中出现在紧接A之后的终结符或“#”。 当非终结符A面临输入符号a，且a不属于A的任意候选首符集但A的某个候选首符集包含时，只有当aFOLLOW(A)时，才可能允许A自动匹配。,LL(1)分析条件,通过上面的讨论，我们可以找出满足构造不带回溯的自顶向下分析的文法条件。 文法不含左递归 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A1 |2 | |n，则FIRST(i)FIRST(j)= (ij) 对文法中的每个非终结符A，若它存在某个候选首符集包含，则，FIRST(A)FOLLOW(A)= 如果一个文法G满足以上条件，则称该文法G为LL(1)
11、文法。 这里LL(1)中的第一个L表示从左到右扫描输入串，第二个L表示最左推导，1表示分析时每一步只需向前查看一个符号。,LL(1)分析条件,对于一个LL(1)文法，可以对其输入串进行有效的无回溯的自顶向下分析。 假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A1 |2 | |n 若aFIRST(i)，则指派i去执行匹配任务。 若a不属于任何一个候选首字符集，则： 若属于某个FIRST(i)，且aFOLLOW(A)，则让A与自动匹配； 否则，a的出现是一种语法错误。 根据LL(1)文法的条件，每一步这样的工作都是确信无疑的,递归下降分析程序构造,扩充的巴科斯范式,前面的巴科斯
12、范式只用到了两个元符号“”和“|” 扩充几个元语言符号： 用花括号表示闭包运算*。 用n0表示可任意重复0次至n次。00=0=. 用方括号表示10，即表示的出现可有可无（等价于 |）。 例如，通常的“实数”可定义为：decimalsigninteger.digitexponentexponentEsignintegerintegerdigitdigitsign+ | -,递归下降分析程序的构造,当文法满足LL(1)条件时，我们就可以为它构造一个不带回溯的自顶向下分析程序，这个分析程序是由一组递归过程组成的。每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。,EE+T | T
13、 TT*F | F F(E) | i,ET+T TF*F F(E) | i,递归下降分析程序构造,ET+T TF*F F(E) | i,PROCEDURE E; BEGINT;WHILE SYM = + DOBEGIN ADVANCE; T END END,PROCEDURE T; BEGINF;WHILE SYM = * DOBEGIN ADVANCE; F END END,预测分析程序,预测分析程序工作过程,实现LL(1)分析的另一种有效方法是使用一张分析表和一个栈进行联合控制。下面要介绍的预测分析程序就是属于这种类型的LL(1)分析器。,预测分析表,预测分析表示一个MA,a形式的矩阵。其
14、中A为非终结符，a是终结符或# 。 矩阵元素MA,a中存放着一条关于A的产生式，指出当A面临输入符号a时所应采用的候选。 MA,a中也可能存放一个“出错标志”，指出A根本不该面临输入符号a。,预测分析过程概述,预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a行事的。如下图所示，对于任何(X,a)，总控程序每次都执行下述三种可能的动作之一： 若X = a = #，则宣布分析成功，停止分析过程。 若X = a #，则把X从STACK栈顶弹出，让a指向下一个输入符号。 若X是一个非终结符，则查看分析表M。 若MX,a中存放着关于X的一个产生式，那么，先把X弹出STACK栈
15、顶，然后把产生式的右部符号串按反序一一推进STACK栈（若右部符号为，则意味着不推什么东西进栈）。 在把产生式的右部符号退进栈的同时应该做这个产生式对应的语义动作（目前暂且不管）。 若MX,a中存放着“出错标志”，则调用出错诊断程序ERROR。,预测分析过程举例,i1*i2+i3,步骤,符号栈,输入串,所用产生式,0,#E,i*i+i#,1,#ET,i*i+i#,ETE,2,#ETF,i*i+i#,TFT,3,#ETi,i*i+i#,Fi,4,#ET,*i+i#,5,#ETF*,*i+i#,T*FT,6,#ETF,i+i#,7,#ETi,i+i#,Fi,8,#ET,+i#,9,#E,+i#,T,10,#ET+,+i#,E+TE,11,#ET,i#,12,#ETF,i#,
