资源描述：
《西安交通大学编译原理课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、西安交通大学《编译原理》课件2009-2010第一学期本章内容自上而下分析过程概述第四章自上而下的分析给定句子从文法开始符号经最左推导构造语法树文法为无二义性的上下文无关文法无回溯的自上而下分析方法(LL(1)分析法)左递归导致推导过程死循环－消除文法左递归修改文法以避免回溯－修剪文法°FIRST(β),FOLLOW(A)YinliangZhao自上而下分析程序的构造Xi’anJiaotongUniversity递归下降分析程序2009预测分析程序24.1自上而下的分析过程概述Token串(程序)的结构G=(VT,VN,S,℘)Start→ExprErrorProcessingErr
2、orExpr→Expr+Term
3、Expr–Term
4、TermMessageTerm→Term*Int
5、Term/Int
6、IntInt∈VTStart,Expr,Term∈VNTokenParserStartSymbol:StartToDownParserStreamTree(Grammar)S→Ei∈VTE→E+T
7、E–T
8、TS,E,T∈VNT→T*i
9、T/i
10、iStartSymbol:SInputStreamOutputResult34上下文无关文法回顾上下文无关文法回顾A→Aa
11、aE→(E)
12、aE⇒(E)⇒((E))⇒((a))L(G)={an
13、n为整数，n≥1}A→aA
14、aL
15、(G)={a,(a),((a)),(((a))),…}E→(E)E⇒(E)⇒((E))⇒…A→Aα
16、ββ不以A开头A→αA
17、βL(G)={βαn
18、n为整数，n≥0}L(G)={}A→εL(G)={ε,…}E→E+a
19、aE⇒E+a⇒E+a+a⇒…A→Aa
20、εL(G)={a,a+a,a+a+a,…}L(G)={an
21、n为整数，n≥0}A→aA
22、ε56YinliangZhao（赵银亮）1西安交通大学《编译原理》课件2009-2010第一学期上下文无关文法回顾上下文无关文法回顾A→(A)A
23、ε产生任意配对的括号stmt-sequence→nonempty-stmt-sequence
24、εnon
25、empty-stmt-sequence→stmt-sequence→stmt;stmt-sequence
26、stmtstmt;nonempty-stmt-sequence
27、stmtstmt→sstmt→sL(G)={s,s;s,s;s;s,…}L(G)={ε,s,s;s,s;s;s,…}stmt-sequence→stmt;stmt-sequence
28、εstmt→sL(G)={ε,s;,s;s;,s;s;s;,…}78上下文无关文法回顾上下文无关文法回顾statement→if-stmt
29、otherstatement→if-stmt
30、otherif-stmt→if(exp)statem
31、entif-stmt→if(exp)statement
32、if(exp)statementelsestatement
33、if(exp)statementelsestatementexp→0
34、1exp→0
35、1L(G)={other,if(0)other,if(1)other,if(0)otherelseother,statement→if-stmt
36、otherif(1)otherelseother,if-stmt→if(exp)statementelse-partif(0)if(0)other,else-part→elsestatement
37、εif(0)if(1)otherelseothe
38、r,exp→0
39、1if(1)otherelseif(0)otherelseother,…}910ParseTreesandAbstractSyntaxTrees上下文无关文法回顾推导：从开始符号起构造特定句子的一个方法exp→expopexp
40、(exp)
41、numberop→+
42、-
43、*推导：不能够唯一地表示所推到出的句子的结构(number–number)*numberexp⇒expopexp⇒(exp)opexp⇒(expopexp)opexp⇒(numberopexp)opexp⇒(number-exp)opexp⇒(number-number)opexp⇒(number-numb
44、er)*exp⇒(number-number)*number1112YinliangZhao（赵银亮）2西安交通大学《编译原理》课件2009-2010第一学期ParseTreeParseTree的结点命名一个解析树（ParseTree）对应一个推导是一颗标1exp记树：(1)exp⇒expopexp内结点用非终结符标记；(2)⇒numberopexp234expopexp(3)⇒number+exp叶子结点用终结符标记；(4)⇒number+number任
