西安交通大学《编译原理》课件2009-2010第一学期本章内容自上而下分析过程概述第四章自上而下的分析给定句子从文法开始符号经最左推导构造语法树文法为无二义性的上下文无关文法无回溯的自上而下分析方法(LL(1)分析法)左递归导致推导过程死循环－消除文法左递归修改文法以避免回溯－修剪文法ƒFIRST(β),FOLLOW(A)YinliangZhao自上而下分析程序的构造Xi’anJiaotongUniversity递归下降分析程序2009预测分析程序24.1自上而下的分析过程概述Token串(程序)的结构G=(VT,VN,S,℘)→ErrorProcessingStartExprErrorExpr→Expr+Term|Expr–Term|TermMessageTerm→Term*Int|Term/Int|IntInt∈VTStart,Expr,Term∈VNTokenParserStartSymbol:StartToDownParserStreamTree(Grammar)S→Ei∈VTE→E+T|E–T|TS,E,T∈VN→InputStreamOutputResultTT*i|T/i|iStartSymbol:S34上下文无关文法回顾上下文无关文法回顾A→Aa|aE→(E)|aE⇒(E)⇒((E))⇒((a))L(G)={an|n为整数，n≥1}A→aA|aL(G)={a,(a),((a)),(((a))),…}E→(E)E⇒(E)⇒((E))⇒…A→Aα|ββ不以A开头A→αA|βL(G)={βαn|n为整数，n≥0}L(G)={}A→εL(G)={ε,…}E→E+a|aE⇒E+a⇒E+a+a⇒…A→Aa|εL(G)={a,a+a,a+a+a,…}L(G)={an|n为整数，n≥0}A→aA|ε56YinliangZhao（赵银亮）1西安交通大学《编译原理》课件2009-2010第一学期上下文无关文法回顾上下文无关文法回顾A→(A)A|ε产生任意配对的括号stmt-sequence→nonempty-stmt-sequence|εnonempty-stmt-sequence→stmt-sequence→stmt;stmt-sequence|stmtstmt;nonempty-stmt-sequence|stmtstmt→sstmt→sL(G)={s,s;s,s;s;s,…}L(G)={ε,s,s;s,s;s;s,…}stmt-sequence→stmt;stmt-sequence|εstmt→sL(G)={ε,s;,s;s;,s;s;s;,…}78上下文无关文法回顾上下文无关文法回顾statement→if-stmt|otherstatement→if-stmt|otherif-stmt→if(exp)statementif-stmt→if(exp)statement|if(exp)statementelsestatement|if(exp)statementelsestatementexp→0|1exp→0|1L(G)={other,if(0)other,if(1)other,if(0)otherelseother,statement→if-stmt|otherif(1)otherelseother,if-stmt→if(exp)statementelse-partif(0)if(0)other,else-part→elsestatement|εif(0)if(1)otherelseother,exp→0|1if(1)otherelseif(0)otherelseother,…}910ParseTreesandAbstractSyntaxTrees上下文无关文法回顾推导：从开始符号起构造特定句子的一个方法exp→expopexp|(exp)|numberop→+|-|*推导：不能够唯一地表示所推到出的句子的结构(number–number)*numberexp⇒expopexp⇒(exp)opexp⇒(expopexp)opexp⇒(numberopexp)opexp⇒(number-exp)opexp⇒(number-number)opexp⇒(number-number)*exp⇒(number-number)*number1112YinliangZhao（赵银亮）2西安交通大学《编译原理》课件2009-2010第一学期ParseTreeParseTree的结点命名一个解析