《语法分析课件》由会员分享，可在线阅读，更多相关《语法分析课件（79页珍藏版）》请在金锄头文库上搜索。
1、第 5 章 语法分析 语法分析是编译的第二阶段；其任务是语法分析是编译的第二阶段；其任务是识别识别和和处理处理比单词更大的语法单位比单词更大的语法单位，如：，如：程序设计语言中程序设计语言中的的表达式表达式、各种各种说明说明和和语句语句乃至全部乃至全部源程序源程序，指出指出其中的其中的语法错误；必要时，可生成内部形式，便于语法错误；必要时，可生成内部形式，便于下一阶段处理。下一阶段处理。 内容提要内容提要: :5.1 5.1 语法分析的基本概念语法分析的基本概念5.2 5.2 递归子程序法递归子程序法5.3 LL(1)5.3 LL(1)分析法分析法5.4 LR()5.4 LR()分析法分析法5
2、.5 5.5 简单优先分析法简单优先分析法语法分析语法分析5.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 算法设计分析1【例例5.15.1】 G(E) G(E)： 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 | (
4、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+c=a*(b+c) )- - 自顶向下法自顶向下法: :E E = = T T语法分
5、析语法分析 为了清楚每次为了清楚每次归约归约的是什麽？我们观察语法树的的是什麽？我们观察语法树的 = a*(b+c)= a*(b+c)5.1.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*(b+cT*(b+c) )=. .T*(F+cT*(F+c) )=. .T*(T+cT*(T+c)
6、)=. .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 递归子程序法的设计原理： 语法分析的核心技术是语法分析的核心技术是“文法文法”的的机内表示机内表示问题；递归子程序法直接把问题；递归子程序法直接把文法文法变成变成程序。程序。 对每一个对每一个非终结符非终结
7、符，构造一个子程序，用以识，构造一个子程序，用以识别该非终结符所定义的符号串。别该非终结符所定义的符号串。每个子程序以产生每个子程序以产生式左部非终结符命名式左部非终结符命名，以产生式右部构造子程序内以产生式右部构造子程序内容。容。例如：设有如下产生式：例如：设有如下产生式： A - aBeD | bAc | A - aBeD | bAc | 则有：递归子程序则有：递归子程序 A:A: 递归子程序法属于递归子程序法属于自顶向下语法分析方法自顶向下语法分析方法。故。故又名递归下降法。又名递归下降法。 设计原理：设计原理：语法分析语法分析y yn n入口入口出口出口a?a?b?b?NEXT(w)N
8、EXT(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 - aBeD | bAc | A - aBeD | bAc | 判断当前单词是否是c即w=c?调用子程序A( (接上页接上页) )读单词函数语法分析语法分析5.2.2 递归子程序的构造算法 扩展文法扩展文法：增设一个产生式，作为主程序：增设一个产生式，作为主程序：Z-Z Z-Z ， 入出口约定入出口约定： 子程序入口时，其子程序入口时，其首符号首符号已经读来！已经读来！子程序出口时，子程序出
9、口时，其其后继符后继符应该读来！应该读来！ 子程序内容设计子程序内容设计：遇遇终结符终结符，判定之，判定之 ，确认后读下一单词；，确认后读下一单词；遇遇非终结符非终结符, ,调用之调用之, ,返回后不读下一单词；返回后不读下一单词； 遇遇空串空串( ( ) ) ，直接出口；，直接出口； 语法分析语法分析【例例5.25.2】G(S):G(S):令令 Z - S , Z - S , 则则 递归子程序递归子程序: :子程序子程序A开始开始结束结束 #SNEXT(w)err0yn入口入口出口出口 a berr1NEXT(w)A berr2NEXT(w)SNEXT(w)子程序子程序Snnnyyy入口入口
10、 cNEXT(w)出口出口遇遇 时时ny dNEXT(w)err3yn主程序主程序S - aAb |bS , A - cd | S - aAb |bS , A - cd | 语法分析语法分析 实际上，上述两点可归纳为同一个条件，即：实际上，上述两点可归纳为同一个条件，即： 递归子程序要求文法应是：递归子程序要求文法应是： 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 | ( E )E - T E - T 1 1T T 【提示提示】 根据文法变换：根据文法变换：A
12、- 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令令 Z - EZ - E开始开始结束结束 #ENEXT(w)err0yn入口入口出口出口
13、 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 )F - i | ( E )E - T E -
14、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 | T E | T - F T
15、T - F TT - T - 2 2F T | F T | F - i | ( E )F - i | ( E )( (接上页接上页) )语法分析语法分析 1. 1. 什麽是什麽是LL(1)LL(1)分析法？分析法？ 5.3.1 LL(1)分析法基本概念 5.3 LL(1)分析法 LL(1) 分析法的基本要点有三：分析法的基本要点有三： 利用一个利用一个分析表分析表，登记如何，登记如何选择产生式选择产生式的知识；的知识； 利用一个利用一个分析栈分析栈，记录分析过程；，记录分析过程； 此分析法要求文法必须是此分析法要求文法必须是 LL(1)文法文法。 LL(1) LL(1)分析法是指从分析法是指从
16、左左到右扫描到右扫描、最最左左推导推导( (LLLL) )和只查看和只查看一一个当前符号（括号中的个当前符号（括号中的 1 1）之意；）之意； LL(1)LL(1)分析法又称预测分析法，与递归子程序分析法又称预测分析法，与递归子程序法同属于自顶向下确定性语法分析方法法同属于自顶向下确定性语法分析方法; ; 语法分析语法分析 2. LL(1)2. LL(1)分析过程示例分析过程示例 G(Z)G(Z)：Z-dAZZ-dAZ | bAc | bAc A-aA A-aA | | 栈栈 当前符号当前符号 剩余序列剩余序列 栈操作栈操作 选择推导产生式后，为什麽要逆序压栈选择推导产生式后，为什麽要逆序压栈
17、? ? 当栈顶为当栈顶为A,A,当前单词为当前单词为c c时，为什么时，为什么选择选择 A A ? ?讨讨论论逆逆序序压压栈栈# # # c # c A A# c# c# c # c A A# # c c# # c A c A b b A A a ab ba c #a c # 选择选择 Z ZbAcbAcb ba c #a c #匹配匹配 b ba ac #c # 选择选择A AaAaAa ac #c #匹配匹配 a a c c# # 选择选择A A c c# #匹配匹配 c c# #正确结束正确结束 Z Z查分查分析表析表 对符号串：对符号串： = = bacbac # # 的分析过程：的分
18、析过程：分析表：分析表：语法分析语法分析 设有文法G(Z), # 栈底标记和结束标记;#栈栈结束结束： 若若 栈顶符栈顶符=a =a 且且 当前符为当前符为a a； 则则 pop,NEXT(w);pop,NEXT(w);# Z 开始开始：栈栈 ; NEXT(w)；当前符当前符 w= # 重复执行重复执行 、 ，直到栈中只剩，直到栈中只剩 # # 为止：为止： 即：栈调整：即：栈调整： # a# 即：栈调整：即：栈调整： # A# a a 3. LL(1) 3. LL(1)分析法算法概要分析法算法概要 若若 栈顶符栈顶符=A =A 且且 当前符当前符 w=a w=a 且且 有有产生式产生式： A
19、 Aa a ， 则则 POP,PUSH(aPOP,PUSH(a ) )R R ; ; 逆序压栈! 否则，否则，错误处理错误处理！语法分析语法分析5.3.2 LL(1)文法及其判定1.首符号集合、后继符集合与选择符集合 设设 G(Z)=(VG(Z)=(VN N, V, VT T, Z, P), Z, P)，A-A- PP，则，则 【注注】 ( ( 可空可空), ), ( ( 不可空不可空) )； 若若 = = 则则 first(first( )= )= ； 设设 # #为输入串的结束符，则为输入串的结束符，则 #follow(Z); #follow(Z); =* * *first(first(
20、)= t| )= t| t t，tVtVT T =* *follow(A)= t| Z follow(A)= t| Z AtAt，tVtVT T =* *语法分析语法分析【注注】 求求 follow(A) follow(A) 要点：要点： 查所有右部含有查所有右部含有A A的产生式的产生式: B - : B - A A 若若 不空时不空时 , , 则则 first(first( ) )follow(A)follow(A) ； 若若 取空时取空时 , , 则则 follow(B)follow(B)follow(A)follow(A) ； 若若 = = 时时 , , 则则 follow(B)fol
21、low(A)follow(B)follow(A)。select()= first(select()= first(dAZdAZ)=d )=d select()= first(select()= first(bcAbcA)=b)=bselect()= first(select()= first(aAaA)=a )=a select()= first(select()= first( )follow(A)= )follow(A)= b,db,d，# # 即：即： B - B - A AG(Z)G(Z)： Z - dAZ | bcA Z - dAZ | bcA A - aA | A - aA | 【
22、例5.4】 求文法产生式的选择集合:则有：则有： 产生式产生式序号序号语法分析语法分析 select()= d select()= d ；2. LL(1)2. LL(1)文法及其判定文法及其判定 LL(1) LL(1)文法可确保文法可确保 递归子程序法递归子程序法 和和 LL(1)LL(1)分分析法析法 的正确运用。的正确运用。【例例5.55.5】 G(Z) G(Z)： Z - dAZ | bcA Z - dAZ | bcA A - aA | A - aA | select()= b select()= bselect()= a select()= a ；即：即： db=db= 又又 ab,d
23、,#= ab,d,#= select()= select()= b,db,d，# # G(Z) G(Z) 是是 LL(1)LL(1)文法。文法。语法分析语法分析 LL(1)分析法示例：【例5.6】 G(Z)：Z - Z b | a 【注注】上述文法可进行等价变换，消除左递归得：上述文法可进行等价变换，消除左递归得： select()= a select()= a select()= a select()= a 选择集合相交选择集合相交 具有左递归的文法，一定不是具有左递归的文法，一定不是LL(1)LL(1)文法！文法！ G G(Z)(Z)是是LL(1)LL(1)文法，可以用文法，可以用 LL(
24、1)LL(1)分析法。分析法。 select( select()= b )= b select( select()= # )= # 选择集合不相交选择集合不相交G G(Z)(Z)： Z - aA , Z - aA , A - bA | A - bA | 语法分析语法分析 列： 终结符 | #5.3.3 LL(1)分析器设计(实现) 应用时，可用下列函数查表，获取相应产生式：应用时，可用下列函数查表，获取相应产生式： L(L(栈顶符，当前符）栈顶符，当前符）= = 产生式序号产生式序号【结构设计结构设计】. LL(1). LL(1)分析表的构造分析表的构造: : LL(1)LL(1)控制程序控制
25、程序+ +LL(1)LL(1)分析表分析表LL(1)LL(1)分析表是存储分析表是存储文法选择集合的知识表文法选择集合的知识表。 行：行： 非终结符非终结符表项：表项：产生式产生式序号 Z # a A A 语法分析语法分析如如 G(Z)G(Z)： Z - aAb | AcA Z - aAb | AcA select()=a; select()=a; 【算法设计算法设计】 A - dA | A - dA | i则则 L( A , a ):=L( A , a ):=A - A - i 求求文法文法选择集合，确认选择集合，确认 LL(1)LL(1)文法；文法； 依次取依次取产生式产生式：select
26、()=d;select()=d;select()=c,d ; select()=c,d ; select()= select()= b,c,#;b,c,#;是是 LL(1)LL(1)文法文法, ,LL(1)LL(1)分析表：分析表：不相交不相交不不相相交交若若 a select( ) a select( ) i 语法分析语法分析NEXT(w)NEXT(w)y yn nerrerrn ny yn nn nerrerr PUSH(#),PUSH(Z) PUSH(#),PUSH(Z) POP(x) POP(x)y y开始开始结束结束xVxVT Tn nerrerry yxVxVN Nw = #w =
27、 #x = wx = wy y查查LL(1)LL(1)分分析析表表: : L L( x ,w )= ?( x ,w )= ? 空？空？. LL(1). LL(1)分析法控制程序：分析法控制程序：PUSH ( iPUSH ( iR R ）把产生式把产生式 i i 右部逆序压栈右部逆序压栈把栈顶符把栈顶符弹入到变弹入到变量量x x中中! !语法分析语法分析 LL(1)分析法综合示例：【例例5.75.7】 G(E) G(E)： E - T | E E - T | E 1 1 T T T - F | T T - F | T 2 2 F F F - i | ( E ) F - i | ( E ) 此文法
28、含左递归，不是此文法含左递归，不是LL(1)LL(1)文法文法; ;经文法经文法变换（消除左递归）后可得：变换（消除左递归）后可得：G(E): E - T EG(E): E - T E E E- - 1 1 T ET E | | T - F T T - F T T T- - 2 2 F TF T | | F - i | ( E ) F - i | ( E ) 其中：其中： 1 1( + ,- ) , ( + ,- ) , 2 2 ( * ,/ ) ( * ,/ ) 这是这是LL(1)LL(1)文法吗文法吗? ?语法分析语法分析select()=first(TE)= select()=first
29、(TE)= i i, ,( ( 1.1.求求G(E) G(E) 的的选择集合：选择集合： 三对选择集合两两不相交，三对选择集合两两不相交，G(E): E - T EG(E): E - T E E E- - 1 1 T ET E | | T - F T T - F T T T- - 2 2 F TF T | | F - i | ( E ) F - i | ( E ) E -E -E-E-T -T -T-T-F -F -select()=first(select()=first( 1 1TETE)= )= 1 1 select()=follow(Eselect()=follow(E)= )= )
30、), ,# # select()=first(FT)= select()=first(FT)= i i, ,( ( select()=first(select()=first( 2 2FTFT)= )= 2 2 select()=follow(T)= select()=follow(T)= 1 1 , ,) ), ,# # select()=first(i)= select()=first(i)= i i select()=first(E)= select()=first(E)= ( ( G(E) G(E)是是 LL(1) LL(1) 文法。文法。( (接上页接上页) )语法分析语法分析 2.
31、构造 LL(1) 分析表： 花括号花括号内内是求得的是求得的选择集合！选择集合！ F T T E E ) ( # 2 1 iT T- - 2 2 FTFT 2 2 | | 1 1, ,) ), ,# # F - i F - i i i | (E) | (E) ( ( E - TEE - TE i i, ,( ( E E- - 1 1 TETE 1 1 | | ) ), ,# # T - FTT - FT i,(i,( G(E):G(E):( (接上页接上页) )语法分析语法分析 符号串 a+b# 的LL(1)分析过程：查分析表： 操 作剩余序列 w x 分析栈# ( + 匹配成功 ) b #
32、+1# ET1 :PUSH(ET1) b # +E# E :PUSH( ) + b # +T# E T : PUSH(i) + b # a F TF ( a 匹配成功 ) + b # a i i :PUSH(TF) + b # a T E T ：PUSH(ET) a+b # a+b # a E# E : PUSH(TF) b # b T# E T ok # # :PUSH ( ) # #T # E T :PUSH ( ) #E# E ( b 匹配成功) # b i i : PUSH（i） # b F TF# E# ET# E # ET分析表控制程序语法分析语法分析 LR( ) LR( )分析法
33、是指从分析法是指从左左到右到右扫描扫描、最、最左左归约归约( (LRLR) )之意；它属于自底向上分析方法。之意；它属于自底向上分析方法。 常用的算法有常用的算法有LR(0)LR(0)和和LR(1)LR(1)等，其中括号内的等，其中括号内的数数是指不查看是指不查看(0)(0)或只查看或只查看一一个当前符号个当前符号(1)(1)，即可，即可确定当前句型的确定当前句型的句柄句柄。5.4 LR( )5.4 LR( )分析法分析法 利用一个利用一个分析表分析表，登记，登记选择选择句柄产生式句柄产生式的知识；的知识； 利用一个利用一个分析栈分析栈，记录分析过程；，记录分析过程；【分析算法分析算法】依次读
34、取依次读取单词，单词，并进行如下操作：并进行如下操作： 当栈顶出现当栈顶出现句柄句柄时，时，规约规约之，否则之，否则移进移进。 5.4.1. LR( )5.4.1. LR( )分析法基本概念分析法基本概念 LR( ) LR( ) 分析法的基本要点有三：分析法的基本要点有三：1. 1. 什么是什么是LRLR（）分析法？（）分析法？语法分析语法分析【例例5.85.8】 G(Z): Z-aBAd, A-bc| G(Z): Z-aBAd, A-bc|c, B-bB|cc, B-bB|c 2. LR( )2. LR( )分析法分析过程示例：分析法分析过程示例： 符号串符号串 abccdabccd 最左归
35、约过程最左归约过程: : 符号串符号串 abccd abccd 的语法树：的语法树： abccdabccd 的语法树的语法树 a b c c da b c c dB BB BA AZ Z 归约过程归约过程的的句柄句柄：句柄句柄次序次序 c cbBbB c caBAdaBAdabccdabccd =. .abBcdabBcd =. .aBcdaBcd =. .aBAdaBAd =. . Z Z语法分析语法分析 句柄产生式句柄产生式 操操 作作 剩余串剩余串 w w 分析栈分析栈 移进移进,NEXT,NEXT d # d # c c# a# a 归约，归约， A - c A - c # # d d
36、# a B# a B 移进移进,NEXT,NEXT # # d d# a B# a B 归约，归约， Z - aBAd Z - aBAd # # a B A# a B A OK OK # # # B - bB B - bB B - c B - c 移进移进,NEXT,NEXT c d # c d # c c# a# a 移进移进,NEXT ,NEXT b c c d # b c c d # a a# # 归约，归约， d # d # c c # a b# a b 归约，归约， d # d # c c# a b# a b 移进移进,NEXT,NEXT c c d # c c d # b b# #
37、 B B B B Z Z A A a a b b c c c c d d句句柄柄( (接上页接上页) ) 利用利用分析栈分析栈记录行分析过程：记录行分析过程：【注注】 何时栈顶出现何时栈顶出现句柄？句柄？怎样求当前怎样求当前句柄产生式句柄产生式 ？设设 待分析的符号串待分析的符号串: abccd#abccd#语法树语法树语法分析语法分析3. 3. 有限自动机有限自动机用作用作句柄识别器：句柄识别器： 如何确认首次出现的如何确认首次出现的 c c 的父亲是的父亲是 B B, ,而不是而不是 A A ？G(Z): Z - aBAdG(Z): Z - aBAd A - bc | A - bc | c
38、 c B - bB | c B - bB | c 句柄句柄一定一定出现于出现于某某一个产生式的一个产生式的右部右部； 归约过程中如何确认归约过程中如何确认句柄句柄？ 是否是句柄是否是句柄，还要看，还要看其其所在符号串中的所在符号串中的位置位置。 怎样判断栈顶出现的怎样判断栈顶出现的句柄句柄不是不是 bcbc, ,而是而是 c c ? ? 显然是错误的显然是错误的( (从文法中可判定：从文法中可判定：aAaA不能相邻不能相邻!) !) 若用若用 bcbc 归约，则有归约，则有 a abcbccd aAcd(cd aAcd( ) ) =. . 若用若用 A A作父亲，则有作父亲，则有 a abcb
39、ccd abAcd(cd abAcd( ) ) =. .显然是错误的显然是错误的( (从文法中可判定：从文法中可判定：AcAc不能相邻不能相邻! !语语法法树树 我们讨论如下两个问题：我们讨论如下两个问题：# #abc cd#abc cd#分析栈分析栈语法分析语法分析 扩展文法，使扩展文法，使文法符号文法符号附有附有位置位置信息：信息： 增设一个产生式增设一个产生式( (如：如：Z- ZZ- Z ) )， 带有带有位置位置编编码的码的文法符号文法符号，称为，称为文法出现文法出现。G(Z)G(Z)并把产生式并把产生式右端符号顺序编码，作为右端符号顺序编码，作为位置位置( (状态状态) )信息信息
40、: :【注注】 由于由于文法出现文法出现比比文法符号文法符号多了一个位置信息，多了一个位置信息， 在分析时，如果用在分析时，如果用文法出现文法出现代替代替文法符号文法符号，是否有助于，是否有助于句柄句柄的确认呢？的确认呢？ 句柄识别器的构造方法句柄识别器的构造方法语法分析语法分析 利用利用扩展文法扩展文法构造构造句柄识别器句柄识别器： 若把若把扩展文法扩展文法中的中的位置号位置号看成看成状态状态，那么，那么就可用就可用有限自动机有限自动机描述描述如下：如下： 对每个产生式，构造自动机，用以识别自己的符对每个产生式，构造自动机，用以识别自己的符号串；号串； (0,Z)=1;(0,Z)=1; 预见
41、预见 某个某个非终结符非终结符，也就，也就预见预见 其所有其所有产产生式的头符号生式的头符号; ;于是各产生式的于是各产生式的子自动机子自动机可可并接并接在一起在一起。 【表示表示】: : 0 0状态状态 预见预见 Z Z 后变换为后变换为 1 1状态状态 ！ 设编码设编码0 0作为自动机的作为自动机的开始状态开始状态，第二个产生式，构造第二个产生式，构造自动机自动机：则则 第一个产生式，构造第一个产生式，构造自动机自动机： (0,a)=2;(0,a)=2; (2,B)=3;(2,B)=3; (3,A)=4;(3,A)=4; (4,d)=5;(4,d)=5; 语法分析语法分析 句柄识别器句柄识
42、别器的自动机构造示例：的自动机构造示例：其中：其中：r(j)r(j) 归约函数归约函数( (即即 按序号为按序号为(j)(j)的的产生式产生式归约！归约！) )； 移进状态：移进状态： 归约状态：归约状态：B - bB - b9 9 B B1010 (4)(4)| c| c11 11 (5)(5)Z - ZZ - Z1 1 (0)(0)Z Z - a- a2 2 B B3 3 A A4 4 d d5 5 (1)(1)A - bA - b6 6 c c7 7 (2)(2)| | c c8 8 (3)(3)G(Z)G(Z) 符号说明符号说明 0 0，2 2，3 3，4 4，6 6，9 9 ； 0
43、01111+ +Z Za aB Bb bb bB Bc cc cA Ad db bc cOKOKr(3r(3) )r(1)r(1)r(2r(2) )r(4)r(4)r(5)r(5)c c 由由扩展文扩展文法法到到句柄识别句柄识别器器的构造过程的构造过程如右图所示：如右图所示：【例例5.85.8】 5 5，7 7，8 8，1010，1111； 分析结束分析结束( (OKOK) )。 接受状态：接受状态： 1 1语法分析语法分析 0 01111+ +Z Za aB Bb bb bB Bc cc cA Ad db bc cOKOKrrrrrrrrrrc c 根据根据句柄识别器句柄识别器进行进行LRL
44、R分析过程：分析过程： 根据根据句柄识别器句柄识别器， abccd# abccd# 识别过程：识别过程：(#(#0 0, ,a a) )=(#=(#0 0a a2 2b b9 9B B1010, ,c c) )=(#=(#0 0a a2 2B B3 3A A4 4, ,d d) )=(#=(#0 0a a2 2, ,b b) )=(#=(#0 0a a2 2b b9 9, ,c c) )=(#=(#0 0a a2 2b b9 9c c1111, ,c c) )=(#(#0 0a a2 2B B3 3, ,c c) )= = (#(#0 0a a2 2B B3 3c c8 8, ,d d) )=
45、(#(#0 0a a2 2B B3 3A A4 4d d5 5, ,# #) )=( (# #0 0Z Z1 1, ,# #) )=0k=0k 句柄识别器句柄识别器又称又称“活前缀图活前缀图”: : 意思是在意思是在最左最左归约归约过程中，识别了过程中，识别了句柄句柄，实际上也就识别了以，实际上也就识别了以句句柄柄为后缀的该句型为后缀的该句型( (规范句型规范句型) )的前部符号串。的前部符号串。注注B - bB - b9 9 B B1010 (4)(4)| c| c11 11 (5)(5)Z - ZZ - Z1 1 (0)(0)Z Z - a- a2 2 B B3 3 A A4 4 d d5
46、 5 (1)(1)A - bA - b6 6 c c7 7 (2)(2)| | c c8 8 (3)(3)句句柄柄【例例5.85.8】文法的文法的句柄识别器句柄识别器: :语法分析语法分析+ +LR(0)LR(0)分析器的基本组成：分析器的基本组成：LR(0)LR(0)分析法要求文法应是分析法要求文法应是 LR(0LR(0）文法）文法。LR(0)LR(0)分析表分析表 LR(0)LR(0)控制器控制器 LR( LR(0 0) )中的中的0 0, ,是指是指不必查看当前符号不必查看当前符号就可确就可确认认句柄句柄之意；之意；5.4.2 LR(0)5.4.2 LR(0)分析器设计分析器设计1. 1
47、. LR(0)LR(0)文法文法及其判定及其判定 句柄识别器中，句柄识别器中，移移进进和和归约归约不冲突不冲突；即；即 移进和归约不同时发生！移进和归约不同时发生！ 满足下述特点的文法称为满足下述特点的文法称为 LR(0)LR(0)文法文法。例例5.8 5.8 文法，就是文法，就是 LR(0)LR(0)文法，文法，请看：请看： 归约归约时不必查看当前符号；时不必查看当前符号；语法分析语法分析【算法算法】 根据根据句柄识别器，句柄识别器，填写填写 LR(0)LR(0)分析表：分析表： 若若 (i,x)=k,x(V(i,x)=k,x(VN N+V+VT T),),则则 R(i,x):= R(i,x
48、):= xkxk ; ; 若若 状态状态i i 标记有（标记有（- -，r(j),r(j), 则则 对任何对任何 a (Va (VT T+#+#），）， R(i,a):= R(i,a):= r(j)r(j) ; ; R(1,#):= R(1,#):= OKOK 。 2. LR(0)2. LR(0)分析表构造分析表构造 扩展文法，扩展文法，构造句柄识别器；构造句柄识别器； LR()LR()分析表分析表是是 LR()LR()分析法的分析法的知识表知识表, ,是是句柄识句柄识别器别器的一种机内的一种机内表示形式：表示形式：状状态态编编码码终结符终结符 + #+ #非终结符非终结符 R(_,_)R(_
49、,_): :0 0 1 1 a a # # Z Z n nakakOKOKZkZkr(j)r(j)r(j)r(j)语法分析语法分析 0 01111+ +Z Za aB Bb bb bB Bc cc cA Ad db bc cOKOKrrrrrrrrrrc cLR(0)LR(0)分析表分析表【例例5.85.8】文法文法构造过程：构造过程： 9 9 10 10 Z Z A A 1 1 5 5 0 0 4 4 8 8 d d # # 6 6 7 7 11 11 3 3 2 2 B B c c b b a a B B1010c c1111 b b9 9r r(4)(4)r r(4)(4)r r(4)(
50、4)r r(4)(4)r r(4)(4) Z Z1 1 A A4 4 OK OKr r(1)(1)r r(1)(1)r r(1)(1)r r(1)(1)r r(1)(1) a a2 2d d5 5r r(3)(3)r r(3)(3)r r(3)(3)r r(3)(3)r r(3)(3)r r(5)(5)r r(2)(2) r r(5)(5)r r(2)(2)c c7 7r r(2)(2)r r(2)(2)r r(2)(2)r r(5)(5)r r(5)(5)r r(5)(5)c c8 8 b b6 6 B B3 3 b b9 9c c1111语法分析语法分析3. LR(0)3. LR(0)控制
51、程序设计控制程序设计开始开始PUSH(#0)PUSH(#0)NEXT(w)NEXT(w)查查LR(0)LR(0)分析表分析表R(Xk,w)=?R(Xk,w)=?R=R=空空? ?Y YerrerrR=OKR=OK结束结束R=R=r(j)r(j)R=WiR=WiPUSH WiPUSH Wi 则则 PUSH Ai;PUSH Ai;取取 A - A - (j) (j) POP( POP( );); 若若 R(Xk,A)=AiR(Xk,A)=Ai Xk Xk 栈顶栈顶文法出现文法出现；归归约约移移进进LR( )LR( )控制器控制器n n语法分析语法分析 LR(0) LR(0)分析法小结示例分析法小结
52、示例G(Z): Z - aBAdG(Z): Z - aBAd A - bc | A - bc | c c B - bB | c B - bB | c【例例5.85.8】文法文法: : 扩展文法，使扩展文法，使文法符号文法符号附有附有位置位置信息：信息： B - bB - b9 9 B B1010 (4)(4)| c| c11 11 (5)(5)Z - ZZ - Z1 1 (0)(0)Z Z - a- a2 2 B B3 3 A A4 4 d d5 5 (1)(1)A - bA - b6 6 c c7 7 (2)(2)| | c c8 8 (3)(3) 由由扩展文法扩展文法构造构造句柄识别器：句
53、柄识别器： 0 01111+ +Z Za aB Bb bb bB Bc cc cA Ad db bc cOKOKr(3r(3) )r(1)r(1)r(2r(2) )r(4)r(4)r(5)r(5)c c语法分析语法分析 0 01111+ +Z Za aB Bb bb bB Bc cc cA Ad db bc cOKOKrrrrrrrrrrc c 9 9 10 10 Z Z A A 1 1 5 5 0 0 4 4 8 8 d d # # 6 6 7 7 11 11 3 3 2 2 B B c c b b a a B B1010c c1111 b b9 9r r(4)(4)r r(4)(4)r r
54、(4)(4)r r(4)(4)r r(4)(4) Z Z1 1 A A4 4 OK OKr r(1)(1)r r(1)(1)r r(1)(1)r r(1)(1)r r(1)(1) a a2 2d d5 5r r(3)(3)r r(3)(3)r r(3)(3)r r(3)(3)r r(3)(3)r r(5)(5)r r(2)(2) r r(5)(5)r r(2)(2)c c7 7r r(2)(2)r r(2)(2)r r(2)(2)r r(5)(5)r r(5)(5)r r(5)(5)c c8 8 b b6 6 B B3 3 b b9 9c c1111 由句柄识别由句柄识别器构造器构造LR(0)
55、LR(0)分分析表：析表：语法分析语法分析 LR(0) LR(0)分析法分析法分析过程分析过程示例：示例： 剩余串剩余串 操操 作作 w w 分析栈分析栈#0 a2 #0 a2 b9b9 B10B10 PUSH(c8),NEXT(w) PUSH(c8),NEXT(w) d# d# c c#0 a2#0 a2 REDUCE(3)REDUCE(3) # # d d#0 a2 B3#0 a2 B3 PUSH(d5),NEXT(w) PUSH(d5),NEXT(w) # # d d#0 #0 a2 B3a2 B3 REDUCE(1)REDUCE(1) # #0 #0 a2 B3 A4a2 B3 A4
56、OKOK # #0#0 d# d# d# d# cd# cd# ccd# ccd# bccd# bccd# PUSH(c11),NEXT(w)PUSH(c11),NEXT(w) c c#0 a2#0 a2 PUSH(a2),NEXT(w) PUSH(a2),NEXT(w) a a#0 #0 REDUCE(4)REDUCE(4) c c REDUCE(5)REDUCE(5) c c#0 a2 b9#0 a2 b9 PUSH(b9),NEXT(w) PUSH(b9),NEXT(w) b b#0#0 a2 a2 b9 b9 c11c11 B3 B3 c8c8 A4 A4 d5 d5 Z1 Z1查分析
57、表查分析表查产生式查产生式控制程序控制程序符号串：符号串：abccdabccd# #语法分析语法分析【例例5.95.9】LR(0)LR(0)分析法示例分析法示例1 1： 构造下述文法的构造下述文法的LR(0)LR(0)分析表：分析表： G(Z)G(Z)： Z - aAb , A - cA | d Z - aAb , A - cA | d 0 0+ +Z Za aA Ad db bc cA AOKOKr(1)r(1)r(2r(2) )r(3)r(3)c cd d 构造句柄识别器：构造句柄识别器： 扩展文法扩展文法：G(Z) Z- ZG(Z) Z- Z1 1 (0) (0) Z - a Z - a
58、2 2 A A3 3 b b4 4 (1)(1) A - c A - c5 5 A A6 6 (2)| d (2)| d7 7 (3)(3)语法分析语法分析 设计设计LR(0) LR(0) 分分析表：析表：r(3)r(3)r(2)r(2) d7 d7 r(1) r(1) d7 d7 d d Z1 Z1 Z Z A6 A6 A3 A3 A A OK OK 1 1 c5 c5 5 5 a2 a2 0 0 r(1) r(1) (1) (1) r(1) r(1) r(1) r(1) 4 4r(3)r(3)r(2)r(2) # #r(2)r(2)r(2)r(2) r(2) r(2) 6 6r(3)r(3
59、)r(3)r(3) r(3) r(3) 7 7 b4 b4 3 3 c5 c5 2 2 c c b b a a 0 0+ +Z Za aA Ad db bc cA AOKOKr(1r(1) )r(2r(2) )r(3)r(3)c cd d语法分析语法分析【例例5.105.10】左递归文法的左递归文法的LR(0)LR(0)分析表构造：分析表构造： d d Z Z A A 1 1 5 5 0 0 4 4 # # 6 6 3 3 2 2 c c b b a a 0 0+ +Z Za aA Ad db bc cOKOKr(1r(1) )r(2r(2) )r(3r(3) )Z-ZZ-Z1 1(0);(0
60、); Z -aZ -a2 2A A3 3b b4 4(1);(1); A -AA -A3 3c c5 5(2)|d(2)|d6 6(3)(3)G(ZG(Z) )【注注】为了使为了使句柄识别句柄识别器器是是确定机确定机，左递归产，左递归产生式生式(2)(2)中的中的A A要与要与(1)(1)中中的的A A编码相同编码相同!?,!?, r r(3)(3) r r(2)(2) r r(1)(1) d d6 6 Z Z1 1 A A3 3 OK OKr r(2)(2) r r(2)(2) r r(2)(2) r r(2)(2) a a2 2r r(1)(1) r r(1)(1) r r(1)(1) r
61、 r(1)(1)r r(3)(3) r r(3)(3) r r(3)(3) r r(3)(3) c c5 5 b b4 4 语法分析语法分析【例例5.115.11】LR(0)LR(0)分析法示例分析法示例1 1 构造下述文法的构造下述文法的LR(0)LR(0)分析表：分析表： G(Z) Z - aAb , A - Ac | dG(Z) Z - aAb , A - Ac | d 扩展文法：扩展文法：G(Z) Z- ZG(Z) Z- Z1 1 (0) (0) Z - a Z - a2 2 A A3 3 b b4 4 (1)(1) A - A A - A5 5c c6 6 (2)| d(2)| d7
62、 7 (3)(3) 构造可归前缀图：构造可归前缀图： 0 0+ +Z Za aA Ad db bA Ac cOKOKr(1)r(1)r(2r(2) )r(3)r(3)语法分析语法分析( (接上页接上页) ) （2 2，A)=3,5,A)=3,5, 是个非确定机；是个非确定机； 0 0+ +Z Za aA Ad db bc cOKOKr(1)r(1)r(2r(2) )r(3)r(3) 确定化的可归前缀图：确定化的可归前缀图： 0 0+ +Z Za aA Ad db bA Ac cOKOKr(1)r(1)r(2r(2) )r(3)r(3)语法分析语法分析 LR(0) LR(0) 分析表：分析表：r
63、(3)r(3)r(2)r(2)r(1)r(1) d6 d6 d d Z1 Z1 Z Z A3 A3 A A OK OK 1 1r(2)r(2)r(2)r(2)r(2)r(2) r(2) r(2) 5 5 a2 a2 0 0r(1)r(1)r(1) r(1) r(1) r(1) r(1) r(1) 4 4r(3)r(3) # #r(3)r(3)r(3)r(3) r(3) r(3) 6 6 c5 c5 b4 b4 3 3 2 2 c c b b a a 0 0+ +Z Za aA Ad db bc cOKOKr(1)r(1)r(2r(2) )r(3)r(3)( (接上页接上页) )语法分析语法分析
64、i ir(j),r(kr(j),r(k) )5.4.3 5.4.3 LR(0)LR(0)分析法的扩展分析法的扩展 LR()LR()分析法的关键技术是分析法的关键技术是句柄识别器句柄识别器的设计问题；的设计问题；如果句柄识别器发生了如果句柄识别器发生了冲突冲突： 此时，此时，LR(0)LR(0)分析法分析法失效失效! ! 需需要改进要改进句柄识别器句柄识别器的的构造方法构造方法，于是出现了各种不同的于是出现了各种不同的 LR( )LR( )分分析法。析法。 【注注】 下面仅通过实例探讨下面仅通过实例探讨 LR(0)LR(0)分析表分析表 的简单扩的简单扩展问题展问题 - - 称为称为 SLR(1
65、)SLR(1)分析法。分析法。i ik kr(j)r(j)x x移进移进/ /归约冲突归约冲突归约归约/ /归归约冲突约冲突或或语法分析语法分析【例例5.95.9】 G(Z): Z-aAb G(Z): Z-aAb ；A-cd|A-cd| 扩展扩展文法文法， 构造构造句柄识别器：句柄识别器： Z- ZZ- Z1 1(0) ; (0) ; Z - aZ - a2 2A A3 3b b4 4(1) (1) A - cA - c5 5d d6 6(2)|(2)| 7 7(3)(3)G(Z)G(Z): : 经确定化经确定化( (消消边) )： 句柄识别器句柄识别器出出现冲突现冲突： :c5,r(3),A
66、3:c5,r(3),A3 称为称为 移移进进/ /归约冲突！归约冲突！看到：看到： bc=bc= ；解决办法：解决办法： 求：求：follow(A)=follow(A)= bb 若若 w=c w=c 则则 c5 ; c5 ; 若若 w=b w=b 则则 r(3) r(3) 。 通过查看通过查看当前单词当前单词，是否可以解决？为此：，是否可以解决？为此：r(3r(3) )0 0+ +Z Za aA Ab bOKOKr(1r(1) )r(2r(2) )c cr(3r(3) ) d d- -语法分析语法分析Z-Z(0)Z-Z(0)Z-aAb(1)Z-aAb(1)A-cd(2) A-cd(2) - (
67、3)(3)SLR(1)SLR(1)分析表分析表b br(3r(3) )SLR(1)SLR(1)句柄识别器：句柄识别器： 扩展扩展句柄识别器，句柄识别器，构造构造SLR(1)SLR(1)分析表分析表r(2)r(2)d6d6 r(1) r(1) Z1 Z1 A3 A3 OK OK a2 a2 r(1) r(1)r(1)r(1) r(1) r(1) r(1) r(1)r(2)r(2)r(2)r(2)r(2)r(2) r(2) r(2) b4 b4c5c5 r(3) r(3)注意与注意与LR(0)LR(0)分析分析表的区别！表的区别！0 0+ +Z Za aA Ab bOKOKr(1r(1) )r(2
68、r(2) )c cd d- - 如此可以解决冲如此可以解决冲突的文法，称为突的文法，称为SLR(1)文法文法。语法分析语法分析S- SS- S1 1(0) (0) S - AS - A2 2a a3 3 | B| B4 4c c5 5 A - A - d d6 6 ; B- ; B-d d7 7 【例例5.105.10】 G(S): S-Aa|Bc G(S): S-Aa|Bc ；A-d; B-d ;A-d; B-d ; 扩展扩展文法文法， 构造构造句柄识别器：句柄识别器： G(S)G(S): :即即 若若 w=a w=a 则则 r(3) ; r(3) ; 若若 w=c w=c 则则 r(4)
69、r(4) 。 求：求：follow(A)follow(A)=a=a；follow(B)follow(B)=c=c0 0+ +S SA Aa ac cOKOKr(1r(1) )r(4)r(4)d dr(3r(3) )r(2r(2) )B B d d0 0+ +S SA Aa ac cOKOKr(1r(1) ),r(4,r(4) )d dr(3r(3) )r(2r(2) )B B 确定化确定化非确定机非确定机语法分析语法分析S- SS- S1 1(0) (0) S - AS - A2 2a a3 3 | B| B4 4c c5 5 A - A - d d6 6 ; B- ; B-d d6 6 扩展
70、扩展句柄识别器，句柄识别器，构造构造SLR(1)SLR(1)分析表分析表 # # A A B B 1 1 5 5 0 0 4 4 S S 6 6 3 3 2 2 d d c c a a r(2)r(2) r(1) r(1) OK OK A2 A2 B4 B4 r(2)r(2)r(2)r(2) r(2) r(2) S1 S1 d6 d6 c5 c5 r(4)r(4) r(3) r(3)r(1)r(1) r(1) r(1) r(1) r(1) a3 a3注意与注意与LR(0)LR(0)分析表的区分析表的区别！别！SLR(1)SLR(1)分析表分析表 通过查看当前单词，通过查看当前单词，解决冲突：解
71、决冲突：0 0+ +S SA Aa ac cOKOKr(1r(1) )d dr(2r(2) )B B ,r(4,r(4) )r(3r(3) ) -SLR(1)SLR(1)句柄识句柄识别器别器a arrrrc c语法分析语法分析 简单优先简单优先分析法是一种从分析法是一种从左左到右到右扫描扫描、最、最左左归归约约分析法；它属于自底向上分析方法。分析法；它属于自底向上分析方法。 该方法利用该方法利用文法符号文法符号之间的之间的优先关系优先关系来确定待归来确定待归约的句柄约的句柄 ，即可确定当前句型的，即可确定当前句型的句柄句柄。5.5 5.5 简单优先分析法简单优先分析法 利用一个利用一个分析表分
72、析表，登记，登记选择选择句柄产生式句柄产生式的知识；的知识； 利用一个利用一个分析栈分析栈，记录分析过程；，记录分析过程；【分析算法分析算法】依次读取依次读取单词，单词，并进行如下操作：并进行如下操作： 当栈顶出现当栈顶出现句柄句柄时，时，规约规约之，否则之，否则移进移进。 5.5.1. 5.5.1. 简单优先分析法基本概念简单优先分析法基本概念 简单优先分析法的基本要点有三：简单优先分析法的基本要点有三：1. 1. 什么是简单优先分析法？什么是简单优先分析法？语法分析语法分析 2. 2. 简单优先分析过程示例简单优先分析过程示例 符号串：符号串： = abbeae #SaAeBSbbaG(S
73、): G(S): S SaAeB|baAeB|b A ASb|eSb|e B BaAaAAe语法分析语法分析 句柄产生式句柄产生式 操操 作作 剩余串剩余串 w w 分析栈分析栈 移进移进,NEXT,NEXT a e # a e # e e# a# a 移进移进,NEXT,NEXT e # e # a a# a A# a A 移进移进,NEXT,NEXT # # e e# a A e# a A e 归约归约 A - e A - e # # aAe a # aAe a 归约归约 B - aA B - aA # # aAe a# aAe a A - Sb A - Sb S - b S - b 归约
74、归约 e a e # e a e # b b# a# a 移进移进,NEXT ,NEXT b b e a e # b b e a e # a a# # 归约归约 a e # a e # e e # a S # a S 移进移进,NEXT,NEXT e a e # e a e # b b# a # a 移进移进,NEXT,NEXT b e a e # b e a e # b b# # A A A A a a a a b b e e e e句句柄柄( (接上页接上页) ) 利用利用分析栈分析栈记录行分析过程：记录行分析过程：【注注】 何时栈顶出现何时栈顶出现句柄？句柄？怎样求当前怎样求当前句柄产生
75、式句柄产生式 ？设设 待分析的符号串待分析的符号串: abbeae#abbeae# S# S b b# aAe# aAe # # B# B句句柄柄 S - aAeB S - aAeB 归约归约# # # # S S OKOK语法树语法树语法分析语法分析同时归约者为相等关系，记作同时归约者为相等关系，记作 ；3. 3. 文法符号之间的优先关系文法符号之间的优先关系归约过程中如何确认归约过程中如何确认句柄句柄？ 是否是句柄是否是句柄，还要看其，还要看其所在符号串中的所在符号串中的位置位置。语语法法树树从语法树上，找出优先关系（指相临符号之间）如下： S S b b，a a A A，A A e e，
76、e e B B 如：如：左后归约者为小于关系，记作左后归约者为小于关系，记作 ； 如：如：aab,b,aae,e,ee ； 如：如：b bb,b,b bee 当把优先关系纳入待分析的符号串时，有如下关系： # # a a b b e e a a # # # # a a e e a a # # # # a A e a A e a a # # # # a A e a A e # # # # # # 结论：一个句型的句柄，位于第一次（自左至右）结论：一个句型的句柄，位于第一次（自左至右）出现在出现在 之间的符号串！之间的符号串！ 语法分析语法分析从文法中获取优先关系从文法中获取优先关系! ! 设设s
77、i si ，sjsj是两个文法符号是两个文法符号; ; 如：如：a Aa A，A eA e，e Be B，S bS b； si sj si sj ，当且仅当有，当且仅当有U Usi sj si sj ； 优先关系的定义优先关系的定义 G(S): G(S): S SaAeB|baAeB|b A ASb|eSb|e B BaAaA si si + +如：如：aae e，aaS S，aaa a，aab b，eesj sj ，当且仅当有，当且仅当有 U UVsjVsj ，且，且 V V sisi； = + +如：如：b bbb，B Bbb，A Abb，e ebb。 (3)头符号集合和尾符号集合 设设
78、AVAVN N， si si ，sjsj是两个文法符号是两个文法符号; ;则则: : FIRSTVT(A)=si| A siFIRSTVT(A)=si| A si, = + +LASTVT(A) = sj|A LASTVT(A) = sj|A sjsj。 = + +语法分析语法分析【例例5.125.12】G(S): G(S): S SaAeB|baAeB|b，A ASb|eSb|e，B BaAaA S A B a b e S A B a e S A BFIRSTVT a , b S,e,a,b aLASTVT B,b,A,e b , e A , b , e 头符号集合头符号集合尾符号集合尾符号
79、集合优先矩阵优先矩阵表项表项=空空表示两个表示两个符号不可符号不可能相临。能相临。 语法分析语法分析+ +简单优先分析器的基本组成：简单优先分析器的基本组成：优先优先分析法要求文法应是分析法要求文法应是简单优先简单优先文法文法。优先矩阵分析表优先矩阵分析表 优先分析控制器优先分析控制器 分析中只分析中只查看当前符号查看当前符号就可确认就可确认句柄句柄；5.5.2 5.5.2 简单优先分析器设计简单优先分析器设计1.1.简单优先简单优先文法文法及其判定及其判定 文法产生式没有相同的右部；文法产生式没有相同的右部； 如如A A ，B B ， 满足下述特点的文法称为满足下述特点的文法称为简单优先简单
80、优先文法文法。例例5.12 5.12 文法，就是文法，就是简单优先简单优先文法，文法，请看：请看：文法符号之间至多有一种优先关系！文法符号之间至多有一种优先关系！ 语法分析语法分析【算法算法】 si sj si sj ， 当且仅当有当且仅当有U Usi sj si sj ； si si sj sj ， 当且仅当有当且仅当有U UVsjVsj，且，且siLASTVT(V)siLASTVT(V)。 2. 2. 简单优先分析矩阵分析表构造简单优先分析矩阵分析表构造设设 W,VVW,VVN N,si,si，sjsj是两个文法符号是两个文法符号; ; 简单优先分简单优先分析表析表是优先分析是优先分析法的
81、知识表法的知识表, ,是是文文法法的一种机内表的一种机内表示形式：示形式：终结符终结符 + +非终结符非终结符+#+# a a Z Z #优先关系优先关系符号符号终终结结符符+ +非非终终结结符符+ +# #语法分析语法分析3. 3. 简单优先控制程序设计简单优先控制程序设计开始开始PUSH(#)PUSH(#)NEXT(w)NEXT(w)查优先分析表查优先分析表R(Xk,w)=?R(Xk,w)=? 空空? ?n nerrerr(#S#) 结束结束PUSH WPUSH WPOP(sj)POP(sj)，POP(sj-1)POP(sj-1)， POP(si)POP(si)；PUSH(A)PUSH(A
82、)。从从sj（栈顶符）开始，往栈内（栈顶符）开始，往栈内查找，找到第一个使查找，找到第一个使si-1? ?y yn n语法分析语法分析只考虑算符（终结符）之间的优先关系只考虑算符（终结符）之间的优先关系 （1 1）算符文法）算符文法 设有一文法设有一文法G G，如果，如果G G中没有形如中没有形如A AQRQR的产生式，其中的产生式，其中Q Q和和R R为非终结符，则称该文法为非终结符，则称该文法为算符文法（为算符文法（OGOG文法）。文法）。 5.5.3 5.5.3 算符优先分析算符优先分析(2)头符号集合和尾符号集合头符号集合和尾符号集合 设设 aVaVT T，P,RVP,RVN N， 则
83、则: : FIRSTVT(P)=a| P aFIRSTVT(P)=a| P a 或或 P RaP Ra, = + +LASTVT(P) =a| P LASTVT(P) =a| P a a 或或 P P aRR。 = + + = + + = + +语法分析语法分析设设a,bVa,bVT T，P,Q,RVP,Q,RVN N， a b a b ， 当且仅当有当且仅当有 P Pabab 或或 P PaQbaQb ； (3) 算符优先关系定义算符优先关系定义算符优先关系定义算符优先关系定义 a a + + a ab b ， 当且仅当有当且仅当有 P PRbRb ，且，且R R a a 或或 R R aQ
84、aQ； = + +(4)算符优先文法算符优先文法 如果算符文法如果算符文法G G中的任何一对终结符中的任何一对终结符a a和和b b之间，仅满之间，仅满足上述一种关系，则足上述一种关系，则G G就是一个算符优先文法（就是一个算符优先文法（OPGOPG）。）。 = + + = + +语法分析语法分析5.6 5.6 语法分析方法综合示例语法分析方法综合示例G(Z)G(Z)：Z - dAZ | bAcZ - dAZ | bAcA - aA | c |A - aA | c |【例例5.135.13 】 给定文法如下：给定文法如下：. . 递归子程序法；递归子程序法；. LL(1). LL(1)分析法；
85、分析法； 试分别用下述分析法，对给定的试分别用下述分析法，对给定的符号串符号串进行语法分析：进行语法分析：. LR(0)( . LR(0)( 或或SLRSLR（1 1）) )分析法；分析法；设设 给定的符号串为：给定的符号串为：= bac= bac Z = bAc = baAc = ba Z = bAc = baAc = ba c = bacc = bac bac bac 是文法是文法 G(Z) G(Z) 的一个句子。的一个句子。注注语法分析语法分析G(Z)G(Z)：Z-dAZZ-dAZ | bAc | bAc A-aA A-aA | e | e |. . 构造递归子程序法：构造递归子程序法：
86、 证明证明 G(Z)G(Z)是是 LL(1)LL(1)文法：文法：select()= first(select()= first(dAZdAZ)= d )= d 求选择集合：求选择集合：select()= first(select()= first(bAcbAc)= b )= b select()= first(select()= first(aAaA)= a )= a select()= first(select()= first(c c) = e) = e select()= follow(A)= select()= follow(A)= d ,b d ,b ，c c 两组选择集合两组选择
87、集合, 皆不相交，皆不相交， G G（Z Z）是）是 LL(1) LL(1) 文法！文法！即即 递归子程序法可用！递归子程序法可用！语法分析语法分析Z子程序子程序主程序主程序 构造递归子程序构造递归子程序(框图框图)：G(Z)G(Z)：Z-dAZZ-dAZ | bAc | bAc A-aA A-aA | e | e |入口入口 aNEXT(w)出口出口遇遇 时时nyAA子程序子程序 eNEXT(w)yn #NEXT(w)结束结束nyZ开始开始err0入口入口出口出口 derr3NEXT(w)AnnyZA cNEXT(w)y berr2nyNEXT(w)语法分析语法分析 分析过程示意分析过程示意
88、：入口入口 aNEXT(w)出口出口遇遇 时时nyAA子程序子程序 eNEXT(w)yn主程序主程序 #NEXT(w)结束结束nyZ开始开始err0bac#设设 待分析的符号串：待分析的符号串：入口入口出口出口 derr3NEXT(w)AZ子程序子程序nnyZA cNEXT(w)y berr2nyNEXT(w)b bb ba aa ac cc cc cc c# # #语法分析语法分析G(Z)G(Z)：Z-dAZZ-dAZ | bAc | bAc A-aA A-aA | e | e |. LL(1). LL(1)分析法：分析法： 证明证明 G(Z)G(Z)是是 LL(1)LL(1)文法：文法：s
89、elect()= first(select()= first(dAZdAZ)= d )= d 求选择集合：求选择集合：select()= first(select()= first(bAcbAc)= b )= b select()= first(select()= first(aAaA)= a )= a select()= first(select()= first(c c) = e) = e select()= follow(A)= select()= follow(A)= d ,b d ,b ，c c 两组选择集合两组选择集合, 皆不相交，皆不相交， G G（Z Z）是）是 LL(1) L
90、L(1) 文法！文法！即即 递归子程序法可用！递归子程序法可用！语法分析语法分析 2. 2. 构造构造 LL(1)LL(1)分析表：分析表： LL(1) LL(1) 分析表：分析表：G(Z)G(Z)：Z-dAZZ-dAZ d d | bAc | bAc b b A-aA A-aA a a | e | e e e |b,c,db,c,d 带有带有选择集合选择集合的文法：的文法： d A Z e c b a # 语法分析语法分析 栈栈 当前符号当前符号 剩余序列剩余序列 栈操作栈操作 逆逆序序压压栈栈# # # c # c A A# c# c# c # c A A# # c c# # c A c
91、A b b A A a ab ba c #a c #pop,push(cAb)pop,push(cAb)b ba c #a c #pop,nextpop,nexta ac #c # pop,push( pop,push(Aa)Aa)a ac #c #pop,next pop,next c c# #c c# # # Z Z 对符号串：对符号串： = = bacbac # # 的分析过程：的分析过程： 分析过程示意分析过程示意：G(Z)G(Z)：Z-dAZZ-dAZ d d | bAc | bAc b b A-aA A-aA a a | e | e e e |b,c,db,c,d d A Z e
92、c b a # pop,push( pop,push( ) ) pop,nextpop,next正确结束正确结束查分查分析表析表语法分析语法分析. LR(0)(SLR(1). LR(0)(SLR(1)分析法：分析法： 扩展扩展文文法，编码：法，编码：G(Z)G(Z)：Z- ZZ- Z1 1 0 0 Z -d Z -d2 2A A3 3Z Z4 4 | b | b5 5A A6 6c c7 7 A -aA -a8 8A A9 9 | e | e10 10 |11 11 直接构造直接构造SLR(1)分析表：分析表： 9 9 10 10 # # Z Z 1 1 5 5 0 0 4 4 8 8 d d
93、 e e 6 6 7 7 3 3 2 2 A A c c b b a a r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(2)r(2)rr A3A3Z1Z1 OK OKA6A6d2d2 b5 b5 rrrrrrrrA9A9e10e10a8a8r(2)r(2)d2d2r(5)r(5)r(2)r(2)e10e10c7c7r(2)r(2)r(2)r(2)r(2)r(2)Z4Z4b5b5r(5)r(5)a8a8r(5)r(5)rra8a8e10e10r(5
94、)r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)Follow(A)= b,c,d Follow(A)= b,c,d 语法分析语法分析 分析过程示意分析过程示意： 剩余串剩余串 操操 作作 w w 分析栈分析栈符号串：符号串：bac bac # #0 b5#0 b5 A6 A6 REDUCE(2)REDUCE(2) # #0 b5 A6#0 b5 A6 OKOK # #0#0 # # # # # # c# c# ac# ac# RUDUCE(5)RUDUCE(5) c c#0 b5#0 b5 PUSH(b5),NEXT(w) PUSH(b5),NEXT(
95、w) b b#0 #0 PUSH(c7),NEXT(w) PUSH(c7),NEXT(w) c c REDUCE(3)REDUCE(3) c c#0 b5 a8#0 b5 a8 PUSH(a8),NEXT(w) PUSH(a8),NEXT(w) a a#0#0 b5 b5 a8 a8 c7 c7 Z1 Z1A9A9LR()LR()分析表分析表语法分析语法分析例例【5.145.14】G(E):G(E):E - E + T | TE - E + T | TT - ( E ) | iT - ( E ) | iE- EE- E1 1 (0) (0)E - EE - E2 2 + +3 3 T T4 4
96、 (1)| (1)| T T5 5(2)(2)T - (T - (6 6 E E7 7 ) )8 8(3)| i(3)| i9 9(4)(4)G(EG(E) )1. 1. 构造句柄识别器：构造句柄识别器：-T Ti i0 0E E-OKOKE E+T T-r(1)r(1)T T-r(2)r(2)( (E E) )-r(3)r(3)i ir(4)r(4)E E( ( (i i【解解】+语法分析语法分析r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)8)8+ +3 3T5T5(6(6i9
97、i9r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(1)r(1)r(1)r(1)r(1)r(1)T4T4(6(6i9i9T5T5 E1 E1(6(6i9i9OKOK+ +3 3r(1)r(1)r(1)r(1) ,2 ,2【习题习题】G(E):G(E):E - E + T | TE - E + T | TT - ( E ) | iT - ( E ) | iTE#)(+i iE- EE- E1 1 (0) (0)E - EE - E2 2 + +3 3 T T4 4 (1)| (1)| T T5 5(2)(2)T - (T - (6 6 E E7 7 ) )8
98、8(3)| i(3)| i9 9(4)(4)G(EG(E) )令令 1,2,2,7 1,2,2,7 分别用分别用 2 2，7 7 代之；代之；是是 SLR(1)SLR(1)分析表！分析表！2.2.用用有限自动机确定化有限自动机确定化方法，直接构造方法，直接构造 SLR(1) SLR(1) 分析表：分析表：0 0 E 7 E 79 98 82,72,76 65 54 43 31,21,2注注 2. 2.语法分析语法分析TE#)(+i i3. 3. 用用SLR(1) SLR(1) 分析表，分析表，构造构造确确定的有定的有限自动限自动机机：E2,7E2,7T5T5T4T4T5T5 E1,2 E1,2
99、r(3)r(3)r(3)r(3)r(4)r(4)r(2)r(2)OKOKr(1)r(1)r(4)r(4)r(3)r(3)8)8r(2)r(2)r(1)r(1)r(4)r(4)r(3)r(3)(6(6r(2)r(2)r(1)r(1)(6(6(6(6r(4)r(4)+ +3 3r(2)r(2)r(1)r(1)+ +3 3r(4)r(4)r(3)r(3)i9i9r(2)r(2)r(1)r(1)i9i9i9i90 09 98 82,72,76 65 54 43 31,21,20 0-OKOKE E+T T-r(1)r(1)T T-r(2)r(2)( (E E) )-r(3)r(3)i ir(4)r(4
100、)+ +( ( (i iT Ti i-1,2,2,71,2,2,7分别用分别用2 2，7 7代之代之语法分析语法分析4.4.用用构造项目集合的构造项目集合的方法，构造方法，构造可规约前缀图可规约前缀图：E E-E EE-E-E+TE+TE-E-T TT-T- (E)(E)T-T-i iE EE E-E-EE-EE-E+T+TE-E+E-E+T TT-T- (E)(E)T-T-i i+E-E+TE-E+TT TOKOK# #-r(1r(1) )I I0 0T TE-TE-T-r(2r(2) )I I1 1I I2 2I I3 3I I4 4T-(T-(E)E)E-E- E+TE+TE-E-T TT-T- (E)(E)T-T-i i( (I I5 5T-(ET-(E) )E-E-EE+T+TE EI I6 6) )T-(E)T-(E)I I7 7-r(3r(3) )i iT-T-iiI I8 8-r(3r(3) )T T( (i i+( (i iE EE+E+E+E+T TT T( (E(E(E)(E)i i文法文法语法分析语法分析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 T语法分析语法分析
