编译原理：第五章语法分析1

1、第 5 章 语法分析 语法分析是编译的第二阶段；其任务是识别和处理比单词更大的语法单位，如：程序设计语言中的表达式、各种说明和语句乃至全部源程序，指出其中的语法错误；必要时，可生成内部形式，便于下一阶段处理。 内容提要:5.1 语法分析的基本概念5.2 递归子程序法5.3 LL(1)分析法5.4 LR()分析法5.5 简单优先分析法5.1 语法分析的基本概念5.1.1 语法分析的定义与分类 【定义】形式上说，语法分析是指对给定的符号串（），判定其是否是某文法G(Z)的句子。即Z 成立吗 ? = + Z 成立吗 ? = .+ 【分类】语法分析方法通常分两大类： 1. 自顶向下法（推导法） 2.

2、自底向上法（归约法） 从开始符号出发，采用推导运算，试图自顶向下构造语法树。 从给定的符号串出发，采用归约运算，试图自底向上构造语法树。或 通常采用“最左推导法”。 通常采用“最左归约法”给定： = a*(b+c)， 是否是表达式？(接上页)5.1.2 算法设计分析1【例5.1】 G(E)： E - T | E+T | E-T T - F | T*F | T/F F - i | (E) 最左推导分析过程：【结论】自顶向下分析的关键技术是如何确定具有相同左部的产生式之侯选者！即 E a*(b+c) = +=T*F=F*F=a*F=a*(E)=a*(E+T)=a*(T+T)=a*(F+T)=a*(

3、b+T)=a*(b+F)=a*(b+c)- 自顶向下法:E=T 为了清楚每次归约的是什麽？我们观察语法树的 = a*(b+c)5.1.2 算法设计分析2 E - T | E+T | E-T T - F | T*F | T/F F - i | (E) - 自底向上法a*(b+c)=.F*(b+c)=.T*(E+c)=.T*(b+c)=.T*(F+c)=.T*(T+c)=.T*(E+F)=.T*(E+T)=.T*(E)=.T*F=.E=.T=.+E a*(b+c)即【结论】自底向上分析的关键技术是如何确定当前句型的句柄！最左归约分析过程： 构造过程： 5.2.1 递归子程序法的设计原理： 语法分析

4、的核心技术是“文法”的机内表示问题；递归子程序法直接把文法变成程序。 对每一个非终结符，构造一个子程序，用以识别该非终结符所定义的符号串。每个子程序以产生式左部非终结符命名，以产生式右部构造子程序内容。例如：设有如下产生式： A - aBeD | bAc | 则有：递归子程序 A: 递归子程序法属于自顶向下语法分析方法。故又名递归下降法。 设计原理：yn入口出口a?b?NEXT(w)yNEXT(w) NEXT(w)nc?ynerr2e?遇时 B A Dyerr1nNEXT(w)A - aBeD | bAc | 判断当前单词是否是c即w=c?调用子程序A(接上页)读单词函数5.2.2 递归子程序

5、的构造算法 扩展文法：增设一个产生式，作为主程序：Z-Z ， 入出口约定： 子程序入口时，其首符号已经读来！子程序出口时，其后继符应该读来！ 子程序内容设计：遇终结符，判定之 ，确认后读下一单词；遇非终结符,调用之,返回后不读下一单词； 遇空串( ) ，直接出口； 【例5.2】G(S):令 Z - S , 则 递归子程序:子程序A开始结束 #SNEXT(w)err0yn入口出口 a berr1NEXT(w)A berr2NEXT(w)SNEXT(w)子程序Snnnyyy入口 cNEXT(w)出口遇时ny dNEXT(w)err3yn主程序S - aAb |bS , A - cd | 实际上，上

6、述两点可归纳为同一个条件，即： 递归子程序要求文法应是： 5.2.3 递归子程序法对文法的要求： 递归子程序是根据文法各产生式的首符号与当前所读单词进行匹配，以决定候选产生式的；这就要求文法： 具有相同左部的各产生式，首符号不同； 文法不能有左递归！如：A - a|a (首符号相同，)； A - A| (直接左递归，)。 LL(1)文法!（见 5.3节）。 5.2.4 递归子程序的构造例： . 消除左递归后的文法1:G(E) :T - F 2 F F - i | ( E )E - T 1T 【提示】 根据文法变换：A - A | A - 【例5.3】G(E)： E - T | E1T T -

7、F | T2F F - i | (E) 其中：1(+,-),2(*,/),i(变量或常数)主程序T - F 2 F F - i | ( E )E - T 1 T 子程序E令 Z - E开始结束 #ENEXT(w)err0yn入口出口NEXT(w)T 1Tyn入口出口NEXT(w)F 2Fyn子程序T(接上页)T - F 2 F F - i | ( E )E - T 1 T 入口出口 i (err1NEXT(w)err2NEXT(w)E )yyynnn子程序F(接上页). 消除左递归后的文法2 :G(E) :T - F 2 F F - i | ( E )E - T 1 T E - T EE -

8、1T E | T - F TT - 2F T | F - i | ( E ) 文法 G(E)消除花括号后可得：令 Z - E ，则可构造递归子程序如下： （主程序 省略）入口出口TE子程序E入口 1NEXT(w)T出口遇时nyE子程序EE - T EE - 1T E | T - F TT - 2F T | F - i | ( E )(接上页)练习题：【习题5.1】解释下述词语： 语法分析 ；语法分析的分类。【习题5.2】构造下述文法的递归子程序： G(S): S - a A S b | B d A - c S | B - b B | d 【习题5.3】构造下述文法的递归子程序： 产生式 S - Bd 的首符号为 b,d ! 产生式 A - 的首符号(后继符) a,b,d提示G(E): E - T + T | - T T - F * F | / F F - i | ( E )a * ( b + c )FTTEFFTETFEaFbFTcFE+T