[编译原理ppt33.ppt

3.3 自上而下语法分析 主要内容 自上而下语法分析的基本概念 无回溯自顶向下语法分析器（预测语法分析器） LL(1)文法 3.3.1 自上而下分析的一般方法 自上而下语法分析的目的是为输入字符串寻找最左推导，或者说，从根节点（文法开始符号）开始，自上而下、从左到右地为输入字符串建立一棵分析树，并以预先确定的顺序创建分析树的节点。 例：假定有文法 (1) S→aCb (2) C→cd|c 分析输入串acb (记为?) 存在的问题 文法左递归问题 一个文法是含有左递归的，如果存在非终结符A 自上而下的分析法无法具有左递归性的文法 例： A→A? | ... 因为虚假匹配导致回溯的问题 例如 A→ αβ1|αβ2，输入字符串由从α导出的非空串开始，则无法判断用哪个产生式去匹配 3.3.2 LL(1) 文法 消除回溯的基本原则：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。 若此候选获得成功匹配，则这种匹配决不会是虚假的；若此候选无法完成匹配任务，则任何其它候选也肯定无法完成 如果不回溯，对文法有什么要求？ 令G是一个不含左递归的文法，对G的所有非终结符的每个候选?定义它的终结首符集FIRST(?)为： FIRST(?)集合包括了?的所有可能推导的开头终结符或可能的?。 要不回溯，对于文法就必须要求： 对于任一非终结符A，它的所有候选首符集两两不相交，即A的任何两个不同候选αi和αj，有 FIRST(αi) ∩ FIRST(αj)=φ (i?j) 如果??FIRST(A)，则这时需要考虑FOLLOW(A) 当非终结符A面临输入符号a，且a不属于A的任意候选首符集但A的某个候选首符集包含ε时，就一定可以使A自动匹配？ 文法G[S],对于非终结符A，定义 FOLLOW(A)={a| S?...Aa..., a?VT} 特别是，当S ?...A，则规定$?FOLLOW(A) FOLLOW(A)是所有句型中出现在紧接A之后的终结符或‘$ 对于文法的任意两个产生式A→ ?|β都满足 FIRST(?) ∩FIRST(β)= φ 若β ? ε，那么FIRST(?) ∩FOLLOW(A)= φ 则该文法是LL(1)文法。 LL(1)中第一个L代表从左到右扫描输入，第二个L代表产生最左推导，1代表在决定语法分析器的每步动作时向前扫描一个输入符。 FIRST和FOLLOW集的计算 FIRST(?)集合包括了?的所有可能推导的开头终结符或可能的?。 FOLLOW(A)是所有句型中出现在紧接A之后的终结符或$ FOLLOW(A)={a| S? ?Aaβ, a?VT} 特别是，当S ? ?A，则规定$?FOLLOW(A) FIRST集合的计算 对每一文法符号X?VT∪VN构造FIRST(X) 连续使用下面的规则，直至每个集合FIRST不再增大为止： 1. 若X?VT，则FIRST(X)＝{X}。 2. 若X→?也是一条产生式，则把?也加到FIRST(X)中。 3.若X?VN，且有产生式X→Y1Y2…Yk，则 a) 把FIRST(Y1)中的所有非?-元素都加到FIRST(X)中； b) 对于某个i，1?j?i-1，FIRST(Yj)都含有?(即Y1…Yi-1??)， 则把FIRST(Yi)中的所有非?-元素都加到FIRST(X)中； c) 若所有的FIRST(Yj)均含有?，j＝1，2，…，k，则把?加到FIRST(X)中。 对文法G的任何符号串?=X1X2…Xn构造集合FIRST(?)。 1. 置FIRST(?)＝FIRST(X1)\{?}； 2. 若对任何1?j?i-1，??FIRST(Xj)，则把FIRST(Xi)\{?}加至FIRST(?)中；特别是，若所有的FIRST(Xj)均含有?，1?j?n，则把?也加至FIRST(?)中。显然，若?＝?则FIRST(?)＝{?}。 FOLLOW集合的计算 对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止： 1. 对于文法的开始符号S，置$于FOLLOW(S)中； 2. 若A→?B?是一个产生式，则把FIRST(?)\{?}加至FOLLOW(B)中； 3. 若A→?B是一个产生式，或A??B?是一个产生式而??? (即??FIRST(?))，则把FOLLOW(A)加至FOLLOW(B)中。 例：对于文法G(E) E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | id 构造每