第二章 簡(jiǎn)單一遍編譯器

1、2022-2-141第二章簡(jiǎn)單的一遍翻譯器第二章簡(jiǎn)單的一遍翻譯器A Simple One Pass CompilerA Simple One Pass Compiler2022-2-14編譯原理2本章主要內(nèi)容本章主要內(nèi)容q開(kāi)發(fā)一個(gè)把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的翻譯程序，展示基本的編譯技術(shù)q主要描述編譯器的前端前端詞法分析、語(yǔ)法分析和語(yǔ)義分析q通過(guò)本章對(duì)編譯器構(gòu)造的過(guò)程有所了解9*5+x95*x+2022-2-14編譯原理32.1 概述概述q程序設(shè)計(jì)語(yǔ)言由語(yǔ)法(syntax)和語(yǔ)義(semantics)兩個(gè)方面定義。語(yǔ)法描述程序的正確形式語(yǔ)義則描述程序的含義q語(yǔ)義的描述比語(yǔ)法的描述難得多描述形式

2、？2022-2-14編譯原理4如何描述語(yǔ)法如何描述語(yǔ)法qBakus-Naur范式(BNF) qSyntax Graphq上下文無(wú)關(guān)文法 (CFG， Context Free Grammar ) 2022-2-14編譯原理5Backus-Naur范式范式(BNF)2022-2-14編譯原理6Examples of BNF2022-2-14編譯原理7Syntax Graph2022-2-14編譯原理82.2 語(yǔ)法定義語(yǔ)法定義q語(yǔ)法描述程序設(shè)計(jì)語(yǔ)言的層次結(jié)構(gòu)，如C語(yǔ)言的條件語(yǔ)句形如： if (expression) statement else statement或者if (expression)

3、statementq這一規(guī)則表示為：if_stmt if (expr) stmt else stmt if_stmt if (expr) stmt q描述規(guī)則稱(chēng)為產(chǎn)生式產(chǎn)生式 (production)q用上下文無(wú)關(guān)文法用上下文無(wú)關(guān)文法 (Context-free Grammar, CFG)來(lái)形式化這種描述。2022-2-14編譯原理92.2.1 上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法CFG是一個(gè)四元組 (Vt, Vn, S, P)，其中：Vt 是一個(gè)非空有窮集合，稱(chēng)作終結(jié)符號(hào)集合Terminal SymbolsVn 是一個(gè)非空有窮集合，稱(chēng)作非終結(jié)符號(hào)集合Non-terminals ，且Vt

4、Vn = 。S Vn ，稱(chēng)作開(kāi)始符號(hào)Start Symbol 。P是一個(gè)非空有窮集合，稱(chēng)為產(chǎn)生式集合Production Rules ，每條產(chǎn)生式形為A，其中AVn，(VtVn)*。2022-2-14編譯原理10例例2.1簡(jiǎn)單的算術(shù)表達(dá)式簡(jiǎn)單的算術(shù)表達(dá)式list list + digitlist list - digitlist digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9終結(jié)符號(hào)：+ - 0 1 2 3 4 5 6 7 8 9非終結(jié)符號(hào)：list digit開(kāi)始符號(hào)：list “”“|” 表示“或者”2022-2-14編譯原理11例例2.1

5、簡(jiǎn)單的算術(shù)表達(dá)式簡(jiǎn)單的算術(shù)表達(dá)式list list + digit | list digit | digitdigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9上述文法定義的是由加號(hào)和減號(hào)分隔的數(shù)字序列構(gòu)成的列表。2022-2-14編譯原理122.2.2 推導(dǎo)（推導(dǎo)（derive）list list + digit list - digit + digit digit - digit + digit 9 - digit + digit 9 - 5 + digit 9 - 5 + 2 P1 : list list + digitP2 : list list -

