南開大學(xué)編譯原理第二章課件

1第二章一個(gè)簡(jiǎn)單的編譯器2學(xué)習(xí)內(nèi)容構(gòu)造一個(gè)以語法分析器為核心的編譯器——將中綴表達(dá)式轉(zhuǎn)換為后綴表示形式利用上下文無關(guān)文法描述源語言的語法結(jié)構(gòu)利用語法制導(dǎo)翻譯方法進(jìn)行表達(dá)式轉(zhuǎn)換構(gòu)造預(yù)測(cè)分析器，進(jìn)行語法分析，并同時(shí)進(jìn)行語法制導(dǎo)翻譯3學(xué)習(xí)內(nèi)容（續(xù)）構(gòu)造更復(fù)雜的詞法分析器——消除單字符單詞的限制，支持變量符號(hào)表的簡(jiǎn)單實(shí)現(xiàn)方法42.1概述語法描述

上下文無關(guān)文法，context-freegrammar

巴科斯-瑙爾范式，Backus-NaurForm，BNF語義描述：非形式化描述輔助代碼生成：

語法制導(dǎo)翻譯，syntax-directedtranslation5構(gòu)造一個(gè)簡(jiǎn)單的編譯器目標(biāo)：表達(dá)式中綴表示后綴表示

9-5+295-2+過程：語法制導(dǎo)翻譯器：語法分析＋中間代碼生成62.2語法定義上下文無關(guān)文法：描述語言的語法結(jié)構(gòu)if(expression)statementelsestatement

對(duì)應(yīng)的文法規(guī)則

stmt

if(expr)

stmtelsestmt產(chǎn)生式，productionif,else——單詞，終結(jié)符號(hào)，terminalexpr,stmt——單詞序列，非終結(jié)符號(hào)，nonterminal具有形式為…可7上下文無關(guān)文法四個(gè)部分組成一組終結(jié)符號(hào)，單詞，基本符號(hào)一組非終結(jié)符號(hào)（語法變量），語法范疇，語法概念一組產(chǎn)生式，定義語法范疇

產(chǎn)生式：A

α

A—一個(gè)非終結(jié)符，左部

α—終結(jié)符或/與非終結(jié)符串，右部一個(gè)特定的非終結(jié)符——開始符號(hào)，startsymbol8形式化定義幾個(gè)概念Σ：有窮字母表，元素——符號(hào)符號(hào)串：Σ中符號(hào)構(gòu)成的有窮序列空字：不含任何符號(hào)的序列，εΣ*：符號(hào)串全體，包括空字φ：空集{}，區(qū)分ε，{}，{ε}Σ*的子集U、V的積（連接）

9幾個(gè)概念（續(xù)）UV≠VU，(UV)W=U(VW)V自身的n次積（連接）記為VnV0={ε}V的閉包（closure）

每個(gè)符號(hào)串，都是V中符號(hào)串有限次連接正則閉包，V+=VV*10四元式定義上下文無法文法(VT,VN,S,P)VT：非空有限集，終結(jié)符號(hào)集合VN：非空有限集，非終結(jié)符號(hào)集合S：開始符號(hào)P

：產(chǎn)生式集合（有限集）

每個(gè)產(chǎn)生式形式A

a，其中

關(guān)于A的產(chǎn)生式

S至少在某個(gè)產(chǎn)生式左部出現(xiàn)一次11例2.1符號(hào)約定expr

expr+digit

expr

expr–digit

expr

digit

digit

0|1|2|3|4|5|6|7|8|9數(shù)字、運(yùn)算符、黑體字符串——終結(jié)符斜體字符串——非終結(jié)符左部相同可合并，‘|’——“或”的意思

expr

expr+digit|expr-digit|digit

候選式12產(chǎn)生式設(shè)計(jì)練習(xí)首先是“人會(huì)做”我們自己先把語法概念“什么模樣”搞清楚然后是“讓計(jì)算機(jī)會(huì)做”——符號(hào)化為這個(gè)語法概念起個(gè)名字，“模樣”中的其他語法概念、單詞也都有相應(yīng)的名字將語法概念放在產(chǎn)生式左部

