第6讲语法判别及算法--自顶向下

1、第6讲 语法判别及算法-自顶向下 自顶向下分析对应文法的最左推导，本讲有两种分析方法：l 递归下降分析l LL(1)分析1 递归下降分析递归下降分析 对每个形如 A文法规则,各设计一个子程序A( ) ,先设计上级文法的子程序，再设计下级文法的子程序，这些子程序往往递归地调用，故称递归下降分析或递归子程序法，运行这些程序就可以对源程序进行语法分析。（1）表达式文法的递归子程序 exp exp addop term | term addop + | - term term mulop factor | factor mulop *| / factor (exp) | number | id规则ex

2、p exp addop term | term有递归，不便于设计子程序，有对规则进行修改。exp = termexp = exp addop term = term addop term exp = exp addop term = term addop term addop term 修改为 exp term addop term ，中表示重复0或若干遍修改后的文法： exp term addop term addop + | - term factor mulop factor mulop *| / factor (exp) | number | id源程序经扫描后的记号存入一个数组中如源

3、程序 3+（5-2）*2 则记号序列为：NUM PLUS LPAREN NUM MINUS NUM RPAREN TIMES NUM代码： token=gettoken(); 先获得一个记号 设计规则exp term addop term的子程序 void exp() term(); while(token=PLUS) | (token=MINUS) token=gettoken(); term(); 设计规则term factor mulop factor的子程序 void term() factor(); while(token=TIMES) | (token=OVER) token=ge

4、ttoken(); factor(); 设计规则factor (exp)|number|id的子程序 void factor() if (token=LPAREN) token=gettoken(); exp(); if(token=RPAREN) token=gettoken(); else error; else if(token=NUM) | (token=ID) token=gettoken(); else error; 对3+2的分析 NUM PLUS NUMtokenE1 NUM T1NUM F1NUM F7NUM F8PLUS F10PLUS T2PLUS T5PLUSE2PLU

5、SE3NUME4NUM T1NUM F1NUM F7NUM F8下一个记号 F10 T2 T5E5（2）赋值语句的递归子程序 规则： assign_stmtidentifier := exp 子程序：void assign_stmt() if (token=ID) token=gettoken(); else error; exit(1); if(token=ASSIGN) token=gettoken(); else error; exit(1); exp(); (3) 多个语句的递归子程序 规则：stmt_sequencestmt_sequence;statement | statemen

6、t 改为：stmt_sequence statement ; statement statement assign_stmt | if_stmt 子程序：void stmt_sequence() statement(); while (token=SEMI) token=gettoken(); statement(); 规则：statement assign_stmt | if_stmt子程序：void statement() if (token=ID) assign_stmt(); else if (token=IF) if_stmt(); else error; exit(1) 条件语句文

7、法： if_stmt if exp then stmt_sequence else stmt_sequence end 子程序： void if_stmt() if (token=IF) exp(); if(token=THEN) token=gettoken(); stmt_sequence(); if(token=ELSE) token=gettoken(); stmt_sequence(); if(token=END) token=gettoken(); else error;exit(1); else error; (4) TINY语言文法及分析 语法树：P100 数据结构：P383T

8、ypedef enum StmtK,ExpK NodeKind;Typedef enum IfK,RepeatK,AssignK,ReadK,WriteKStmtKind;Typedef enum OpK,ConstK,IdKExpKind;Typedef struct treenodestruct treenode * child3; 3个子结点Struct treenode *sibling; 同属NodeKind nodekind; 句子或表达式Union StmtKind stmt;ExpKind exp;kind; 句子或表达式类型 Union TokenType op; int v

9、al; char *name;attr; 属性TreeNode;创建树结点 如：TreeNode *t=(TreeNode *)malloc(sizeof(TreeNode);t-child0=null;t-child1=null;t-child2=null;t-sibling 指向ift-nodekind=StmtK;t-kind.stmt=ReadK;=“x”;read(x)P100 图3-6 中的结点类型句子类型：如操作符类型：如read（x）op(child0 指向op(child1= 指向assign结点 t-child2=null;t-sibling=null

10、; t-nodekind=StmtK;t-kind.stmt=IfK;t-attr.* 为空if结点设t为指向此结点的指针,有两个子树，无同属t-child0 指向op(child1= 指向 结点 t-child2=null;t-sibling=null; t-nodekind=ExpK;t-kind.stmt=OpK;t-attr.op=LT;结点t-child0=null; t-child1=null; t-child2=null;t-sibling=null; t-nodekind=ExpK;t-kind.stmt=ConstK;t-attr.val=0;op(child0=null;

11、t-child1=null; t-child2=null;t-sibling=null; t-nodekind=ExpK;t-kind.stmt=IdK;=“x”;id(x)能返回语法树的递归子程序表达式： 如3+5-6 Treenode * exp() Treenode * t=term(); while (token=PLUS) | (token=MINUS) Treenode *p=newexpnode(OpK); p-child0=t; p-attr.op=token; t=p; token=gettoken(); t-child1=term(); return

12、t Treenode * term() Treenode *t=factor(); while(token=TIMES) | (token=OVER) Treenode * p=newexpnode(OpK) p-child0=t; p-attr.op=token; t=p; token=gettoken(); p-child1=factor(); return t Treenode * factor() Treenode *t=NULL; switch(token) case NUM: t=newexpnode(ConstK); t-attr.val=str_val(tokenstring

13、); token=gettoken(); break; case ID: t=newexpnode(IdK); =tokenstring; token=gettoken(); break; case LPAREN: t=exp(); token=gettoken(); break; default: error; break; return t;赋值语句： assign_stmt id :=expTreenode * assign_stmt() Treenode * t=newstmtNode(AssignK); if (token=ID) =tok

14、enstring; token=gettoken(); if (token=ASSIGN) token=gettoken(); else error; else error; t-child0=exp(); return t; 2 LL(1)分析L: 自左向右输入L: 最左推导1: 先前看1个符号（1）基本方法例文法S(S)S|要分析串()是否符合文法分析过程：分析栈输入动作$ S( ) $规则 S(S)S右部入栈 （逆序）$ S ) S ( ) $匹配，栈顶出栈，输入头后移$ S ) S ) $规则 S 右部入栈 （逆序）$ S ) ) $匹配，栈顶出栈，输入头后移$ S $规则 S 右部入

