《编译原理：第五章语法分析1》由会员分享，可在线阅读，更多相关《编译原理：第五章语法分析1（18页珍藏版）》请在金锄头文库上搜索。
1、第第 5 5 章章 语法分析语法分析 语法分析是编译的第二阶段；其任务是语法分析是编译的第二阶段；其任务是识别识别和和处理处理比单词更大的语法单位比单词更大的语法单位，如：，如：程序设计语言中程序设计语言中的的表达式表达式、各种各种说明说明和和语句语句乃至全部乃至全部源程序，源程序，指出指出其中的其中的语法错误；必要时，可生成内部形式，便于语法错误；必要时，可生成内部形式，便于下一阶段处理。下一阶段处理。 内容提要内容提要: :5.1 5.1 语法分析的基本概念语法分析的基本概念5.2 5.2 递归子程序法递归子程序法5.3 LL(1)5.3 LL(1)分析法分析法5.4 LR()5.4 LR
2、()分析法分析法5.5 5.5 简单优先分析法简单优先分析法5.1 5.1 语法分析的语法分析的基本基本概念概念5.1.1 5.1.1 语法分析的定义与分类语法分析的定义与分类 【定义定义】形式上说，语法分析是指对给定的符号形式上说，语法分析是指对给定的符号串（串（ ），判定其是否是某文法），判定其是否是某文法G(Z)G(Z)的句子。即的句子。即Z Z 成立吗成立吗 ? ? = + + Z Z 成立吗成立吗 ? ? = . .+ + 【分类分类】语法分析方法通常分两大类：语法分析方法通常分两大类： 1. 1. 自顶向下法自顶向下法（推导法推导法） 2. 2. 自底向上法自底向上法（归约法归约法
3、） 从开始符号出发，采用从开始符号出发，采用推导推导运算运算，试图，试图自顶自顶向下向下构造语法树。构造语法树。 从给定的符号串出发，采用从给定的符号串出发，采用归约归约运算运算，试图，试图自底向上自底向上构造语法树。构造语法树。或或 通常采用通常采用“最左推导法最左推导法”。 通常采用通常采用“最左归约法最左归约法”给定：给定： = a*(b+c)= a*(b+c)， 是否是表达式？是否是表达式？( (接上页接上页) )5.1.2 5.1.2 算法设计分析算法设计分析1 1【例例5.15.1】 G(E) G(E)： E - T | E+T | E-T E - T | E+T | E-T T
4、- F | T*F | T/F T - F | T*F | T/F F - i | (E) F - i | (E) 最左推导最左推导分析过程：分析过程：【结论结论】自顶向下分析的关键技术是如何确定具有自顶向下分析的关键技术是如何确定具有相同左部的产生式之相同左部的产生式之侯选者侯选者！即即 E a*(b+c)E a*(b+c) = + +=T*F=T*F =F*F=F*F =a*F=a*F =a*(E=a*(E) )=a*(E+T=a*(E+T) )=a*(T+T=a*(T+T) )=a*(F+T=a*(F+T) )=a*(b+T=a*(b+T) )=a*(b+F=a*(b+F) )=a*(b
5、+c=a*(b+c) )- - 自顶向下法自顶向下法: :E E = = T T 为了清楚每次为了清楚每次归约归约的是什麽？我们观察语法树的的是什麽？我们观察语法树的 = a*(b+c)= a*(b+c)5.1.2 5.1.2 算法设计分析算法设计分析2 2 E - T | E+T | E-T E - T | E+T | E-T T - F | T*F | T/F T - F | T*F | T/F F - i | (E) F - i | (E) - - 自底向上法自底向上法a*(b+ca*(b+c) )=. .F*(b+cF*(b+c) )=. .T*(E+cT*(E+c) )=. .T*(
6、b+cT*(b+c) )=. .T*(F+cT*(F+c) )=. .T*(T+cT*(T+c) )=. .T*(E+FT*(E+F) )=. .T*(E+TT*(E+T) )=. .T*(E)T*(E)=. .T*FT*F=. .E E=. .T T=. .+ +E E a*(b+ca*(b+c) )即即【结论结论】自底向上分析的关键技术是自底向上分析的关键技术是如何确定如何确定当前句型的句柄！当前句型的句柄！最左归约最左归约分析过程分析过程： 构造过程：构造过程： 5.2.1 5.2.1 递归子程序法的设计递归子程序法的设计原理原理： 语法分析的核心技术是语法分析的核心技术是“文法文法”的
7、的机内表示机内表示问题；递归子程序法直接把问题；递归子程序法直接把文法文法变成变成程序。程序。 对每一个对每一个非终结符非终结符，构造一个子程序，用以识，构造一个子程序，用以识别该非终结符所定义的符号串。别该非终结符所定义的符号串。每个子程序以产生每个子程序以产生式左部非终结符命名式左部非终结符命名，以产生式右部构造子程序内以产生式右部构造子程序内容。容。例如：设有如下产生式：例如：设有如下产生式： A - A - aBeDaBeD | | bAcbAc | | 则有：则有：递归子程序递归子程序 A:A: 递归子程序法属于递归子程序法属于自顶向下语法分析方法自顶向下语法分析方法。故。故又名递归
8、下降法。又名递归下降法。 设计原理：设计原理：y yn n入口入口出口出口a?a?b?b?NEXT(w)NEXT(w)y yNEXT(w) NEXT(w) NEXT(w)NEXT(w)n nc?c?y yn nerr2err2e?e?遇时时 B B A A Dyerr1err1nNEXT(w)NEXT(w)A - A - aBeDaBeD | | bAcbAc | | 判断当前单词是否是c即w=c?调用子程序A( (接上页接上页) )读单词函数5.2.2 5.2.2 递归子程序的递归子程序的构造构造算法算法 扩展文法扩展文法：增设一个产生式，作为主程序：增设一个产生式，作为主程序：Z-Z Z-
9、Z ， 入出口约定入出口约定： 子程序入口时，其子程序入口时，其首符号首符号已经读来！已经读来！子程序出口时，子程序出口时，其其后继符后继符应该读来！应该读来！ 子程序内容设计子程序内容设计：遇遇终结符终结符，判定之，判定之 ，确认后读下一单词；，确认后读下一单词；遇遇非终结符非终结符, ,调用之调用之, ,返回后不读下一单词；返回后不读下一单词； 遇遇空串空串( ( ) ) ，直接出口；，直接出口； 【例例5.25.2】G(S):G(S):令令 Z - S , Z - S , 则则 递归子程序递归子程序: :子程序子程序A开始开始结束结束 #SNEXT(w)err0yn入口入口出口出口 a
10、berr1NEXT(w)A berr2NEXT(w)SNEXT(w)子程序子程序Snnnyyy入口入口 cNEXT(w)出口出口遇遇 时时ny dNEXT(w)err3yn主程序主程序S - S - aAbaAb | |bSbS , A - , A - cdcd | | 实际上，上述两点可归纳为同一个条件，即：实际上，上述两点可归纳为同一个条件，即： 递归子程序要求文法应是：递归子程序要求文法应是： 5.2.3 5.2.3 递归子程序法对文法的递归子程序法对文法的要求要求： 递归子程序是根据文法各产生式的递归子程序是根据文法各产生式的首符号首符号与当前与当前所读所读单词单词进行匹配，以决定进行
11、匹配，以决定候选产生式候选产生式的；这就要求的；这就要求文法：文法： 具有相同左部的各产生式，首符号不同；具有相同左部的各产生式，首符号不同； 文法不能有左递归！文法不能有左递归！如：如：A - aA - a |a|a ( (首符号相同，首符号相同，)； A - AA - A | | ( (直接左递归，直接左递归，)。 LL(1)LL(1)文法文法! !（见（见 5.35.3节）。节）。 5.2.4 5.2.4 递归子程序的递归子程序的构造例构造例： . 消除左递归后的文法消除左递归后的文法1:G(E) :G(E) :T - F T - F 2 2 F F F - i | ( E )F - i
12、 | ( E )E - T E - T 1 1T T 【提示提示】 根据文法变换：根据文法变换：A - AA - A | | A - A - 【例例5.35.3】G(E)G(E)： E - T | EE - T | E1 1T T T - F | T T - F | T2 2F F F - i | (E) F - i | (E) 其中：其中：1 1(+,-),(+,-),2 2(*,/),i(*,/),i(变量或常数变量或常数) )主程序主程序T - F T - F 2 2 F F F - i | ( E )F - i | ( E )E - T E - T 1 1 T T 子程序子程序E令令
13、Z - EZ - E开始开始结束结束 #ENEXT(w)err0yn入口入口出口出口NEXT(w)T 1 1Tyn入口入口出口出口NEXT(w)F 2 2Fyn子程序子程序T( (接上页接上页) )T - F T - F 2 2 F F F - i | ( E )F - i | ( E )E - T E - T 1 1 T T 入口入口出口出口 i (err1NEXT(w)err2NEXT(w)E )yyynnn子程序子程序F( (接上页接上页) ). . 消除左递归后的文法消除左递归后的文法2 :2 :G(E) G(E) : :T - F T - F 2 2 F F F - i | ( E
14、)F - i | ( E )E - T E - T 1 1 T T E - T EE - T EE - E - 1 1T E | T E | T - F TT - F TT - T - 2 2F T | F T | F - i | ( E )F - i | ( E ) 文法文法 G(E)消除花括号后可得：消除花括号后可得：令令 Z - E Z - E ，则可构造递归子程序如下：则可构造递归子程序如下： （主程序（主程序 省略）省略）入口入口出口出口TE子程序子程序E入口入口 1 1NEXT(w)T出口出口遇遇 时时nyEE子程序子程序EE - T EE - T EE - E - 1 1T E
15、| T E | T - F TT - F TT - T - 2 2F T | F T | F - i | ( E )F - i | ( E )( (接上页接上页) )练习题：练习题：【习题习题5.15.1】解释下述词语：解释下述词语： 语法分析语法分析 ；语法分析的分类。；语法分析的分类。【习题习题5.25.2】构造下述文法的递归子程序：构造下述文法的递归子程序： G(S): S - a A S b | B dG(S): S - a A S b | B d A - c S | A - c S | B - b B | d B - b B | d 【习题习题5.35.3】构造下述文法的递归子程序：
16、构造下述文法的递归子程序： 产生式产生式 S - S - BdBd 的首符号为的首符号为 b,d !b,d ! 产生式产生式 A - A - 的首符号的首符号( (后继符后继符) a,b,d) a,b,d提示提示G(E): E - T + T | - T G(E): E - T + T | - T T - F * F | / F T - F * F | / F F - i | ( E )F - i | ( E )a * ( b + c )a * ( b + c )F FT TT TE EF FF FT TE ET TF FE Ea aF Fb bF FT Tc cF FE E+ +T TE E( () )F FT T* *T TET | | E + T | | E - TTF | | T * F | | T / FFi | ( E )| ( E )P:P:基本图形库基本图形库 =. .+ + =+ +A = . .+ + = + +=*, =+ , =.* , =.+ , =l* , =l+ , =.l+ ，=.l* = =. .谢谢收看！