“模樣”放在產(chǎn)生式右部

都是用名字替換掉語法概念和單詞——13產(chǎn)生式設(shè)計(jì)練習(xí)while(expression)statement

for(expression1;expression2;expression3)

statmentint(float,double,char)id1,id2,…;

對(duì)應(yīng)的產(chǎn)生式

stmt

while(expr)

stmt

對(duì)應(yīng)的產(chǎn)生式

stmt

for(expr;expr;expr)

stmttype

int|float|double|char

idlist

idlist,id|id

decl

typeidlist;14推導(dǎo)單詞串(string)：0個(gè)或多個(gè)單詞構(gòu)成的序列推導(dǎo)(derive)

由開始符號(hào)作為推導(dǎo)起點(diǎn)用產(chǎn)生式右部替換左部非終結(jié)符反復(fù)替換，最終得到單詞串語言(language)

語法所定義的語言——可由開始符號(hào)推導(dǎo)出的所有單詞串的集合15例2.2前面定義的表達(dá)式的CFG，可按如下步驟推導(dǎo)出表達(dá)式：9-5+2expr

expr+

digit

expr-digit+digit

digit-digit+digit

9-digit+digit

9-5+digit

9-5+2

P1:expr

expr+digitP2:expr

expr-digitP3:expr

digitP4:digit

9P4:digit

5P4:digit

2expr

expr+digit

expr

expr–digit

expr

digit

digit

0|1|2|3|4|5|6|7|8|916例2.2（續(xù)）exprdigitdigitexprdigitexpr952-+172.2.1語法分析樹(parsetree)圖示推導(dǎo)過程，推導(dǎo)語法樹：根節(jié)點(diǎn)標(biāo)記為開始符號(hào)每個(gè)葉節(jié)點(diǎn)用一個(gè)T或e標(biāo)記每個(gè)內(nèi)部節(jié)點(diǎn)用一個(gè)NT標(biāo)記節(jié)點(diǎn)A，孩子節(jié)點(diǎn)X1，X2，…，Xn

節(jié)點(diǎn)應(yīng)用了產(chǎn)生式A

X1X2…Xn對(duì)A

e

，節(jié)點(diǎn)A只有一個(gè)孩子節(jié)點(diǎn)e18例2.4葉節(jié)點(diǎn)從左至右構(gòu)成樹的輸出（yield）

開始符號(hào)推導(dǎo)出（生成）的單詞串語言：語法分析樹生成的單詞串集合exprdigitdigitexprdigitexpr952-+expr

expr+digitexpr

expr–digit192.2.2二義性（ambiguity）多個(gè)語法分析樹生成相同的單詞串

——多個(gè)意義定義無歧義語法或用附加規(guī)則消除歧義20例2.5exprexprexprexprexpr+2-59exprexprexprexprexpr-9+52expr

expr+expr|expr–expr|0|1|…|9212.2.3運(yùn)算符的結(jié)合率9-5-2——(9-5)-2還是9-(5-2)？左結(jié)合（leftassociative）：+,-,*,/右結(jié)合（rightassociative）：^,=exprdigitdigitexprdigitexpr952--expr

expr+digit

expr

expr–digit

expr

digit

digit

0|1|2|3|4|5|6|7|8|922右結(jié)合例asgnvarvarasgnvarasgncba==asgn

var=asgn|varvar

a|b|c|…|z232.2.4運(yùn)算符優(yōu)先級(jí)9+5*2——(9+5)*2還是9+(5*2)？運(yùn)算符優(yōu)先級(jí)：*的優(yōu)先級(jí)比+高典型的優(yōu)先級(jí)

()

*/——左結(jié)合

+-——左結(jié)合24結(jié)合優(yōu)先級(jí)的表達(dá)式文法expr

