编译原理第四章.ppt

第四章自顶向下语法分析

自顶向下：自底向上：例4.2:G[E]:E?T|EATT?F|TMFF?(E)|i分析符号串i+i*iA?+|-M?*|/例4.3:G[S]:S?b|Sa分析baaSSSSSbSaSaSaSabSaSab分析时可能出现:(1)回溯原因:推导过程中有多个侯选式可供选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。例4.1(2)死循环。例4.2：在没有对当前输入符号匹配就进入处理S的过程，无法确定什么时候才用S?b替换,造成死循环.原因:左递归已知文法G[E]:E→ETE|（E）|iT→*|+是否存在左递归，若有消除4.1.2回溯问题在分析中，A?x1|x2|…|xn，难以确定采用哪个规则，若从x1到xn逐个来试,则效率太低。在自顶向下分析过程中，对候选式的选择可根据当前输入符号来决定.例教材4.2:S?aBCB?bC|dBC?c|a分析句子adbcaS=aBC4.2三种终结符集(重点)1.First集(首符号集)定义:对于文法G的所有非终结符的每个候选式β，其终结首符号集称为First集First(β)={a|βay,a∈VT,y∈V*}特别,若β=ε,则First(β)=Φ例:G[E]:E?E+T|TT?T*F|FF?(E)|i则:First(E+T)={(,i}First(T)={(,i}First(T*F)={(,i}Follow(U)={a|S…Ua…,a∈VTU{#}}3.Select集(可选集)定义:文法G[S],有规则A?β,则该规则的可选集为:First(β),当β≠εSelect(A?β)=Follow(A),当β=ε例:G[S]:S?aBc|bBB?bB|d|ε例:G[S]:S?aA|bA?cAS|ε4.LL(1)文法思想4.判定LL(1)文法(重点)文法是非左递归的满足条件无回溯性分析表的构造：思路：(1)产生式子填到何处？例2：已知文法G[S]：S→(L)|aL→L，S|S构造LL(1)分析表，并分析串（a,a,a）消除左递归：S?(L)|aL?SL’L’?,SL’|ε(2)求Select(S?(L))={(}Select(S?a)={a}Select(L?SL’)={(,a}Select(L’?,SL’)={,}Select(L’?ε)=follow(L’)={#,)}（3）LL(1)分析表（4）分析符号串总结重要概念：FirstfollowselectLL(1)文法的判断：如果不满足，会修改给定一个文法，给定一个句子，用LL(1)分析Follow(U)={a|S…Ua…,a∈VTU{#}}自顶向下：(重点)3.LL(1)文法逻辑分析:(重点)1.试消除下面文法G[