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

-1-,编译程序的面向对象设计与实现,Dr. Zheng Xiaojuan Associate Professor Software College of Northeast Normal University April. 2009,-2-,阶段三：语法分析器开发,-3-,项目需求,读入词法分析的输出结果token序列； 对token序列进行语法分析生成语法正确的与源程序结构相对应的语法分析树； 能够指出语法错误所在位置。,-4-,一、编译原理内容,-5-,语法分析程序的功能,-6-,所需编译知识关联图,Develop a Parser,Syntax definition,basing on,Context Free Grammar,using,implement,Top-down,Bottom-up,-7-,Top-down parsing,Syntax definition,basing on,CFG,using,check precondition,Predict(A),first(),follow(A),Yes,Recursive-descent,LL(1),Implement,所需编译知识关联图,-8-,一、Context Free Grammar (CFG),定义为四元组(VT,VN,S,P) VT是有限的终极符集合 VN是有限的非终极符集合 S是开始符，S VN P是产生式的集合，且具有下面的形式： AX1X2Xn 其中AVN，Xi (VTVN) ，右部可空。,-9-,二、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集合互不相交) 这个条件保证:针对当前的符号和当前的非终极符,可以选择唯一的产生式来进行推导;,-10-,三、 Grammar Transformation,消除公共前缀(left factoring) 公共前缀 A 1 | | n| 1| m 提取公因子 A A| 1| m A 1 | | n,-11-,消除左递归(left recursion) 直接左递归:A A(1 | | n)| 1| m 消除方法: A (1| m)A A (1| | n)A|,-12-,消除左递归(left recursion) 间接左递归: 消除方法: Pre-conditions Algorithm,S A b A S a | b,1:S 2:A A Aba | b A bA A baA | ,-13-,四、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 ),-14-,1 First Set (first集),Definition: First() = a | *a, aVT, if * then First()= First() ,How to calculate First()? = , First() = = a, aVT, First() = a = A, AVN, First() = First(A) = X1 X2 Xi-1 Xi Xn,-15-,S = A | A * , AVN,For each terminal symbol a, First(a) = a,For each symbol X, calculate First(X),VN=A1, , An , calculate First(Ai) 初始化, First(Ai) =; for i =1 to n 对于Ai的每个产生式, - if Ai , First(Ai) = First(Ai) ; - if Ai Y1 . Ym, Y1 ,. ,YmS, First(Ai) = First(Ai) First(Y1) First(Ym) - if Ai Y1 . Ym, Y1 ,. ,Yj-1S, Yj S First(Ai) = First(Ai) First(Y1) First(Yj-1)- First(Yj) (3) Repeat (2) until 每个First(Ai)没有变化(收敛).,-16-,Example,P: (1) E TE (2) E + TE (3) E (4) T FT (5) T * F T (6) T (7) F (E) (8) F i (9) F n,S = E, T,-17-,2 Follow Set (follow集),How to calculate Follow(A), AVN (1)初始化, AVN, Follow(A) = (2)Follow(S) = # (3)对于每个产生式A If there is no non-terminal symbol in , skip; If = B, BVN, Follow(B) = Follow(B) (First()-) If First(), Follow(B) = Follow(B) Follow(A) If = B, Follow(B) = Follow(B) Follow(A) (4) Repeat (3) until all follow sets do not change any more;,-18-,Example,P: (1) E TE (2) E + TE (3) E (4) T FT (5) T * F T (6) T (7) F (E) (8) F i (9) F n,-19-,3 Predict Set (predict集),Definition: Predict(A ) = first(), if first(); Predict(A ) = (first()- ) follow(A), if first();,-20-,Example,P: (1) E TE (2) E + TE (3) E (4) T FT (5) T * F T (6) T (7) F (E) (8) F i (9) F n,first集,follow集,First(TE)=i, n,( ,First(+TE)=+,Follow(E)=#, ),First(FT)=i,n,( ,First(*FT)=*,Follow(T)= ),+, # ,First(E)= ( ,First(i)=i,First(n)=n,-21-,五、 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,-22-,General Process,G = (VT, VN, S, P) Predefined function: void match(a: VT) Global variable: token: VT Input string: str,For each A VN, A 1| n A( ) case token of Predict(A 1): SubR(1) ; break; Predict(A n): SubR(n) ; break; other: error; ,-23-,General Process,void match(a: VT) if token = a token = readNext(str); else error(); ,SubR(): = X1 X2 Xn If Xi VT, match(Xi) If Xi VN, Xi();,SubR(): = ,-24-,Example,P: (1) Z aBd a (2) B d d (3) B c c (4) B bB b,Z ( ) if token = a match(a); B( ); match(d); else error( ); ,B ( ) case token of d: match(d);break; c: match(c); break; b: match(b); B( ); break; other: error( ); ,a b c d,main( ) read(token); Z( ),-25-,Building Parse Tree,Data structure ParseTree Operations ParseTree BuildRoot(symbol: VT VN); ParseTree BuildOneNode(symbol: VT VN) AddOneSon(father:*ParseTree, son:*ParseTree ) SetNum(Node:*ParseTree, n:int),符号 儿子个数 儿子指针,-26-,Example,Z ( ) if token = a match(a); B( ); match(d); else error(); return nil; ,*ParseTree,T = BuildRoot(Z);,AddOneSon(T, A);,A = BuildOneSon(a);,AddOneSon(T, BB);,BB=,AddOneSon(T, D);,D = BuildOneSon(d);,return T;,SetNum(T, 3);,-27-,六、 LL(1) Parsing Method,LL(1) Parsing LL(1) parsing table to record predict sets for each production; (LL(1)分析表) A general engine(一个通用的驱动程序),-28-,LL(1) Parsing Table (LL(1)分析表),How to build LL(1) Parsing Table for a LL(1) Grammar? For a LL(1) Grammar G = (VT, VN, S, P) VT = a1, , an VN = A1, , An LL(Ai, ai) = Ai , if aipredict(Ai ) LL(Ai, ai) = error, if ai not belong to the predict set of any production of Ai,-29-,LL(1) Parsing Mechanism,Stack,Input,#,a,驱动程序: 栈为空情形的处理 X VT情形的处理 X VN情形的处理,X,LL1分析表,-30-,LL(1) Parsing Engine,1 初始化： Stack := ；Push(S)； 2 读下一个输入符： Read(a)； 3 若当前格局是( , # )，则成功结束；否则转下； 4 设当前格局为（. X, a.)，则 若X VT & X= a ，则 Pop(1)； Read(a)；goto 3 若X VT & X a ，则 Error； 若X VN ，则： if LL(X, a)=XY1 Y2 Yn then Pop(1)；Push(Yn ,.,Y1)；goto3 else Error,-31-,Building Parse Tree During LL(1),1 初始化： Stack := ； root=BuildOneNode(S); Push(S, root)； 2 读下一个输入符： Read(a)； 3 若当前格局是( , # )，则成功结束；否则转下； 4 设当前格局为（. X, a.)，则 若X VT goto3 else Error,-32-,二、语法分析程序的实现,-33-,部分SNL语言的上下文无关文法,总程序： Program := ProgramHead DeclarePart ProgramBody . 程序头： 2) ProgramHead := PROGRAM ProgramName 3) ProgramName := ID 程序声明： DeclarePart := TypeDecpart VarDecpart ProcDecpart 类型声明： TypeDecpart := | TypeDec TypeDec := TYPE TypeDecList TypeDecList := TypeId = TypeDef ; TypeDecMore TypeDecMore := | TypeDecList TypeId := ID,-34-,语法树节点的数据结构,原则：语法分析器的输出将作为语义分析的输入，因此语法分析树中不仅应该包含源程序的结构信息，还应该为语义分析提供必要的信息。在进行语法分析时，语法分析程序将根据源语言的文法产生式，为相应的非终极符创建一个语法树节点，并为之赋值，得到的是与程序结构相似的改进的语法树。除此之外，只要能够清晰表达出源程序的语法结构即可。语法树节点的数据结构 可小组自行定义。,-35-,语法树节点的数据结构,-36-,ProK PheadK p TypeK DecK IntegerK t1 VarK DecK IntegerK v1 v2 ProcDecK q DecK value param: IntegerK i VarK DecK IntegerK a StmLk StmtK Assign ExpK a IdV ExpK i IdV StmtK Write ExpK a IdV StmL