6、digitP3 : list digitP4 : digit 9P4 : digit 5P4 : digit 2例例2.2 數(shù)字序列數(shù)字序列9 - 5 + 2的推導(dǎo)的推導(dǎo)2022-2-14編譯原理13例例2.3 函數(shù)調(diào)用中的參數(shù)列表函數(shù)調(diào)用中的參數(shù)列表What is this grammar for ?What does “” represent ?What kind of production rule is this ?How to define “param”?call id ( opt_params )opt_params params | params params, param |

7、 param2022-2-14編譯原理142.2.3 分析樹(shù)分析樹(shù)(Parse Tree)q分析樹(shù)描述如何從文法的開(kāi)始符號(hào)推導(dǎo)出它的語(yǔ)言中的一個(gè)語(yǔ)句。q如果非終結(jié)符A有產(chǎn)生式 A XYZ，則A的一棵分析樹(shù)為：AXYZ2022-2-14編譯原理15Parse Treeq分析樹(shù)具有如下性質(zhì)：Root is labeled with the Start Symbol Leaf node is a token or Interior node (Non-leaf) is a Non-Terminal If A x1x2xn, Then A is an interior; x1x2xn are chil

8、dren of A and may be non-terminals or tokensq一個(gè)文法生成的語(yǔ)言語(yǔ)言是它的某個(gè)分析樹(shù)生成的串的集合。為給定的符號(hào)串找到一棵分析樹(shù)的過(guò)程稱(chēng)為串的語(yǔ)法分析語(yǔ)法分析(parsing)(parsing)。2022-2-14編譯原理16listdigitdigitlistdigitlist952-+list list + digit list - digit + digit digit - digit + digit 9 - digit + digit 9 - 5 + digit 9 - 5 + 2 推導(dǎo)過(guò)程可以用分析樹(shù)（推導(dǎo)過(guò)程可以用分析樹(shù)（ Parse T

9、ree ）表示）表示2022-2-14編譯原理172.2.4 二義性二義性 AmbiguityWhy is this a Problem ?Grammar:string string + string | string string | 0 | 1 | | 9對(duì)某個(gè)文法，如一個(gè)句子有兩棵以上的分析樹(shù)，稱(chēng)為二義（歧義）文法。stringstringstringstringstring+2-59stringstringstringstringstring-+2592022-2-14編譯原理18如何判斷文法具有二義性？q如果文法的某個(gè)句子存在兩棵分析樹(shù)， 則該句子是二義性的 。q如果一文法包含二義性

10、的句子，則這個(gè)文法是二義性的。| | SaSbSbSaS 2022-2-14編譯原理19| | SaSbSbSaS 句子abab有兩個(gè)不同的最左推導(dǎo)，該句子是二義性的 ，所以此文法是二義性的。ababababSSbSaabSaSbSabSbSaSababababSSbSaabSabSbSaSlmlmlmlmlmlmlmlmlmlm 2022-2-14編譯原理202.2.5 Associativity of Operatorsq可以用括號(hào)來(lái)表明計(jì)算順序，如9-5+2 = (9-5)+2q如果對(duì)某個(gè)運(yùn)算符op，x1,x2,x3為運(yùn)算對(duì)象，且x1 op x2 op x3 表示 (x1 op x2)

11、op x3，則稱(chēng)op是左結(jié)合的；如果x1 op x2 op x3 表示 x1 op (x2 op x3)，則稱(chēng)op是右結(jié)合的。2022-2-14編譯原理21right letter = right | letterletter a | b | c | | zlistdigitdigitlistdigitlist952-+list list + digit | list - digit | digitdigit 0 | 1 | | 9rightletterletterrightletterrightcba=Left vs. Right2022-2-14編譯原理22Questionq如何增加*、/

12、運(yùn)算符？list list + digit | list - digit | digitdigit 0 | 1 | | 9list list + digit | list - digit | list * digit | list / digit | digitdigit 0 | 1 | | 92022-2-14編譯原理232.2.6 Operator PrecedenceqWhat does 9 + 5 * 2 mean? listdigitdigitlistdigitlist952+*listdigitdigitlistdigitlist952-+2022-2-14編譯原理242.2.6

