第4章 语法分析 自上而下 3.0.ppt

如：M[X，a]={X—＞UVW},就用WVU（U在顶）替换栈顶的X作为输出； 如：M[X，a]=error，则调用error程序。 对第3）条， X∈VN，查分析表M的元素M[X，a] 分析表格式 F —＞(E) F —＞id F T′—＞ ε T′—＞ ε T′—＞ *FT′ T′—＞ ε T′ T —＞ FT′ T —＞ FT′ T E′—＞ ε E′—＞ ε E′—＞ +TE′ E′ E —＞ TE′ E —＞ TE′ E # ) ( * + id E —＞ TE′ E′—＞ +TE′|ε T —＞ FT′ T′—＞ *FT′ |ε F —＞（E）|i 例4.5 按预测分析程序，对于输入 id+id*id 所作动作如下所示： 栈 输 入 输 出 1 #E id+id*id# 2 #E′T id+id*id# E—＞TE′ 3 #E′T′F id+id*id# T—＞FT′ 4 #E′T′id id+id*id# F—＞id 5 #E′T′ +id*id# 6 #E′ +id*id# T′—＞ε 7 #E′T′+ +id*id# E′—＞ +TE′ #E′T id*id# #E′T′F id*id# T—＞ FT′ M[ E, id ] = E —＞TE′ M[ T, id ] = T —＞FT′ 左部出栈，右部反序压栈 ! M[F, id ] = F —＞id 匹配，id出栈 输入串指针后移 X a E id T id F id id id 栈 输 入 输 出 10 #E′T′id id*id# F—＞id 11 #E′T′ *id# 12 #E′T′F* *id# T′—＞*FT′ 13 #E′T′F id# 14 #E′T′id id# F—＞ id 15 #E′T′ # 16 #E′ # T′—＞ε # # E′—＞ε 有: X=a=#，分析成功。 id id X a T ′ id * * F id id id T’ # E’ # # # 结论： ①输出的产生式就是最左推导的产生式。栈中放右 部，等待与α匹配； ②表指出（栈顶，a）时，如何扩充树，出错马上发 现。 实质： 栈：残缺规范句型 表：指出VN按哪一条扩充，依赖于VT 上述分析过程生成的语法树： F —＞(E) F —＞id F T′—＞ ε T′—＞ ε T′—＞ *FT′ T′—＞ ε T′ T —＞ FT′ T —＞ FT′ T E′—＞ ε E′—＞ ε E′—＞ +TE′ E′ E —＞ TE′ E —＞ TE′ E # ) ( * + id id + id * id # ： + E? T F T? * F T? id id ε ε E T E? F T? id ε 2、分析表的构造 分析表格式： F —＞(E) F —＞id F T′—＞ ε T′—＞ ε T′—＞ *FT′ T′—＞ ε T′ T —＞ FT′ T —＞ FT′ T E′—＞ ε E′—＞ ε E′—＞ +TE′ E′ E —＞ TE′ E —＞ TE′ E # ) ( * + id 思路： 1）把产生式填到何处？ 2）按α ? 将产生式分为两种： 一种是：α a… 另种是：α ε 先要构造两个与G有关的集合：FIRST(α)和FOLLOW(A)； 1）定义：若G，α∈V*，S，A∈VN FIRST