expr+term|expr–term|termterm

term*factor|term/factor|factorfactor

digit|(expr)digit

0|1|2|3|…|9expr、term、factor——不同的優(yōu)先級(jí)25Grammar-basedcompressionx=10011100010001110001111111000

s0

s1s3s2s3s4s4s3s1

100s2

s10s3

s4s2s4

11解壓——推導(dǎo)s0

s1s3s2s3s4s4s3

s1s4s2s2s4s2

s4s4s4s2

s1s4s10s10s4s10s4s4s4s10

100s410001000s41000s4s4s41000

1001110001000111000111111100026推導(dǎo)練習(xí)7–3*(4+6)expr

expr–term

term–term

factor–term

7–term7–term*factor7–factor*factor7–3*factor7–3*(expr)7–3*(expr

+term)7–3*(term

+term)7–3*(factor

+term)7–3*(4

+

term)7–3*(4

+

factor)7–3*(4

+

6)27推導(dǎo)練習(xí)S→SS+|SS*|a

給出aa+a*的推導(dǎo)和語法樹S→

SS*

→

SS+S*

→aS+S*

→aa+S*

→aa+a*282.3語法制導(dǎo)翻譯翻譯：為生成代碼，需保存語言結(jié)構(gòu)的類型、代碼位置、代碼數(shù)量等屬性(attribute)：類型、串、內(nèi)存位置等語法制導(dǎo)翻譯

syntax-directedtranslation語法制導(dǎo)定義

syntax-directeddefinition

屬性與語法結(jié)構(gòu)相關(guān)聯(lián)指明翻譯方法翻譯模式，translationscheme29怎么設(shè)計(jì)語法制導(dǎo)翻譯程序首先還是“人會(huì)做”設(shè)計(jì)文法程序員自己先理清翻譯的方法——每個(gè)語法結(jié)構(gòu)如何翻譯然后“讓計(jì)算機(jī)會(huì)做”設(shè)計(jì)文法符號(hào)屬性，表示翻譯結(jié)果把翻譯方法轉(zhuǎn)換為語義規(guī)則（語義動(dòng)作）——屬性的運(yùn)算，將其附著于產(chǎn)生式手工編寫或利用自動(dòng)生成工具形成語法分析程序，語義規(guī)則（語義動(dòng)作）嵌入到程序的恰當(dāng)位置，恰好實(shí)現(xiàn)了翻譯方法302.3.1表達(dá)式的后綴表示法表達(dá)式E的后綴形式Postfix(E)如何生成：E為變量或常量：Postfix(E)=EE=E1

opE2，op—二元運(yùn)算符，E1、E2—子表達(dá)式：

Postfix(E)=Postfix(E1

opE2)

=Postfix(E1)Postfix(E2)opE=(E1)：

Postfix(E)=Postfix(E1)(9-5)+295-2+

9-(5+2)952+-312.3.2語法制導(dǎo)定義基于語言的上下文無關(guān)文法語法符號(hào)——一組屬性產(chǎn)生式——一組語義規(guī)則(semanticrule)

——屬性值計(jì)算規(guī)則CFG+語義規(guī)則語法制導(dǎo)定義關(guān)聯(lián)關(guān)聯(lián)32語法制導(dǎo)翻譯的基本過程翻譯——輸入輸出映射過程輸入單詞串x語法分析樹節(jié)點(diǎn)n標(biāo)記為X，X.a——X的屬性計(jì)算節(jié)點(diǎn)n的X.a的值——利用X產(chǎn)生式的語義規(guī)則“注釋語法分析樹”（annotatedparsetree）332.3.3綜合屬性synthesizedattributes：

節(jié)點(diǎn)屬性值由其孩子節(jié)點(diǎn)屬性值所決定自底向上（bottom-up）計(jì)算34例2.6

expr、term都設(shè)置屬性t——字符串型，表示表達(dá)式的后綴表示形式expr

expr–term|expr+term|termterm

