编译原理及其习题解答武汉大学出版社教程chap6节.ppt

* * 编译原理 Compiler Principles 算法描述P174 流程图P175 例子：P176及表6.5 算符优先分析算法描述 编译原理 Compiler Principles 优先函数 优先函数比优先矩阵节省空间 文法中有n个文法符号时，优先矩阵中有(n+1)2个元素。如：假设某文法中有99个终结符，其算符优先关系矩阵则有10000个元素，每个元素至少用2个二进制位来表示，也需要20000位，即2500个字节。 在实际应用中，往往用优先函数来代替优先矩阵来表示优先关系。具有n个终结符的算符文法（或具有n个文法符号的简单优先文法），只需2(n+1)个单元存放优先函数。 优先函数的构造 用关系图构造优先函数 用迭代法构造 编译原理 Compiler Principles 优先函数的定义 为了节约存储空间和便于执行比较运算?，定义两个优先函数f和g，它们是从终结符号映射到整数的函数。对于文法符号R和S，定义择f和g,使之满足： 1．当 R · S 时, f(R) g(S); ???? 2. 当 R = S 时, f(R)= g(S); ??? 3. 当 R · S 时, f(R) g(S)。 ? 于是，R和S之间的优先关系，可以由比较f(R) 与g(S)的大小来决定。 f:入栈优先函数； g:比较优先函数。 损失:错误检测能力降低，例如： id ·id不存在, f(id) g(id)可比较。 · 编译原理 Compiler Principles 优先函数 例子 简单表达式文法的算符优先关系矩阵： 线性化后，优先函数为： 在进行语法分析时，每当需要查询符号对(Si,Sj)之间的优先关系，比较f(Si)和g(Sj）的大小即可。 编译原理 Compiler Principles 关于优先函数的3个重要事实(1) 不是所有的优先矩阵都能线性化。 a b a = . b = = f(a)=g(a) f(a)g(b) f(b)=g(a) f(b)=g(b) 于是有： f(a)=g(b) 编译原理 Compiler Principles 关于优先函数的3个重要事实(2) (2) 对于给定的优先矩阵，若优先函数存在，则优先函数不唯一，即存在无穷多个f和g满足条件。 + - * / ^ ( ) id $ f 3 3 5 5 5 1 7 7 1 g 2 2 4 4 6 6 1 6 1 等价于 编译原理 Compiler Principles 关于优先函数的3个重要事实 (3) (3) 优先矩阵线性化后，每一对符号之间，都能够进行比较。对于原先不存在优先关系的符号对，因为也能比较，所以，在分析过程中，当输入串存在语法错误时，可能被掩盖（至少是推迟发现）。 编译原理 Compiler Principles 优先函数构造的两种方法 Bell法 1.有向图法(Bell法) 若优先文法中的所有符号（包括#)为n个，{A1,A2,……An}，则： 作一个具有2n个结点的有向图。通常的，分为上下两排，各n个结点，上面一排结点的标记为fAi，上排结点标记为gAi 。 若Ai . Aj ,则从fAi到gAi画一条箭弧。 若Ai . Aj ,则从gAi到fAi画一条箭弧。 若Ai =. Aj ,则从fAi到gAi画一条双箭弧。 编译原理 Compiler Principles 优先函数构造的两种方法 Bell法 (3) 给每个结点赋予一个数，此数等于从该结点出发所能到达的结点（包括该结点本身）的个数，即为f(Ai)或g(Ai)的值。 (4) 按照优先关系矩阵，检查函数f(Ai)或g(Ai)的值是否符合优先函数的定义。 编译原理 Compiler Principles 优先函数构造Bell法 举例1 文法G[E]： E→E+T | T T →T*F | F F → id gid fid f* g* g+ f+ f$ g$ = id + * $ f 6 4 6 2 g 7 3 5 2 编译原理 Compiler Principles 优先函数构造Bell法 举例2 是否存在优先函数？ a b f 4 4 g 4 4 ga fa gb fb a b a = . b = = 编译原理 Compiler Principles 优先函数构造Bell法 举例3 课本例6.19 p179 图6.11 当一个优先文法的优先关系矩阵的阶数比较高时，bell法线性化过程很难手工实现。可以考虑用布尔矩阵来构造优先函数。下面介绍一个容易在