第四章自顶向下的语法分析

第四章自顶向下的语法分析内容摘要：

hen FIRST(X):=FIRST(X)∪ {ε}。 2020/11/17 20 LL(1)文法的判定 算法 计算 FIRST(α)。 输入：文法 G=(V， T， P， S)， α(V∪ T)*， α= X1… Xn。 输出： FIRST(α)。 步骤： 1．计算 FIRST(X1)。 2． FIRST(α):= FIRST(X1){ε}。 3． k:=1。 4． while (ε∈ FIRST(Xk) and kn) do begin 5． FIRST(α):= FIRST(α)∪ (FIRST(Xk+1){ε})。 6． k:=k+1 end 7． if (k=n and ε∈ FIRST(Xk)) then FIRST(α):=FIRST(α)∪ {ε}。 2020/11/17 21 例 表达式文法的语法符号的 FIRST 集 FIRST(F)={（ , id} FIRST(T)=FIRST(F)={（ , id} FIRST(E)=FIRST(T)={（ , id} FIRST(E39。 )={+， ε} FIRST(T39。 )={*,ε} FIRST(+)={+}, FIRST(*)={*} FIRST(（ )={（ } FIRST(） )={） } FIRST(id)={id} E→TE39。 E39。 →+TE’|ε T→FT39。 T39。 →*FT’|ε F→(E)|id 2020/11/17 22 LL(1)文法的判定 算法 计算 FOLLOW集。 输入：文法 G=(V， T， P， S)， AV。 输出： FOLLOW(A)。 步骤： 1．对 X∈ V， FOLLOW(X) := 。 2． FOLLOW(S) := {}， 为句子的结束符。 3．对 X∈ V，重复下面的第 4步到第 5步，直到所有FOLLOW集不变为止。 4．若 A→αBβ∈ P，则FOLLOW(B):=FOLLOW(B)∪ FIRST(β)–{ε}。 5．若 A→αB或 A→αBβ∈ P，且 β ε， A≠B，则 FOLLOW(B):=FOLLOW(B)∪ FOLLOW(A)。 *2020/11/17 23 例 表达式文法的语法变量的 FOLLOW 集 FOLLOW(E) = { , ) } FOLLOW(E39。 )= FOLLOW( E ) = { , ) } FOLLOW(T) = {FIRST(E39。 ){ε}}∪ FOLLOW(E)∪ FOLLOW(E39。 )= {+,),} FOLLOW(T39。 )= FOLLOW(T)= {+,),} FOLLOW(F) = FIRST(T’)∪ FOLLOW(T)∪ FOLLOW(T39。 ) ={*,+,),} E→TE39。 E39。 →+TE39。 |ε T→FT39。 T39。 →*FT39。 |ε F→(E)|id FIRST(F)={（ ,id} FIRST(T)=FIRST(F)={（ ,id} FIRST(E)=FIRST(T)={（ ,id} FIRST(E39。 )={+， ε} FIRST(T39。 )={*,ε} 2020/11/17 24 表达式文法是 LL(1) 文法  E → T E39。  E39。 → + T E39。 ｜ ε  T → F T39。  T39。 → * F T39。 ｜ ε  F → ( E ) ｜ id 考察  E39。 : + 不在 FOLLOW( E39。 ) = { ), }  T39。 : * 不在 FOLLOW( T39。 ) = { +, ), }  F: ( 和 id 不同 2020/11/17 25 非 LL(1)文法的不确定性 例 对文法  S→cAd  A→ab|a 输入 cad 的分析 S d c A b a S d c A a 2020/11/17 26 不确定性的解决方法 1) 采用回溯算法  过于复杂，效率低下 2）改写文法  将非 LL(1)文法改写为等价的 LL(1)文法  无法改写时：  增加其它的判别因素  文法过于复杂，无法用自顶向下方法处理 2020/11/17 27 预测分析法  系统维持一个分析表和一个分析栈，根据当前扫描到的符号，选择当前语法变量（处于栈顶）的候选式进行推导 ——希望找到相应输入符号串的最左推导。  一个通用的控制算法  一个分析栈， 为栈底符号  一个输入缓冲区， 为输入串结束符  一个统一形式的分析表 M  不同语言使用内容不同的分析表 2020/11/17 28 预测分析器的构成 输入缓冲区 (符号序列 ) 栈 预测分析程序 预测分析表 M 输出的 产生式序列 2020/11/17 29 系统的执行与特点  在系统启动时，输入指针指向输入串的第一个字符，分析栈中存放着栈底符号 和文法的开始符号。  根据栈顶符号 A和读入的符号 a，查看分析表 M,以决定相应的动作。  优点： 1）效率高 2）便于维护、自动生成  关键 —— 分析表 M的构造 2020/11/17 30 预测分析程序的总控程序 算法 预测分析程序的总控程序。 输入：输入串 w和文法 G=(V, T, P, S)的分析表 M。 输出：如果 w属于 L(G)，则输出 w的最左推导，否则报告错误。 步骤： 1．将栈底符号 和文法开始符号 S压入栈中。 2． repeat 3． X:=当前栈顶符号。 4． a:=当前输入符号。 5． if X∈ T∪ {} then 6． if X=a then 7． {if X≠ then begin 8． 将 X弹出栈。 9． 前移输入指针 10． end} 2020/11/17 31 预测分析程序的总控程序 11． else error 12． else 13． if M[X, a]=Y1Y2… Yk then begin 14． 将 X弹出栈。 15． 依次将 Yk， … ， Y2，。