0|1|2|3|…|935翻譯方法語義規(guī)則9+5E:E1+E295+Post(E)=Post(E1)Post(E2)+expr

expr+termexpr.t=

expr.t||term.t||‘+’中綴后綴36例2.6（續(xù)）ProductionSemanticRuleexpr

expr1+term expr.t=expr1.t||term.t||‘+’expr

expr1–term expr.t=expr1.t||term.t||’-’expr

term expr.t=term.tterm

0 term.t=‘0’term

1 term.t=‘1’…. ….term

9 term.t=‘9’37例2.6（續(xù)）注釋語法分析樹expr.t=95-expr.t=9expr.t=95-2+term.t=5term.t=2term.t=92+5-938例2.7：機(jī)器人移動(dòng)描述指揮機(jī)器人行動(dòng)的指令序列，每個(gè)指令指揮機(jī)器人向一個(gè)方向前進(jìn)一個(gè)距離單位seq

seqinstr|

begininstr

east|north|west|south39例2.7：機(jī)器人移動(dòng)命令序列：

beginwestsoutheasteasteastnorthnorth40機(jī)器人移動(dòng)的語法制導(dǎo)定義ProductionSemanticRuleseq

beginseq.x:=0seq.y:=0seq

seq1instrseq.x:=seq1.x+instr.dx

seq.y:=seq1.y+instr.dyinstr

eastinstr.dx:=1instr.dy:=

0instr

northinstr.dx:=

0instr.dy:=

1instr

westinstr.dx:=-1instr.dy:=

0instr

southinstr.dx:=

0instr.dy:=

-141語法分析樹命令序列：beginwestsouthseq.x=-1

seq.y=0seq.x=0

seq.y=0seq.x=-1

seq.y=-1instr.dx=-1

instr.dy=0instr.dx=0

instr.dy=-1beginwestsouth422.3.4語法制導(dǎo)定義的實(shí)現(xiàn)樹的遍歷：計(jì)算完所有孩子節(jié)點(diǎn)的屬性，父節(jié)點(diǎn)才能計(jì)算自身屬性后序遍歷，深度優(yōu)先voidvisit(noden){

forn的每個(gè)孩子m（從左至右的順序）

visit(m);

利用n的語義規(guī)則計(jì)算其屬性值}432.3.5翻譯模式translationscheme同樣基于上下文無關(guān)文法語義動(dòng)作（semanticaction，程序片斷）嵌入產(chǎn)生式的右部

rest

+term{print(‘+’)}rest1

語法分析樹添加額外節(jié)點(diǎn)指明了語義動(dòng)作執(zhí)行順序restterm{print(‘+’)}+rest1442.3.6執(zhí)行翻譯模式語義動(dòng)作的執(zhí)行順序非常重要語法制導(dǎo)定義的特性——簡(jiǎn)單性

左部的翻譯（后綴字符串）＝右部終結(jié)符的翻譯按產(chǎn)生式中順序連接用翻譯模式實(shí)現(xiàn)語法制導(dǎo)定義語義動(dòng)作——打印額外字符串按照字符串在語法制導(dǎo)定義中的順序rest

+termrest1rest.t:=term.t||‘+’||rest1.t

rest

+term{print(‘+’)}rest1

45例2.8expr

expr+term{print(‘+’)}

expr-term{print(‘-’)}

termterm

0{print(‘0’)}term1

{print(‘1’)}…term9

{print(‘9’)}46帶語義動(dòng)作的語法分析樹“由左至右”執(zhí)行語義動(dòng)作邊進(jìn)行語法分析，邊執(zhí)行語義動(dòng)作termtermtermexprexprexpr952-+{print(‘-’)}{print(‘9’)}{print(‘5’)}{print(‘2’)}{print(‘+’)}47語法制導(dǎo)定義練習(xí)構(gòu)造翻譯模式，中綴前綴