15、栈 （逆序）$ $接受注意：开始时栈中只有$符号和文法开始符号 替换时，采用的规则唯一，逆序入栈 只有两种动作： 替换和匹配相当于S=(S)S=()S=() 最左推导（2）LL(1)分析算法关键是构造LL(1)分析表 终符非终符ab$A规则规则规则规则B规则规则规则规则规则规则规则规则为了使表格中的规则唯一，需要 修改文法 求First集和Follow集 修改文法消除左递归，提取左因子形如AA| 改为 A A A A |例如： exp exp addop term | term 改为：exp term exp exp addop term exp | 形如A| 改为AA A | First集（

16、首符号集） 设是由非终结符号和终结符号组成的任意串则 First()=例如：EE+T|T TT*F|F F(E)|i求First(E)E=T=F=(E) ( 是首符号E=T=F=i i 是首符号故 First(E)=( , i求First(T*F)T*F=F*F=(E)*F ( 是首符号T*F=F*F=i*F i 是首符号故 First(T*F)=( , i求First(i*i) First(i*i)=i .,|*TVaaa Follow集（后随集）设文法GS，对一个非终结符U 则Follow(U)=例如： EE+T|T TT*F|F F(E)|I求Follow(E)E=E+T + 是后随符号

17、E=E+T=E+F=E+(E) ) 是后随符号故Follow(E)=+ ,),$求Follow(T)E=T=T*F *是后随符号E=E+T=T+T +是后随符号E=E+T=T+T=F+T=(E)+T=(T)+T )是后随符号故Follow(T)=*,+,),$.,.|*TVaaUSa 构造LL(1)分析表对每个规则 A 当时，求First() 当=时，求Follow(A)例如：文法S(S)S|,求LL(1)分析表对于S(S)S First( (S)S )= ( 对于S Follow(S)= ),$ VTVN() $SS(S)SSS LL(1)分析算法push $push 开始符号while 栈

18、顶$ do if 栈顶是终结符号 and 等于输入符号 then 匹配，pop栈顶符号，输入下一个符号 else if 栈顶是非终符 且 分析表相应格有规则 then pop栈顶非终符，规则右部逆序入栈 else 错误 if 栈顶为$ 且 输入符号为$ then 接受，退出 else 错误例如：用LL(1)方法分析 3+（5-2）*x 是否符合以下文法 GE：EE + T | E-T | T T T * F | T / F | F F(E) | num | id解： 修改文法： 提左因子 EE E1 |T E1 +T | -T 消左递归 ETE EE1E | 即 ET E E +T E | -

19、T E | 提左因子 TT T1 |F T1 *F | /F 消左递归 TF T TT1 T | 即 TF T T * F T | / F T | 修改后的文法GE: ET E E +T E | -T E | TF T T * F T | / F T | F(E) | num | id求分析表 ET E E +T E | -T E | TF T T * F T | / F T | F(E) | num | id规则First()或Follow()ET E( num idE +T E+FidIdE $ )E -T E-TF T( num idT * F T*T / F T/T $ + - ) F

20、(E)(F numnum VTVN+-*/()num id$EE TTF(E)LL(1)分析表T ET ET E+T E-T EFTFTFT/FT*FTnumid分析过程分析栈输入动作替换T $ E + ( 5 2 ) * x $替换E +T E$ E T + + ( 5 2 ) * x $匹配$ E T ( 5 2 ) * x $替换TF T$ E T F ( 5 2 ) * x $替换F(E)$ E T ) E ( ( 5 2 ) * x $匹配$ E T ) E 5 2 ) * x $替换ET E$ E T ) E T 5 2 ) * x $替换TF T$ E T ) E T F 5 2 ) * x $替换F num$ E T ) E Tnum 5 2 ) * x $匹配3 + ( 5 2 ) *