13、Operator PrecedenceqWhat does 9 + 5 * 2 mean? (9 + 2) * 5 9 + (5 * 2)q不同的運(yùn)算符號(hào)有不同的優(yōu)先級(jí)，如9+5*2 表示 9+(5*2)，所以*的優(yōu)先級(jí)比+高。Typically( )* /+ -is precedence order 2022-2-14編譯原理25n通過(guò)適當(dāng)改寫(xiě)文法規(guī)則，可以描述不同的結(jié)合律和優(yōu)先級(jí)：n基本因子：factor digit | ( expr ) n項(xiàng)由因子進(jìn)行乘除運(yùn)算構(gòu)成：term term * factor | term / factor |factor nexpr由項(xiàng)進(jìn)行加減運(yùn)算構(gòu)成：exp

14、r expr + term | expr term | term2022-2-14編譯原理26表達(dá)式文法：表達(dá)式文法：expr expr + term | expr term | termterm term * factor | term / factor |factor factor digit | ( expr ) 2022-2-14編譯原理27練習(xí)：構(gòu)造練習(xí)：構(gòu)造9+5*2的分析樹(shù)的分析樹(shù)2022-2-14編譯原理28Java語(yǔ)句的語(yǔ)法語(yǔ)句的語(yǔ)法stmt id = expr ;| if (expr )then stmt| if (expr ) stmt else stmt| while

15、(expr) stmt| do stmt while (expr);| stmts stmts stmts stmt| 注意注意“；”的設(shè)置的設(shè)置；出現(xiàn)在所有不以stmt結(jié)尾的產(chǎn)生式末尾，避免多余分號(hào)2022-2-14編譯原理292.3 語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯Syntax-Directed Translationq語(yǔ)法是掌握語(yǔ)義的鑰匙q語(yǔ)法制導(dǎo)定義每個(gè)文法符號(hào)有屬性的集合每個(gè)產(chǎn)生式有語(yǔ)義計(jì)算規(guī)則的集合q語(yǔ)法制導(dǎo)翻譯向表達(dá)式附加規(guī)則或代碼片斷翻譯模式：描述翻譯過(guò)程的表示法2022-2-14編譯原理30語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯Syntax-Directed Translationq一個(gè)例子：將中

16、綴表達(dá)式翻譯成后綴表達(dá)式expr expr1 + term 翻譯expr1；翻譯term；處理+；2022-2-14編譯原理312.3.1 后綴表示后綴表示Postfix Notationq歸納定義：If E is a variable or constant , then Postfix(E) = EIf E is E1 op E2, then Postfix(E) = Postfix(E1 op E2) = Postfix(E1) Postfix(E2) opIf E is (E1) then Postfix(E) = Postfix(E1) Examples:( 9 5 ) + 2 9

17、5 2 +9 ( 5 + 2 ) 9 5 2 + -2022-2-14編譯原理322.3.2 語(yǔ)法制導(dǎo)定義語(yǔ)法制導(dǎo)定義 Syntax-Directed Definitionq每個(gè)文法符號(hào)有屬性的集合(a Set of Attributes)q每個(gè)產(chǎn)生式有語(yǔ)義計(jì)算規(guī)則的集合(a Set of Semantic Rules)2022-2-14編譯原理332.3.3 中綴到后綴翻譯的語(yǔ)法制導(dǎo)定中綴到后綴翻譯的語(yǔ)法制導(dǎo)定義義 q例2.6為每個(gè)非終結(jié)符定義屬性“t” ，表示其對(duì)應(yīng)的表達(dá)式的后綴表示，每條產(chǎn)生式帶有語(yǔ)義規(guī)則Production Semantic Ruleexpr expr1 + term

