LL_综合练习.pptVIP

第4章 语法分析 —— 自顶向下分析法 综合练习 已知文法G[E]如下： E→E+T | E-T | T T→T*F | T/F | F F→(E) | i 请用LL(1)分析法识别符号串： # ((i+i)*i-i)/i # 一、判断G[E]是否为LL(1)文法 1. 消除递归，得到文法G’[E] ： 基本步骤如下： （1）首先建立一个以文法非终结符为元素的一维数组X，对应每个非终结符设置一个标志位，以记录能否推出ε。其值有三种情况：“未定”、“是”、“否”。 例如，本例中： （2）其次，按下述步骤逐步更新标志位： 依次扫描文法每一条产生式 删除所有右部含终结符的产生式。若因此使得以某非终结符为左部的所有产生式都被删除，则置该非终结符的标记为“否”。 若某非终结符存在一条右部为ε的产生式，则置该非终结符的标志为“是”，并删除以该非终结符为左部的所有产生式。同时将对应标识改为“是”。 扫描产生式X→Y1Y2…Yn的右部的每一符号Yi： 若某非终结符Yi标志为“是”，则从X右部删去该非终结符Yi ，若进而使得X产生式右部为空，则置X的标志为“是”，并删除以X为左部的所有产生式。 若某非终结符Yi标志为“否”，则删去X产生式。若因此而使得左部为X的有关产生式都被删去，则置X的标志为“否”。 重复步骤②，直到扫描完一遍文法的产生式，非终结符标志位不再改变为止。 结果如下页所示。 （1）单个文法符号的FIRST 对于文法中的每一个符号X?（VN∪VT），构造FIRST（X）时，只要连续使用下列步骤，直至FIRST集不再扩大为止。 若X?VT，则FIRST（X）＝{X}； 若X?VN，存在X→?产生式，则??FIRST（X）； 若X?VN，存在X→a…产生式，a ?VT ，则a?FIRST（X）； 若X→Y1Y2…Yn是产生式，当Y1, …, Yi-1都?VN且都能 ?（其中1≤i≤n），则 FIRST(X) =： (FIRST(Y1)-{?})∪(FIRST(Y2)-{?})∪…∪(FIRST(Yi-1)-{?})∪FIRST(Yi) 若所有的Yi均 ?，i＝1, 2, …, k，则： FIRST(X)= FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{?} 本例中，非终结符的FIRST集如下： FIRST(E)={(，i} FIRST(E‘)={+，-，ε} FIRST(T)={(，i} FIRST(T’)={*，/， ε} FIRST(F)={(，i} （2）符号串的FIRST 对符号串?=X1X2…Xn，可按下示步骤构造FIRST (?)： 若?=?，则FIRST(?)={?}; 若X1不能 ? ，则FIRST(?)=FIRST(X1) ； 若对任何1≤j≤i-1，2≤i≤n，有??FIRST(Xj)，则 特别地，若所有FIRST(Xj)均含有?（1≤j≤n），则 本例中各个候选式的FIRST集如下： FIRST(+TE’)={+} FIRST(-TE’)={-} FIRST(TE’)={(，i} FIRST(*FT’)={*} FIRST(/FT’)={/} FIRST(FT’)={(，i} FIRST((E))={(} FIRST(i)={i} 4. 判断是否存在回溯，若存在，则消除回溯 本例中得非终结符的FOLLOW集 FOLLOW(E)={#，)} FOLLOW(T)={+，-，#，)} FOLLOW(F)={*，/，+，-，#，)} FOLLOW(E‘)={#，)} FOLLOW(T’)={+，-，#，)} 本例中的LL(1)分析表如下： 【解】按如下步骤进行： 一、判断G[E]是否为LL(1)文法 判断是否存在左递归，若存在，则消除左递归； 确定每一个非终结符能否?ε； 求解所有非终结符、所有候选式的FIRST集； 判断是否存在回溯，若存在，则消除回溯； 求所有非终结符的FOLLOW集； 构造LL(1)分析表； 判断是否为LL(1)文法。 二、使用LL(1)分析法识别指定符号串； 三、根据识别过程，绘出语法分析树。 E’→+TE’ E’ →-TE’ E →TE’ T’ →*FT’ T’ →/FT’ T →FT’ F →(E) F →i E’ →ε T’ →ε P83~85 未定 未定 未定 未定 未定 初值 T E F T E 2. 确定每一个非终结符能否推出ε 是 是 未定 未定 T 观察右部符号 是 否 否 否 4 右部含ε的产生式 是 否 未定 未定 3 删除右部含终结符的产生式 未定 否 未定 未定 2 初始化 未定 未定 未定 未定 1 备注 E F T E 遍序 非终结符能否推出ε的情况： 3. 求FIRST集