第4章自上而下语法方法.ppt

1、FIRST集及其计算方法 （2）FIRST集的计算方法 对G中的文法符号X，X∈VT∪VN，则FIRST(X)的计算方法为： ①若X∈VT，则 FIRST(X) ={ X }; ②若X∈VN，则 规则一：若有产生式 X→a…，其中a∈VT，则a∈FIRST(X)； 规则二：若有产生式X→?，则 ?∈FIRST(X)； 规则三：若有产生式 X→Y… ，其中 Y∈VN，则把FIRST(Y)中的所有非ε元素都加入到FIRST(X)中； 1、FIRST集及其计算方法 （2）FIRST集的计算方法 更一般的情形，若有产生式X→Y1Y2…Yn，其中 Y1，Y2，…Yi-1∈VN （1i≤n），则： 将FIRST(Y1)中的所有非ε元素都加入到FIRST(X)中；若对任意 j（1≤j≤i-1），均有ε∈FIRST(Yj)（即 ），则将FIRST(Yi)中的所有非ε元素都加入到FIRST(X)中；若所有FIRST(Yj)均含有ε（j=1,2,…,n），即 ，则把ε加入到FIRST(X)中。 ③反复使用以上规则，直至每个非终结符的FIRST集不再增大为止。 1、FIRST集及其计算方法 【例4.7】 文法G[E]如下所示，求该文法所有非终结符的FIRST集。 　　 A FIRST(A) E E′ T T′ F (,i (,i (,i +,? *,? 1、FIRST集及其计算方法 现在，我们能够对文法G的任何符号串α=X1X2…Xn，构造集合FIRST(α)。其方法如下： 　　①置 ； 　　②当 ，若对任何 ，有 ，则将  中所有元素加入到 中； 　　③若对所有的 ，均有 ，则 。 特别地，当α=?时，FIRST(α)={?}。 1、FIRST集及其计算方法 【例4.8】 接着例4.7的题，求文法G[E]的所有候选式的FIRST集。 　　 E E′ T T′ F FIRST (,i +,? (,i *,? (,i 返回 2、FOLLOW集及其计算方法 （1）FOLLOW集的定义 给定文法 ，对于G中任意非终结符A，我们定义A的 FOLLOW集 为： 特别地，若 ，则规定 # FOLLOW(A) 。 FOLLOW(A)的直观意义 FOLLOW(A)是所有句型中出现在紧接A之后的终结符或‘#’。 2、FOLLOW集及其计算方法 （2）FOLLOW集的计算方法 对于文法G的每个非终结符A，FOLLOW(A)的计算方法如下： 规则一：对于文法的开始符号S，置#于FOLLOW(S)中； 规则二：若有产生式 ，其中 ，则将 加至FOLLOW(B)中； 规则三：若有产生式 或 （ ，即 ），则把FOLLOW(A)加至FOLLOW(B)中； 规则四：反复使用规则②和③，直至每个非终结符的FOLLOW集不再增大为止。 2、FOLLOW集及其计算方法 【例4.9】 如同例4.7中的文法G[E]，求其所有非终结符的FOLLOW集。 　　 A FIRST(A) FOLLOW(A) E (,i E′ +,? T (,i T′ *,? F (,i #,) +,#,) *,+,#,) #,) +,#,) 返回 3、LL(1)文法及LL(1)判定条件 （1）LL(1)文法 LL(1)文法是一种满足构造不带回溯的自上而下分析的文法。这里，LL(1)中的第一个L表示从左至右扫描输入串，第二个L表示最左推导，1表示分析时每一步只需向前查看一个符号。 类似地, 可有LL(k)文法， 即向前查看k个符号才能确定选用哪个产生式