自顶向下语法分析方法.ppt

第四章 语法分析——自上而下分析 语法分析就是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序).语法分析常用的方法:自顶向下分析与自底向上分析.而自底向上分析又可分为:算符优先分析与LR分析. 自顶向下分析也称面向目标的分析方法,也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子. 自顶向下分析方法分为:确定的和不确定的.确定的分析方法需要对文法有一定的限制;而不确定的方法是一种穷举的试探方法. 5.1 确定的自顶向下分析 若有文法G1[s]： S-pA|qB A-cAd|a B-dB|b 构造输入串W=pccadd的语法树。 该文法的特点： 1）每个产生式的右部都由终结符号开始； 2）若两个产生式有相同的左部，则它们的右部由不同的终结符开始。 文法G2[S]为： S-Ap S-Bq A-a A-cA B-b B-dB 给出输入串W=ccap的推导过程。 该文法的特点： 1）产生式的右部不全是由终结符开始； 2）若两个产生式有相同的左部，则它们的右部是由不同的终结符或非终结符开始； 3）文法中无空产生式。 文法G3[S]为： S-aA S-d A-bAS A- ? 给出W=abd的推导过程。 5.2 LL(1)文法的判别 判断LL(1)文法的步骤: 1.求出能够推出?的非终结符 1)初始化 2) 扫描文法的产生式 a)删除所有右部含有终结符的产生式,若以某一非终结符为左部的所有产生式都被删除,则将数组中对应该非终结符的标记修改为“否”; b)若某一非终结符的某一产生式右部为?,则将数组中对应该非终结符的标志置为“是”,并从文法中删除该非终结符的所有产生式. 判别步骤(续) 3) 扫描产生式右部的每一符号 a)若所扫描到的非终结符号在数组中的对应标志是“是”,则删去该非终结符,若这使得产生式右部为空,则对产生式左部的非终结符在数组中对应的标志改为“是”,并删去该非终结符为左部的所有产生式; b)若所扫描到的非终结符号在数组中的对应标志是“否‘,则删去该产生式,若这使得产生式左部非终结符的有关产生式都被删去,则将数组中该非终结符对应的标志改成”否“. 4) 重复3),直到扫描完一遍文法的产生式,数组中非终结符对应的特征再没有改变为止. 2.计算FIRST集 1)计算每一文法符号X的FIRST集-----FIRST(X) (a)若X?VT,则FIRST(X)={ X }; (b)若X?VN且有产生式X-a….,a ? VT,则a ? FIRST(X); (c)若X?VN且有产生式X-?,则 ? ? FIRST(X); (d) X?VN且Y1, …,Yi都?VN,而有产生式X- Y1 …Yn.当Y1, …,Yi-1= ?(其中1?i ?n),则FIRST(Y1)-{?}, …, FIRST(Yi-1)-{?},FIRST(Yi)都包含在FIRST(X)中; (e)若(d)中所有Yi= ?(i=1, …,n),则FIRST(X)=FIRST(Y1)? FIRST(Y2) ? … ? FIRST(Yn) ?{?} 计算FIRST集(续) 2)求每个符号串的FIRST集 a)若符号串? ?V*, ?=X1…Xn,当X1不能= ?,则置FIRST(?)=FIRST(X1); b)若对任何j(1?j?i-1, 2?i?n), ? ? FIRST(Xj)则FIRST(?)=(FIRST(X1)-{?}) ? (FIRST(X2)-{?}) ?… ? (FIRST(Xi-1)-{?}) ?FIRST(Xi) ; c)当所有FIRST(Xj)都含有?时,则 FIRST(?)= (? FIRST(Xj)) ?{?}. 3.计算FOLLOW集 对文法中每一A ?VN计算FOLLOW(A) a)设S为文法中开始符号,将“#”加入FOLLOW(S)中; b)若A-?B?是一个产生式,则将FIRST(?)的非空元素加入FOLLOW(B)中;若?= ?,则将FOLLOW(A)也加入FOLLOW(B)中. c)重复使用(b)直到每个非终结符的FOLLOW集不再增大为止. 1.提取左公共因子提取左公共因子是指当文法中含有形如： A→α?1|α?2|...|α?n|?1|?2|...|?m 的规则， 可以把它修