编译原理第五章语法分析-自下而上分析.ppt

第五章 语法分析-自下而上分析,5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析法 5.4 语法分析器的自动产生工具YACC,5.1 自下而上分析基本问题,5.1.1 归约 5.1.2 规范归约简述 5.1.3 符号栈的使用与语法树的表示,5.1.1 归约,“移进-归约”法： 用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。 例子：假定文法G SaAcBe Ab AAb Bd 输入串abbcde归约到S过程。,图5.1 规约中符号栈的变迁,问题： 如果步骤5用规则(2)，而不是用规则(3)则会有不同的结果。这就是“可规约串”问题。对可规约串的刻画不同，分析的方法也不同，本课程讨论“最左素短语”和“句柄”两种可规约串刻画方法。,5.1.2 规范归约简述,短语、直接短语和句柄定义： 令G是一个文法，S是文法的开始符号，假定是文法的一个句型，如果有 S* A 且A+ 则称是句型相对于非终结符A的短语。特别是，如果有 A 则称是句型相对于规则A 的直接短语 一个句型的最左直接短语称为该句型的句柄。,利用句柄规约的例子： 句型 归约规则 abbcde (2)Ab aAbcde (3)AAb aAcde (4)Bd aAcBe (1)SaAcBe S,规范规约的一般定义： 假设是文法G的一个句子，我们称序列 n, n-1,0 是的一个规范规约，如果此序列满足： (1) n= (2) 0=S (3)对任意的i,i-1是从i经句柄替换的结果。,规范推导： 最右推导常被称为规范推导 规范句型： 最右推导的句型称为规范句型 规范归约： 规范推导的逆过程（最左规约）称为规范归约,5.1.3 符号栈的使用与语法树的表示,规范规约的数据结构和动作： 采用栈作为语法分析的基本数据结构。 符号栈 输入串 # w# #S # 语法分析对符号栈的使用有四类操作：“移进”、“归约”、“接受”和“出错处理”。 任何可规约串的出现必须在栈顶。,例5.3：输入串i1*i2+i3的分析步骤： 步骤 符号栈 输入串 所用产生式 0 # i1*i2+i3# 预备 1 #i1 *i2+i3# 进 2 #F *i2+i3# 归，用Fi 3 #T *i2+i3# 归，用TF 4 #T* i2+i3# 进 5 #T*i2 +i3# 进 13 #E # 归，用EE+T 14 #E # 接受,5.2 算符优先分析,5.2.1 算符优先文法及优先表构造 5.2.2 算符优先分析算法 5.2.3 优先函数 5.2.4 算符优先分析中的出错处理,算符优先分析法的主要思想： 是自下而上的归约过程，但这种归约未必是严格的最左归约。而是借助于两个终结符之间的优先关系来寻找“可归约串”进行归约。 算符优先关系定义： (1) ab: a的优先性低于b。当且仅当G中含有形如PaR的产生式，而 Rb或R Qb；但并不意味b高于a。 (2) ab: a的优先性等于b。当且仅当G中含有形如Pab的产生式或PaQb的产生式；但并不意味b等于a。 (3) ab：a的优先性高于b。当且仅当G中含有形如PRb的产生式，而R a或R aQ。a的优先性高于b。,5.2.1 算符优先文法及优先表构造,算符文法定义： 一个文法，如果它的任一产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：QR 算符优先文法定义： 如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三关系之一： ab，ab ，ab,例5.4 构造下面算法优先文法的优先表 (1)EE+T|T (2)TT*F|F (5.3) (3)FPF|P (4)P(E)|i 解： 由(4)可得()；由(2)(3)可得* 最后可得表5.1所示优先表。,算符优先文法G构造优先关系表的算法,FIRSTVT(P)和LASTVT(P)定义： FIRSTVT(P)=a|P+a或P+Qa,aVT而QVN LASTVT(P)=a|P+a或P+aQ,aVT而QVN FIRSTVT(P)构造： 若有产生式Pa或PQa，则aFIRSTVT(P); 若aFIRSTVT(Q)，且产生式PQ，则aFIRSTVT(P)。,算法程序运算如下：,PROCEDURE INSERT(P,a); IF NOT FP,a THEN BEGIN FP,a:=TRUE;把(P,a)下推进STACK栈END; 主程序： BEGIN FOR 每个非终结符P和终结符a DO FP,a:=FALSE; FOR 每个形如Pa或PQa的产生式 DO INSERT(P,a); WHILE STACK 非空DO BEGIN 把STACK的栈顶记为（Q,a），上托出去； FOR每条形如PQ的产生式 DO INSERT(P,a); END OF WHILE;END,构造优先表的算法：,FOR 每条产生式 PX1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符THEN置Xi Xi+1 IF in-2且Xi都为终结符,但Xi+1为非终结符 THEN置XiXi+2； IF Xi 为终结符,而Xi+1为非终结符 THEN FOR FIRSTVT(Xi+1)中的每个a DO 置Xi a; IF Xi为非终结符而Xi+1为终结符 THEN FOR LASTVT(Xi)中的每个a DO 置 aXi+1 END,5.2.2 算符优先分析算法,素短语： 是一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。 最左素短语： 最左边的素短语是最左素短语。 例子： 对文法(5.3)p*p和i是句型p*p+i的素短语，而p*p+i本身也是素短语。,算符优先文法： 算符优先文法，我们把句型（括在两个之间）的一般形式写成： N1a1N2a2NnanNn+1# 其中，每个ai都是终结符，Ni是可有可无的非终结符。 文法G的任何短语是满足如下条件的最左子串NjajNiaiNi+1 aj-1 aj aj aj+1 , ,aj-1 ai ai ai+1,算符优先分析算法,k:=1 Sk:=； REPEAT 把下一个输入符号读进a中； IF SkVTTHEN j:=k ELSE j:=k-1; WHILE Sj a DO BEGIN REPEAT Q:=Sj; IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把Sj+1Sk归约为某个N； k:=j+1;Sk:=N END OF WHILE; IF Sj a OR Sj a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR /*调用出错诊察程序*/ UNTIL a=#,算法分析： 没有定义非终结符的优先级，它无法发现单个非终结符组成的“可规约串”，所以算符优先分析不是规范规约。 优点： 速度快。 缺点： 忽略了非终结符的规约过程，存在一定的危险。,5.2.3 优先函数,入栈优先函数f和比较优先函数g定义： 若Q1Q2 则f(Q1)g(Q2) 采用优先函数的优缺点： 便于比较运算，节省空间。 由任何两个非终结符都可以进行比较，所以可能掩盖一些问题。,从优先表构造优先函数的方法是： 对于每个终结符a（包括）令其对应两个符号fa和ga，画一张以fa和ga所有符号为结点的方向图，如果ab,那么，就从fa画一箭弧至gb；如果a b，就画一条从gb到fa的箭弧。 对每个结点都赋予一个数，此数等于从该结点能到达结点（包括出发结点自身在内）的个数。赋给fa的数作为f(a)，赋给gb的数作为g(b)。 检查所构造出来的函数f和g，看它们 同原来的关系表是否有矛盾。如果没有矛盾，则f和g就是所要的优先函数。如果有矛盾，那么，就不存在优先函数。,5.2.4 算符优先分析中的出错处理,错误类型： 若找到某一“句柄”（此处“句柄”指素短语），但不存在任一产生式，其右部为此“句柄”。 若在栈顶终结符号与下一输入符号之间不存在任何优先关系；,算法5.2.1,对规约中发现的问题： (1)找出相近的素短语； (2)分析差异； (3)给出可能的错误信息。 对算符优先分析中的问题： (1)如+或*被规约，则检查其两端是否出现非终结符。否则，打印错误信息：“缺表达式” (2)如i被规约，则检查其左端或右端是否有非终结符。如果有，则给出信息：“表达式无运算符连接” (3)如果( )被规约，则检查是否在括号间有一非终结符。如果没有，则给出信息：“括号无表达式”。,算法5.2.1,采用对输入串进行“改变、插入和删除”等方法。 如：当(结束，将(从站顶移去，并给出错误信息：非法左括号。 当I或)后跟I或(时，在输入端插入+,并给出错误信息：“缺少运算符”。 当表达式以右括号开始，从输入串中删除)，并给出错误信息：“非法右括号”。 若站顶有非终结符E，则表达式分析完毕。 若为空，则在输入端插入I；给出错误信息：缺少表达式。,5.3 LR分析法,5.4 语法分析器的自动产生工具YACC,YACC：LALR(1)分析程序的生成器 工作方式：,Yacc程序的构成：3个部分，中间以%分割 声明：变量、常量的声明，正规定义 翻译规则：形式如下，其中pi是正规式 p1 动作1 p2 动作2 用C语言编写的支持例程,% #include #include % %token NUMBER /* 此处声明了允许的记号 */ % command : exp printf(“%dn”, $1); /* command为开始符号 */ ; /* allows printing of the result */ exp : exp + term $ = $1 + $3; /* 记号可以直接出现在语法规则中*/ | exp - term $ = $1 - $3; | term $ = $1; ; term : term * factor $ = $1 * $3; | factor $ = $1; ;,factor : NUMBER $ = $1; | ( expr ) $ = $2; ; % main( ) return yyparse( ); int yylex(void) int c; while (c = getchar() = ); /* eliminates blanks */ if (isdigit(c) ungetc( c , stdin ); scanf(“%d”, /* allows for printing of an error messages */,Yacc分析冲突与消除二义性的规则： 在y.output中报告调查的分析冲突 二义性消除的规则 Yacc可以为分析冲突发生产生一个分析程序，并消除二义性 指明有二义性的文法相分割开得算符优先及结合性的机制：使得文法描述更简单 %left + - %left * 表明+，-有相同的优先权