18、expr.t := expr1.t | term.t | +expr expr1 term expr.t := expr1.t | term.t | -expr term expr.t := term.tterm 0 term.t := 0term 1 term.t := 1. .term 9 term.t := 92022-2-14編譯原理34注釋分析樹(shù)注釋分析樹(shù) q綜合屬性：屬性值是由子節(jié)點(diǎn)的屬性確定的q通過(guò)遍歷分析樹(shù)可以求得結(jié)果q計(jì)算順序：深度優(yōu)先遍歷是一種常用的方法expr.t =95-expr.t =9expr.t =95-2+term.t =5term.t =2term.t =92

19、+5-92022-2-14編譯原理352.3.4 語(yǔ)法樹(shù)的遍歷語(yǔ)法樹(shù)的遍歷2022-2-14編譯原理362.3.5 翻譯模式翻譯模式q也可以把上下文無(wú)關(guān)文法擴(kuò)展成翻譯模式（也叫翻譯文法），不生成分析樹(shù)來(lái)進(jìn)行屬性計(jì)算。q特點(diǎn)是在產(chǎn)生式的右部插入語(yǔ)義動(dòng)作rest + term print(+) rest1 q翻譯模式類(lèi)似于語(yǔ)法制導(dǎo)定義，只是語(yǔ)義規(guī)則的計(jì)算順序是顯式給出的。2022-2-14編譯原理37翻譯模式翻譯模式expr expr1 + term print(+) expr1 - term print(-) termterm 0 print(0)term 1 print(1)term 9 pr

20、int(9)2022-2-14編譯原理38termtermtermexprexprexpr952-+print(-)print(9)print(5)print(2)print(+)q可以把語(yǔ)義動(dòng)作看作是特殊的終結(jié)符，不匹配輸入，語(yǔ)法分析的時(shí)候直接執(zhí)行2022-2-14編譯原理392.4語(yǔ)法分析語(yǔ)法分析(Parsing)q兩類(lèi)方法（指構(gòu)造分析樹(shù)結(jié)點(diǎn)的順序）自頂向下(top-down)自底向上(bottom-up)q自頂向下方法從開(kāi)始符號(hào)開(kāi)始構(gòu)造分析樹(shù)對(duì)終結(jié)符，看是否與輸入匹配（否則回溯）對(duì)非終結(jié)符，選擇一個(gè)產(chǎn)生式構(gòu)造子樹(shù)2022-2-14編譯原理40stmt expr; | if (expr)

21、stmt | for (optexpr; optexpr; optexpr) stmt| otheroptexpr | expr2.4.1 自頂向下語(yǔ)法分析自頂向下語(yǔ)法分析假定有輸入：假定有輸入： for ( ; expr; expr) other2022-2-14編譯原理41stmtfor ( ; expr ; expr ) other2022-2-14編譯原理42stmt)optexpr ; optexpr; optexpr(forstmtfor ( ; expr ; expr ) other2022-2-14編譯原理43stmt)optexpr ; optexpr; optexpr(fo

22、rstmtfor ( ; expr ; expr ) other2022-2-14編譯原理44stmt)optexpr ; optexpr; optexpr(forstmtfor ( ; expr ; expr ) other2022-2-14編譯原理45stmt)optexpr ; optexpr; optexpr(forstmtfor ( ; expr ; expr ) other2022-2-14編譯原理46stmt)optexpr ; optexpr; optexpr(forstmtfor ( ; expr ; expr ) otherexprexprother2022-2-14編譯原

23、理472022-2-14編譯原理482.4.2 預(yù)測(cè)分析法預(yù)測(cè)分析法 Recursive Descent and Predictive Parsingq上述分析過(guò)程可以用遞歸下降法來(lái)實(shí)現(xiàn)：每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)遞歸過(guò)程q如果我們根據(jù)輸入能確定地選取要擴(kuò)展的產(chǎn)生式（或要調(diào)用的子過(guò)程），則稱(chēng)為預(yù)測(cè)分析法。q對(duì)應(yīng)產(chǎn)生式stmt for (optexpr; optexpr; optexpr) stmt執(zhí)行調(diào)用序列：match(for); match();optexpr(); match(;); optexpr(); match(;); optexpr(); match(); stmt();2022-2-

