编译原理与技术.pptVIP

《编译原理与技术》讲义 编译原理与技术 －－ 自顶向下分析 自顶向下分析 分析树的建立 从根（开始符号）出发，从上而下，从左自右为输入串建立分析树 为输入串寻找一个最左推导 自顶向下分析 e.g.1 文法G0： S ?A B C A ?a B ?b C ?c 自顶向下分析 e.g.1 文法G0： S ?A B C A ?a B ?b C ?c 自顶向下分析 e.g.1 文法G0： S ?A B C A ?a B ?b C ?c 自顶向下分析 e.g.1 文法G0： S ?A B C A ?a B ?b C ?c 自顶向下分析 e.g.1 文法G0： S ?A B C A ?a B ?b C ?c 自顶向下分析 e.g.1 文法G0： S ?A B C A ?a B ?b C ?c 自顶向下分析 e.g.1 文法G0： S ?A B C A ?a B ?b C ?c 自顶向下分析 e.g.1 文法G0： S ?A B C A ?a B ?b C ?c 自顶向下分析 e.g.1 文法G0： S ?A B C A ?a B ?b C ?c 自顶向下分析 e.g.1 文法G0： S ?A B C A ?a B ?b C ?c 自顶向下分析 文法G0较简单－非终结符只有唯一的产生式 试探分析法 当待分析（展开）的非终结符对应多条产生式，可以选择其一进行尝试分析（最左推导）； 当此产生式无法与输入串“匹配”时则需要“回溯”－即放弃已建立的部分分析树，同时调整输入串指针恢复到此次分析前位置，再另选一产生式重新分析。 只有当所有的所有的尝试均不成功，分析失败！ 自顶向下分析 试探分析法 e.g.2 文法G1如下 S ? x A y A ? ab A ? a 输入串 xay$ 的分析过程。 自顶向下分析 试探分析法 e.g.2 文法G1： （1）S ? x A y （2）A ? ab （3）A ? a 输入串 xay$的 分析过程。 自顶向下分析 试探分析法 e.g.2 文法G1： （1）S ? x A y （2）A ? ab （3）A ? a 输入串 xay$的 分析过程。 自顶向下分析 试探分析法 e.g.2 文法G1： （1）S ? x A y （2）A ? ab （3）A ? a 输入串 xay$ 的分析过程。 自顶向下分析 试探分析法 在文法有左递归特征时，可能导致无限循环而此时无法读入任何输入符（输入指针保持不变）。 如表达式文法G2： E?E+T | T T?T*F | F F?(E) | id 自顶向下分析 预测分析法 对于待分析的非终结符A，可以根据当前输入符号（记号）来准确唯一地选择A的某一产生式。若该产生式“匹配”成功，则意味着A分析成功；若匹配失败，则即使选择A的其它产生式也会导致A分析失败（因而不需要回溯）。 Case 1:文法G1 A ? a b A的两个产生式右部具有 A ? a 相同的（非空）前缀a 那么A面临输入符a选择谁呢？ 自顶向下分析 预测分析法 提左因子的文法变换 文法G1中， A ? a b A ? a A’ A ? a A’ ? b | ? 自顶向下分析 预测分析法 e.g.3 文法G1中， A ? a b A ? a A’ A ? a A’ ? b | ? A 面临 a 时有唯一的产生式A ? a A’； A’面临 b 时可以选A’ ? b； 空产生式 A’ ? ? 何时选用呢？ 自顶向下分析 预测分析法 提左因子变换的一般形式 自顶向下分析 预测分析法 Case 2: 文法G2 E ? E + T E的产生式的（直接）左递归妨碍了 E ? T 输入符号的有效读入（实际上不读） 并导致死循环。 消除左递归（A ?＋ A…）的文法变换 － 直接左递归的消除（A ?A…） 自顶向下分析 预测分析法 e.g.4 消除文法G2中的直接左递归。 E? E + T E? T E’ E? T E’? + T E’ |