構(gòu)造9-5*2的注釋語法分析樹expr→{print(‘+’);}expr+term |{print(‘-’);}expr–term |termterm→{print(‘*’);}term*factor |{print(‘/’);}term/factor |factorfactor→{print(num.value);}num |(expr)48Yacc語法分析器自動(dòng)生成工具語法分析器源程序語法分析器可執(zhí)行程序myyacc.y49Yacc程序結(jié)構(gòu)定義段：%{C語言代碼%}定義%%

規(guī)則段：語法規(guī)則、翻譯模式%%

用戶子程序段50例：簡(jiǎn)單表達(dá)式計(jì)算%{/****************************************************************************expr.yParserWizardgeneratedYACCfile.Date:2005年8月22日****************************************************************************/#include<ctype.h>#include<stdio.h>%}直接復(fù)制到語法分析程序中51例：簡(jiǎn)單表達(dá)式計(jì)算（續(xù)）%include{#ifndefYYSTYPE#defineYYSTYPEdouble#endif}%tokenNUMBER%left'+''-'%left'*''/'%rightUMINUS%%我們要翻譯的結(jié)果是什么？表達(dá)式值！

所以類型是doubleYYSTYPE是翻譯結(jié)果的類型運(yùn)算符優(yōu)先級(jí)復(fù)制頭文件中52例：簡(jiǎn)單表達(dá)式計(jì)算（續(xù)）lines : linesexpr'\n' {printf("%g\n",$2);} | lines'\n' | ;expr : expr'+'expr {$$=$1+$3;} | expr'-'expr {$$=$1-$3;} | expr'*'expr {$$=$1*$3;} | expr'/'expr {$$=$1/$3;} | '('expr')' {$$=$2;} | '-'expr%precUMINUS {$$=-$2;} | NUMBER ;表達(dá)式的上下文無關(guān)文法53例：簡(jiǎn)單表達(dá)式計(jì)算（續(xù)）NUMBER : '0' {$$=0.0;} | '1' {$$=1.0;} | '2' {$$=2.0;} | '3' {$$=3.0;} | '4' {$$=4.0;} | '5' {$$=5.0;} | '6' {$$=6.0;} | '7' {$$=7.0;} | '8' {$$=8.0;} | '9' {$$=9.0;} ;

%%54例：簡(jiǎn)單表達(dá)式計(jì)算（續(xù)）intyygettoken(void){ returngetchar();}intmain(void){ returnyyparse();}還沒有完整的詞法分析器，簡(jiǎn)單地令每個(gè)字符是一個(gè)單詞調(diào)用語法分析（翻譯）器55C++版本%{/****************************************************************************expr.yParserWizardgeneratedYACCfile.Date:2016年10月18日****************************************************************************/#include<iostream>#include<cctype>usingnamespacestd;%}56C++版本（續(xù)）%include{#ifndefYYSTYPE#defineYYSTYPEdouble#endif}//parsername%nameexpr//classdefinition{ //placeanyextraclassmembershere virtualintyygettoken();}57C++版本（續(xù)）//constructor{ //placeanyextrainitialisationcodehere}//destructor{ //placeanyextracleanupcodehere}//placeanydeclarationshere//%tokenNUMBER%left'+''-'%left'*''/'%rightUMINUS58C++版本（續(xù)）lines : linesexpr'\n' {cout<<$2<<endl;} | lines'\n' | ;expr : expr'+'expr {$$=$1+$3;} | expr'-'expr {$$=$1-$3;} | expr'*'expr {$$=$1*$3;} | expr'/'expr {$$=$1/$3;} | '('expr')' {$$=$2;} | '-'expr%precUMINUS {$$=-$2;} | NUMBER ;59C++版本（續(xù)）NUMBER : '0' {$$=0.0;} | '1' {$$=1.0;} | '2' {$$=2.0;} | '3' {$$=3.0;} | '4' {$$=4.0;} | '5' {$$=5.0;} | '6' {$$=6.0;} | '7' {$$=7.0;} | '8' {$$=8.0;} | '9' {$$=9.0;} ;60C++版本（續(xù)）intYYPARSERNAME::yygettoken(){ //placeyourtokenretrievingcodehere returngetchar();}intmain(void){ intn=1; exprparser; if(parser.yycreate()){ n=parser.yyparse(); } returnn;}612.4語法分析確定一個(gè)單詞串是否可由一個(gè)文法生成構(gòu)造語法分析樹時(shí)間復(fù)雜度O(n3)O(n)自頂向下分析方法，top-down

語法樹構(gòu)造——由根向葉

適合手工編寫語法分析器自底向上分析方法，bottom-up

語法樹構(gòu)造——由葉向根

適用更多文法，自動(dòng)生成工具622.4.1自頂向下分析方法從根節(jié)點(diǎn)（標(biāo)記為開始符號(hào)）開始構(gòu)造語法樹，不斷重復(fù)以下步驟對(duì)標(biāo)記為NTA的節(jié)點(diǎn)n

選擇一個(gè)關(guān)于A的產(chǎn)生式

利用產(chǎn)生式右部構(gòu)造n的孩子節(jié)點(diǎn)選擇下一個(gè)沒有擴(kuò)展（構(gòu)造孩子節(jié)點(diǎn)）的節(jié)點(diǎn)，對(duì)它執(zhí)行163例：Pascal的類型type

simple|id

|array[simple]of

typesimple

integer

|char

|numdotdotnumdotdot，”..”64語法分析樹構(gòu)造過程輸入：array[numdotdotnum]ofintegertype(a)(b)type]simpleof[arraytype65語法分析樹構(gòu)造過程輸入：array[numdotdotnum]ofinteger(c)type]simpleof[arraytypenumnumdotdot66語法分析樹構(gòu)造過程（續(xù)）type]simpleof[arraytypenumnumdotdotsimple(d)

67語法分析樹構(gòu)造過程（續(xù)）type]simpleof[arraytypenumnumdotdotsimpleinteger(e)68平凡算法初始狀態(tài)，只有一個(gè)根節(jié)點(diǎn)，標(biāo)記為開始符號(hào)，輸入指針指向第一個(gè)單詞對(duì)于NT節(jié)點(diǎn)選擇產(chǎn)生式（嘗試、回溯）構(gòu)造孩子節(jié)點(diǎn)對(duì)孩子節(jié)點(diǎn)從左至右繼續(xù)分析對(duì)于T節(jié)點(diǎn)與當(dāng)前輸入單詞進(jìn)行比較若匹配，輸入指針前移，處理下一個(gè)節(jié)點(diǎn)不匹配，可能需要回溯或報(bào)告錯(cuò)誤69掃描輸入分析過程type

simple|id

|array[simple]of

typesimple

integer

|char

|numdotdotnum70掃描輸入分析過程（續(xù)）type

simple|id

|array[simple]of

typesimple

integer

|char

|numdotdotnum71掃描輸入分析過程（續(xù)）type

simple|id

|array[simple]of

typesimple

integer

|char

|numdotdotnum72掃描輸入分析過程（續(xù)）type

simple|id

|array[simple]of

typesimple

integer

|char

|numdotdotnum73掃描輸入分析過程（續(xù)）742.4.2預(yù)測(cè)分析遞歸下降分析

recursive-descentparing

遞歸函數(shù)非終結(jié)符預(yù)測(cè)分析

predictiveparsing

只需一個(gè)超前單詞———產(chǎn)生式唯一確定75預(yù)測(cè)分析程序?qū)K結(jié)符的處理——匹配輸入，指針移動(dòng)procedure

match(t:token);beginiflookahead=t

then

lookahead:=nexttoken

elseerrorend;76預(yù)測(cè)分析程序（續(xù)）proceduretype;beginiflookaheadisin{integer,char,num}then

simple

elseif

lookahead=‘’thenbegin

match(‘’);match(id)

endelseiflookahead=arraythenbegin

match(array);match(‘[‘);

simple;

match(‘]’);match(of);

typeendelseerrorend;超前單詞選擇產(chǎn)生式分析孩子節(jié)點(diǎn)處理T處理NT，遞歸type

simple|id

|array[simple]of

typesimple

integer

|char

|numdotdotnum77預(yù)測(cè)分析程序（續(xù)）proceduresimple;beginiflookahead=integerthen

match(integer);

elseiflookahead=charthen

match(char);elseiflookahead=numthenbegin

match(num);match(dotdot);match(num)

endelseerrorend;782.4.4設(shè)計(jì)預(yù)測(cè)分析器一個(gè)超前單詞———產(chǎn)生式

推導(dǎo)出的單詞串的第一個(gè)單詞不同A

FIRST()：推導(dǎo)出的單詞串的第一個(gè)單詞的集合，可包含εFIRST(simple)={integer,char,num}

FIRST(

id)={}

FIRST(array

[simple]

oftype)={array}A,A

b，F(xiàn)IRST()和FIRST(b)不能相交唯一確定79預(yù)測(cè)分析器算法為每個(gè)NTA構(gòu)造一個(gè)函數(shù)，完成如下工作：產(chǎn)生式選擇對(duì)A

，超前符號(hào)在FIRST()中

選擇它若有沖突

預(yù)測(cè)分析法不適用A

e，且超前單詞不在其他任何產(chǎn)生式右部的FIRST集中

選擇它80預(yù)測(cè)分析器算法產(chǎn)生式的使用——依次處理右部符號(hào)對(duì)NT，調(diào)用對(duì)應(yīng)函數(shù)對(duì)T，與超前單詞比較，若匹配讀取下一單詞，否則錯(cuò)誤81結(jié)合翻譯模式簡(jiǎn)單方法首先構(gòu)造預(yù)測(cè)分析器實(shí)現(xiàn)語義動(dòng)作將語義動(dòng)作程序段復(fù)制到分析器代碼中位置？語義動(dòng)作位于語法符號(hào)X之后

程序段中將之放在緊接在處理X的代碼之后位于產(chǎn)生式開始，復(fù)制到函數(shù)最前面822.4.5左遞歸leftrecursion，導(dǎo)致無限循環(huán)解決方法：改寫文法AA|改寫為AR

RR|ε例expr

expr+term|term

expr

termrest

rest

+termrest|εabvoididlist(){

…if(lookahead==…){ idlist();

…}}一直不變id,id,…

83左遞歸vs.右遞歸842.5構(gòu)造表達(dá)式轉(zhuǎn)換的編譯器原始語法：需改寫expr

expr+term{print(‘+’)}expr

expr-term{print(‘-’)}expr

termterm

0{print(‘0’)}term1

{print(‘1’)}…term9

{print(‘9’)}85消除左遞歸、加入翻譯模式expr

termrestrest

+term{print(‘+’)

}rest|-term{print(‘-’)

}rest|εterm

0{print(‘0’)}term1

{print(‘1’)}…term9

{print(‘9’)}869-5+2翻譯為95-2+{print(‘2’)}exprtermterm{print(‘-’)}term{print(‘+’)}rest{print(‘5’)}{print(‘9’)}restrest25-9+

872.5.3非終結(jié)符實(shí)現(xiàn)代碼非終結(jié)符的分析函數(shù)——exprvoidexpr(){ term();rest();}expr

termrest88非終結(jié)符的分析函數(shù)——restvoidrest(){

if(lookahead==‘+’){ match(‘+’);term();putchar(‘+’);rest(); }

else

if(lookahead==‘-’){ match(‘-’);term();putchar(‘-’);rest(); }}rest

+term{print(‘+’)

}rest|-term{print(‘-’)

}rest|ε89非終結(jié)符的分析函數(shù)——termvoidterm(){

if(isdigit(lookahead)){ putchar(lookahead);match(lookahead); }

elseerror();}term

0{print(‘0’)}term1

{print(‘1’)}…term9

{print(‘9’)}902.5.4優(yōu)化——消除rest尾遞歸voidrest(){L: if(lookahead==‘+’){ match(‘+’);term();putchar(‘+’);gotoL; }

else

if(lookahead==‘-’){ match(‘-’);term();putchar(‘-’);gotoL; }}91優(yōu)化——rest并入exprvoidexpr(){ term();

while(1)

if(lookahead==‘+’){ match(‘+’);term();putchar(‘+’); }

else

if(lookahead==‘-’){ match(‘-’);term();putchar(‘-’); }

elsebreak;}922.5.5完整程序#include<ctype.h>intlookahead;main(){ lookahead=getchar(); expr(); putchar(‘\n’);}voidmatch(intt){

if(lookahead==t) lookahead=getchar();

elseerror();}932.6詞法分析2.6.1去除空白符和注釋2.6.2常量：<num,31>,<num,28>,…2.6.3標(biāo)識(shí)符與關(guān)鍵字識(shí)別count=count+incrementid=id+id單詞id不同實(shí)例count,increment的區(qū)分<id,符號(hào)表項(xiàng)指針>關(guān)鍵字（keyword），保留字（reserved）運(yùn)算符，<,<=,<>，可以每個(gè)運(yùn)算符作為一類單詞942.6.4詞法分析器接口usesgetchar()toreadcharacterpushesbackcusingungetc(c,stdin)returnstokentocallertokenvalSetsglobalvariabletoattributevaluelexan()lexicalanalyzer952.6.5詞法分析器程序#include<stdio.h>#include<ctype.h>#defineNUM256intlineno=1;inttokenval=NONE;intlexan(){ intt;