24、14編譯原理49void match ( terminal t)if (lookahead = t ) lookahead = nextTerminal; else report(“error”)2022-2-14編譯原理50void stmt() switch (lookahead ) case expr: match(expr); match(;); break;case if: match(if); match(); match(expr); match(); stmt();break;case for: match(for); match();optexpr(); match(;);

25、optexpr(); match(;); optexpr(); match(); stmt();break;case other: match(other); break;default: report(“error”)2022-2-14編譯原理51Problem with Top Down Parsingq如果A | ，預(yù)測(cè)分析法要求 和 的開(kāi)始符號(hào)集合(First集合)能夠區(qū)分，即不相交First() First()=。q如果文法中存在左遞歸，采用遞歸下降法會(huì)導(dǎo)致無(wú)窮循環(huán)。為此，需要改寫(xiě)產(chǎn)生式來(lái)消除左遞歸。qexpr expr + term2022-2-14編譯原理52q改寫(xiě)產(chǎn)生式來(lái)消除左

26、遞歸：A A | q可以改成A B B B | q兩者產(chǎn)生的語(yǔ)言都是*2022-2-14編譯原理532.5 簡(jiǎn)單表達(dá)式的翻譯器簡(jiǎn)單表達(dá)式的翻譯器expr expr + term print(+) expr - term print(-) termterm 0 print(0)term 1 print(1)term 9 print(9)中綴到后綴的初始翻譯模式中綴到后綴的初始翻譯模式2022-2-14編譯原理54q初始的文法是左遞歸的，需要變換。變換時(shí)，把語(yǔ)義動(dòng)作也看成是文法符號(hào)expr expr + term printf(+)expr expr term printf(-)expr term

27、q變換成expr term restrest + term printf(+) rest | - term printf(-) rest|2022-2-14編譯原理55expr expr + term printf(+)expr expr term printf(-)expr term變換成expr term restrest + term printf(+) rest | - term printf(-) rest|A A | A | 轉(zhuǎn)換成A R R R | R | AAAA2022-2-14編譯原理56修改后的翻譯模式修改后的翻譯模式expr term restrest + term p

28、rintf(+) rest | - term printf(-) rest|term 0 print(0)term 1 print(1)term 9 print(9)2022-2-14編譯原理57從從9-5+2到到95-2+的翻譯的翻譯print(2)exprtermterm print(-)term print(+) restprint(5)print(9)restrest25-9+ 2022-2-14編譯原理58void expr( ) term(); rest();void rest( ) if (lookahead = +) match(+); term( ); putchar(+);

29、 rest( ); else if (lookahead = -) match(-); term( ); putchar(-); rest( ); else ;void term( )if (isdigit(lookahead) putchar(lookahead); match(lookahead); else error( );非終結(jié)符非終結(jié)符expr、rest和和term的函數(shù)的函數(shù)2022-2-14編譯原理592022-2-14編譯原理60運(yùn)行結(jié)果：運(yùn)行結(jié)果：?jiǎn)栴}： 如何改進(jìn)程序，使之能夠處理數(shù)值的計(jì)算？如20+15 如何改進(jìn)程序，使之能夠處理其他運(yùn)算？如20*152022-2-14編

30、譯原理612.6 詞法分析詞法分析q為上面的翻譯器增加一個(gè)詞法分析器。去除blank（空格、tab、換行）、注釋識(shí)別整型常數(shù)識(shí)別標(biāo)識(shí)符和關(guān)鍵字qToken用表示q手工編寫(xiě)的簡(jiǎn)單詞法分析器lexan()2022-2-14編譯原理62expr expr + term print(+) expr - term print(-) termterm term * factor print(*) term / factor print(/) factorfactor (expr) num print(num.value) id print(id.lexeme)2022-2-14編譯原理63在輸入和語(yǔ)法分析器之間插入詞法分析器在輸