第5讲-语法分析-2(预测分析).pdfVIP

第四章 语法分析 FIRST集和 FOLLOW集的计算 哈尔滨工业大学陈鄞 计算文法符号X 的FIRST(X ) FIRST ( X ) ：可以从X 推导出的所有串首终结符构成的集合 如果X * ε，那么ε∈FIRST ( X ) 例 ① E →TE FIRST ( E ) = { ( id } ② E → +TE |ε FIRST ( E ) = { + ε } ③ T →FT FIRST ( T ) = { ( id } ④ T → *FT |ε FIRST ( T ) = { * ε } ⑤ F → (E)|id FIRST ( F ) = { ( id } 算法 不断应用下列规则，直到没有新的终结符或ε可以被 加入到任何FIRST 集合中为止 如果X 是一个终结符，那么FIRST ( X ) = { X } 如果X 是一个非终结符，且 X →Y …Y ∈P (k≥1) ，那么如 1 k 果对于某个i ，a在FIRST (Y ) 中且ε在所有的 i * FIRST(Y ) , … , FIRST(Y ) 中( 即Y ...Y  ε) ，就把a加入 1 i-1 1 i-1 到FIRST( X ) 中。如果对于所有的j = 1,2, . . . , k ，ε在 FIRST(Y ) 中，那么将ε加入到FIRST( X ) j 如果X →ε∈P ，那么将ε加入到FIRST( X ) 中 计算串X X …X 的FIRST 集合 1 2 n 向FIRST(X X …X )加入FIRST(X ) 中所有的非ε符号 1 2 n 1 如果ε在FIRST(X ) 中，再加入FIRST(X ) 中的所有非ε符号； 1 2 如果ε在FIRST(X )和FIRST(X ) 中，再加入FIRST(X ) 中的 1 2 3 所有非ε符号，以此类推 最后，如果对所有的i ，ε都在FIRST(Xi) 中，那么将ε加入到 FIRST(X X …X ) 中 1 2 n 计算非终结符A 的FOLLOW(A) FOLLOW(A) ：可能在某个句型中紧跟在A 后边的终结符a 的集合 * * FOLLOW(A)={a| S  αA aβ, a ∈V ，α,β∈(V ∪V ) } T T N 如果A 是某个句型的的最右符号，则将结束符“$”添加到FOLLOW(A) 中 例 ① E →TE FIRST ( E ) = { ( id } FOLLOW( E ) = { $ ) } ② E →