while(1){ t=getchar();

if(t==‘‘||t==‘\t’) ;96詞法分析器程序（續(xù)）

else

if(t==‘\n’) lineno++;

else

if(isdigit(t)){ tokenval=0;

while(isdigit(t)){ tokenval=tokenval*10+t–‘0’; t=getchar(); } ungetc(t,stdin);

returnNUM; }

else{tokenval=NONE;returnt;} }}972.7符號(hào)表不同階段保存（使用）單詞的不同信息2.7.1接口insert(s,t)：?jiǎn)卧~t的實(shí)例s（字符串）插入符號(hào)表，返回其索引lookup(s)：返回字符串s對(duì)應(yīng)表項(xiàng)的索引，若未找到，返回02.7.2保留字可存入符號(hào)表insert(“div”,div) insert(“mod”,mod)982.7.3一種實(shí)現(xiàn)方式

ARRAYsymtablelexptrtokenattributes

divmodididEOSiEOStnuocEOSdomEOSvidARRAYlexemes0123499帶有符號(hào)表功能的詞法分析器intlexan(){ charlexbuf[100]; charc; while(1){

從輸入字符序列讀取一個(gè)字符，保存到c;

if(c==‘‘||c==‘\t’);

elseif(c==‘\n’)lineno++;

elseif(isdigit(c)){ tokenval=c及后續(xù)數(shù)字組成的數(shù)值; returnNUM; }100帶有符號(hào)表功能的詞法分析器

elseif(isalpha(c)){

將c及后續(xù)字母、數(shù)字放入lexbuf; p=lookup(lexbuf); if(p=0) p=insert(lexbuf,ID); tokenval=p; return符號(hào)表項(xiàng)p的token值; }else{ tokenval=NONE; return字符c對(duì)應(yīng)的整數(shù); } }}101Lcc的符號(hào)表字符串的管理//string.cstaticstructstring{ char*str; intlen; structstring*link;}*buckets[1024];char*stringn(constchar*str,intlen){ inti; unsignedinth; constchar*end; structstring*p; assert(str); for(h=0,i=len,end=str;i>0;i--) //Hash h=(h<<1)+scatter[*(unsignedchar*)end++]; h&=NELEMS(buckets)-1;1