吉大编译课件编译器开发3.ppt

编译程序的面向对象设计与实现 Dr. Zheng Xiaojuan Associate Professor Software College of Northeast Normal University April. 2009 阶段三：语法分析器开发 项目需求 读入词法分析的输出结果token序列； 对token序列进行语法分析生成语法正确的与源程序结构相对应的语法分析树； 能够指出语法错误所在位置。 一、编译原理内容 语法分析程序的功能 所需编译知识关联图 所需编译知识关联图 一、Context Free Grammar (CFG) 定义为四元组(VT,VN,S,P) VT是有限的终极符集合 VN是有限的非终极符集合 S是开始符，S? VN P是产生式的集合，且具有下面的形式： A?X1X2…Xn 其中A?VN，Xi? (VT?VN) ，右部可空。 二、Top-down parsing 自顶向下语法分析方法的前提条件 G = (VT, VN, S, P) For any A? VN, For any two productions of A, Predict(A ? ?1)? Predict(A ? ?2) = ? (同一个非终极符的任意两个产生式的predict集合互不相交) 这个条件保证:针对当前的符号和当前的非终极符,可以选择唯一的产生式来进行推导; 三、 Grammar Transformation 消除公共前缀(left factoring) 公共前缀 A ? ??1 | … | ??n| ?1|…| ?m 提取公因子 A ? ?A’| ?1|…| ?m A’ ? ?1 | … | ?n 消除左递归(left recursion) 直接左递归:A ? A(?1 | … | ? n)| ?1|…| ?m 消除方法: A ? (?1|…| ?m)A’ A’ ? (?1| … | ?n)A’|? 消除左递归(left recursion) 间接左递归: 消除方法: Pre-conditions Algorithm 四、Three Important Sets First Set(first集) for a string ? with non-terminal and terminal symbols; First(?) Follow Set(follow集) for a non-terminal symbol A; Follow(A) Predict Set(预测集) for a production; Predict(A? ?) 1 First Set (first集) Definition: First(?) = {a | ??*a?, a?VT}, if ??*? then First(?)= First(?) ? {?} For each symbol X, calculate First(X) Example 2 Follow Set (follow集) Example 3 Predict Set (predict集) Definition: Predict(A ? ?) = first(?), if ? ? first(?); Predict(A ? ?) = (first(?)- ?) ? follow(A), if ? ? first(?); Example 五、 Recursive-Descent Parsing The goal of parsing Check whether the input string belongs to the language of CFG; Two actions match(a): to check current symbol, if match, read next symbol; Derivation: select the production General Process G = (VT, VN, S, P) Predefined function: void match(a: VT) Global variable: token: VT Input string: str General Process void match(a: VT) { if token == a token = readNext(str); else error(); } Example Building Parse Tree Data