SyntaxAnalysis語法分析學(xué)習(xí)

SyntaxAnalysis語法分析Chapter4SyntaxAnalysis語法分析4.1

語法分析器的作用4.2

上下文無關(guān)文法

4.3

自頂向下語法分析4.4

自底向上語法分析4/6/202324.1

語法分析器的作用詞法分析源程序目標(biāo)程序語法分析語義分析文字表、符號(hào)表處理錯(cuò)誤處理中間代碼優(yōu)化中間代碼生成前端后端●

Thephaseofacompiler編譯程序的結(jié)構(gòu)目標(biāo)代碼生成4/6/202334.1

語法分析器的作用語法分析器詞法分析器記號(hào)流源程序前端其他部分分析樹中間表示符號(hào)表管理器出錯(cuò)處理器parser分析程序sequenceoftokens記號(hào)序列(input)syntaxtree語法樹(output)syntaxTree=parse();4/6/20234●源程序中可能出現(xiàn)的錯(cuò)誤①詞法錯(cuò)誤如非法字符或拼寫錯(cuò)關(guān)鍵字、標(biāo)識(shí)符等； 如@intege20times②語法錯(cuò)誤是指語法結(jié)構(gòu)出錯(cuò)，如少分號(hào)、begin/end不配對(duì)等。 begin x:=a+b y:=x;4.1

語法分析器的作用4/6/20235●源程序中可能出現(xiàn)的錯(cuò)誤①詞法錯(cuò)誤②語法錯(cuò)誤③靜態(tài)語義錯(cuò)誤④動(dòng)態(tài)語義錯(cuò)誤（邏輯錯(cuò)誤）4.1

語法分析器的作用如非法字符或拼寫錯(cuò)關(guān)鍵字、標(biāo)識(shí)符等；@ intege 20times是指語法結(jié)構(gòu)出錯(cuò)，如少分號(hào)、begin/end不配對(duì)等。begin x:=a+b； y:=x;如無窮遞歸、變量為零時(shí)作除數(shù)等。while(t){...};a:=a/b;類型不一致、參數(shù)不匹配等；如a,b:integer;x:array[1..10]ofinteger;x:=a+b;4/6/20236●語法錯(cuò)誤處理的目標(biāo)

清楚而準(zhǔn)確地報(bào)告錯(cuò)誤的出現(xiàn)（地點(diǎn)正確、不漏報(bào)、不錯(cuò)報(bào)也不多報(bào)）；迅速地從每個(gè)錯(cuò)誤中恢復(fù)過來（以便分析繼續(xù)進(jìn)行）；不應(yīng)使對(duì)語法正確源程序的分析速度降低太多。4.1

語法分析器的作用4/6/202374.2Context-freegrammars上下文無關(guān)文法●Thesyntaxofaprogramminglanguageisusuallygivenbythegrammarrulesofacontext-freegrammar.程序設(shè)計(jì)語言的語法通常是由上下文無關(guān)文法規(guī)則給出?！馮herulesofacontext-freegrammararerecursive.上下文無關(guān)文法的規(guī)則是遞歸的。4/6/202384.2.1上下文無關(guān)文法概述4.2.1.1Comparisontoregularexpressionnotation與正則表達(dá)式比較thecontext-freegrammar:number

number

digit|digit；digit0|1|2|3|……|9theregularexpression:number=digitdigit*digit=0|l|2|3|4|5l6|7|8|9*?|()=無不出現(xiàn)|含義變化(=,::=)thecontext-freegrammar:expexpopexp|(exp)|numberop+|–|*Backus-Naur范式(BNF文法)4/6/202394.2.2.1Specificationofcontext-freegrammarrules

上下文無關(guān)文法規(guī)則的說明●什么是文法？文法是對(duì)語言結(jié)構(gòu)的定義與描述。即從形式上用于描述和規(guī)定語言結(jié)構(gòu)的稱為“文法”（或稱“語法”）。例:請(qǐng)判斷英語句子Thebigelephantatethepeanut.語法上是否正確？4/6/202310<句子><主語><謂語><主語><冠詞><形容詞><名詞><冠詞>the<形容詞>big<名詞>elephant|peanut<謂語><動(dòng)詞><賓語><動(dòng)詞>ate<賓語><冠詞><名詞>解：(1)已知語法規(guī)則(2)由規(guī)則推導(dǎo)句子推導(dǎo)方法：從一個(gè)要識(shí)別的符號(hào)開始推導(dǎo)，即用相應(yīng)規(guī)則的右部來替代規(guī)則的左部，每次僅用一條規(guī)則去進(jìn)行推導(dǎo)。<句子>=><主語><謂語><主語><謂語>=><代詞><謂語>……直到所有帶<>的符號(hào)都由終結(jié)符號(hào)替代為止。4/6/202311<句子>=><主語><謂語>=><冠詞><形容詞><名詞><謂語>=>the<形容詞><名詞><謂語>=>thebig<名詞><謂語>=>thebigelephant<謂語>=>thebigelephant<動(dòng)詞><賓語>=>thebigelephantate<賓語>=>thebigelephantate<冠詞><名詞>=>thebigelephantatethe<名詞>=>thebigelephantatethepeanut<句子>::=<主語><謂語><主語>::=<冠詞><形容詞><名詞><冠詞>::=the<形容詞>::=big<名詞>::=elephant|peanut<謂語>::=<動(dòng)詞><賓語><動(dòng)詞>::=ate<賓語>::=<冠詞><名詞>上述推導(dǎo)可寫成<句子>=>thebigelephantatethepeanut+4/6/202312(1)有若干語法成分同時(shí)存在時(shí)，總是從最左的語法成分進(jìn)行推導(dǎo)，這稱之為最左推導(dǎo)，類似的有最右推導(dǎo)（一般推導(dǎo)）。(2)從一組規(guī)則可推出不同的句子，如以上規(guī)則還可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它們?cè)谡Z法上都正確，但在語義上都不正確。所謂文法是在形式上對(duì)句子結(jié)構(gòu)的定義與描述，而未涉及語義問題。Note4/6/2023134.2.2.2Derivationsandthelanguagedefinedbyagrammar推導(dǎo)及由文法定義的語言1.相應(yīng)的正則式：2.derivation推導(dǎo)例：根據(jù)文法，請(qǐng)判斷程序(34-3)*42語法上是否正確？

expexpopexp|(exp)|numberop+|–|*(1)exp=>expopexp [exp

expopexp](2)=>

expopnumber [exp

number](3)=>

exp*number [op*](4)=>(exp)*number [exp

(exp)](5)=>(expopexp)*number [exp

expopexp](6)=>

(expopnumber)*number[expnumber](7)=>

(exp-number)*number[op

-](8)=>(number-number)*number[exp

number](number-number)*number4/6/202314L(G)={s|exp=>*s}●文法定義的（產(chǎn)生的）語言exp：開始符號(hào)thestartsymbol=>*：星推導(dǎo)(=>+：正推導(dǎo))s：句子expexpopexp|(exp)|numberop+|–|*exp：開始符號(hào)thestartsymbolexp

number：產(chǎn)生式Nonterminals(非終結(jié)符)Terminals(終結(jié)符)●文法4/6/202315●Example1)已知文法G：E(E)|a，請(qǐng)問文法定義的語言是什么？L(G)={a,(a),((a)),(((a))),…}={(na)n|naninteger>=0}2)已知文法G：E(E)，請(qǐng)問文法定義的語言是什么？空3)已知文法G：EE+a|a，請(qǐng)問文法定義的語言是什么？L(G)={a,a+a,a+a+a,a+a+a+a,...}4)已知正則式為a+，請(qǐng)問相應(yīng)的文法及定義的語言是什么？G:AAa|aorAaA|aL(a*)={an|naninteger>=0}leftrecursiverightrecursive5)已知正則式為a*，請(qǐng)問相應(yīng)的文法是什么？G:AAa|orAaA|Recursive遞歸Grammar文法AA|

A

A|

4/6/202316●Example6)已知文法定義的語言如下(C的嵌套if語句)，請(qǐng)寫出該文法？otherif(0)otherif(1)otherif(0)otherelseotherif(1)otherelseotherif(0)if(0)otherif(0)if(1)otherelseotherif(1)otherelseif(0)otherelseotherG:Statementif-stmt|otherif-stmtif(exp)statement|if(exp)statementelsestatementexp0|1statementif-stmt|otherif-stmtif(exp)statementelse-partelse-partelsestatement|exp0|1OR4/6/202317●Example7)已知文法A(A)A|，請(qǐng)問(()(()))()語法正確嗎？A=>(A)A [A(A)A]=>(A)(A)A [A(A)A]=>(A)(A) [A

]=>(A)() [A

]=>((A)A)() [A(A)A]=>(()A)() [A

]=>(()(A)A)() [A(A)A]=>(()(A))() [A

]=>(()((A)A))(

) [A(A)A]=>(()(()A))() [A

]=>(()(()))() [A

]∴(()(()))()語法正確4/6/202318●Example8)已知文法G如下，請(qǐng)問文法定義的語言是什么？stmt-sequence

stmt;stmt-sequence|stmtstmtsL(G)={s,s;s,s;s;s,...)若例8中允許語句序列為空，即定義的語言為

L(G‘)={

,s;,s;s;,s;s;s;,...)，則相應(yīng)的文法是什么？stmt-sequence

stmt;stmt-sequence|

stmt

s若例8中允許語句序列為空，但要求分號(hào)作為語句分隔符，即定義的語言為

L(G‘)={,s,s;s,s;s;s,...)，則相應(yīng)的文法是什么？stmt-sequencenonempty-stmt-sequence|

nonempty-stmt-sequencestmt；nonempty-stmt-sequence|stmtstmts4/6/202319●Example若例8中允許語句序列為空，但要求分號(hào)作為語句結(jié)束符，

即定義的語言為

L(G‘)={

;,s;,;s;,s;s;,;s;s;,s;s;s;,...)，則相應(yīng)的文法是什么？stmt-sequencestmt-other1stmt-other2stmt-other1stmt|

stmt-other2;stmtstmt-other2|;stmts4/6/2023204.2.3Parsetreesandabstractsyntaxtrees

分析樹與抽象的語法樹(1)exp=>expopexp [exp

expopexp](2) =>(exp)opexp [exp(exp)](3) =>(expopexp)opexp [exp

expopexp](4) =>(numberopexp)opexp [exp

number](5) =>(number-exp)opexp [op-](6) =>(number-number)opexp [exp

number](7) =>(number-number)*exp [op*](8) =>(number-number)*number [expnumber](1)exp=>expopexp [exp

expopexp](2)=>

expopnumber [exp

number](3)=>

exp*number [op*](4)=>(exp)*number [exp

(exp)](5)=>(expopexp)*number [exp

expopexp](6)=>

(expopnumber)*number[expnumber](7)=>

(exp-number)*number[op

-](8)=>(number-number)*number[exp

number]●derivation推導(dǎo)最右推導(dǎo)最左推導(dǎo)4/6/2023211)推導(dǎo)(1)exp=>expopexp(2)=>numberopexp(3)=>number+exp(4)=>number+number(1)exp=>expopexp(2)=>expopnumber(3)=>exp+number

(4)=>number+number

●分析樹(與推導(dǎo)相對(duì)應(yīng)的作了標(biāo)記的樹)2)分析樹(1)exp=>expopexp(2)=>exp+exp(3)=>number+exp(4)=>number+number

exp+opexpexpnumbernumberexp+opexpexpnumbernumberexp+opexpexpnumbernumber1234143213244/6/202322(1)exp=>expopexp (2) =>(exp)opexp

(3) =>(expopexp)opexp(4) =>(numberopexp)opexp

(5) =>(number-exp)opexp

(6) =>(number-number)opexp(7) =>(number-number)*exp

(8) =>(number-number)*number(1)exp=>expopexp (2)=>

expopnumber

(3)=>

exp*number (4)=>(exp)*number

(5)=>(expopexp)*number

(6)=>

(expopnumber)*number(7)=>

(exp-number)*number(8)=>(number-number)*number●derivation推導(dǎo)numberexp*opexpexpnumber14exp()opexpexp-number235678numberexp*opexpexpnumber12exp()opexpexp-number8736544/6/2023231)表達(dá)式3+4的分析樹：●Abstractsyntaxtrees抽象語法樹(簡(jiǎn)稱語法樹)exp+opexpexpnumbernumber3 4+342)語法樹：expOpExp(op,exp,exp)|ConstExp(integer)opPlus|Minus|Times3)

簡(jiǎn)單的算術(shù)表達(dá)式抽象語法樹的文法:例1：簡(jiǎn)單表達(dá)式的抽象語法樹解：4/6/202324typedefenum{Plus,Minus,Times}OpKind

typedefenum{OpK.ConstK}ExpKind;

typedefstructstreenode

{ExpKindkind;

OpKindop;structstreenode*lchild,*rchild;intval;}STreeNode;typedefSTreeNode*SyntaxTree;4)簡(jiǎn)單的算術(shù)表達(dá)式抽象語法樹的存儲(chǔ)結(jié)構(gòu)：4/6/202325解：分析樹例2：if語句的抽象語法樹1)已知簡(jiǎn)化了的if語句的文法：statementif-stmt|otherif-stmtif(exp)statement|if(exp)statementelsestatementexp0|1請(qǐng)畫出串if(0)otherelseother的語法樹!if-stmtelseexpstatement0statementif()statementotherother4/6/202326解：分析樹2)已知文法：statementif-stmt|otherif-stmtif(exp)statementelse-partelse-partelsestatement|exp0|1請(qǐng)畫出串if(0)otherelseother的語法樹!if-stmtelseexpstatement0statementif()statementotherotherelse-part4/6/2023273)if語句的抽象語法樹：if0otherother4)if語句的存儲(chǔ)表示：typedefenum{ExpK,StmtK)NodeKind;typedefenum{Zero.One}ExpKind;typedefenum{IfK.OtherK)StmtKind;typedefstructstreenode{NodeKindkind;ExpKindekind; .StmtKindskind;structstreenode*test,*thenpart,*elsepart;}STreeNode;

typedefSTreeNode*SyntaxTree;4/6/202328解：分析例3：順序結(jié)構(gòu)的語句的抽象語法樹1)已知順序結(jié)構(gòu)的語句的文法：

stmt-sequence

stmt;stmt-sequence|stmtstmts請(qǐng)畫出串s;s;s的語法樹!stmt-sequence;stmtstmt-sequences;stmtssstmt-sequencestmt4/6/2023292)順序結(jié)構(gòu)的語句的抽象語法樹;ss;sseqsssseqsssseqssssss≌OR4/6/2023304.2.4Ambiguity二義性4.2.4.1AmbiguousGrammars二義性文法例：已知簡(jiǎn)單整型算術(shù)文法，exp

expopexp|(exp)|numberop+|-|*

請(qǐng)畫出串34-3*42的語法樹!解：1)推導(dǎo)2)分析樹3)語法樹4/6/202331解：1)最左推導(dǎo)例：已知簡(jiǎn)單整型算術(shù)文法exp

expopexp|(exp)|numberop+|-|*請(qǐng)畫出串34-3*42的分析樹!exp=>expopexp=>expopexpopexp=>numberopexpopexp=>number-expopexp=>number-

numberopexp=>number-number*exp=>number-number*

numberandexp=>expopexp=>number

op

exp=>number-exp

=>number-

expopexp=>number-numberopexp

=>number-number*exp=>number-number*numbernumberexp*opexpexpnumberopexpexp-numbernumberexp-opexpexpnumberopexpexp*number2)分析樹4/6/202332例：已知簡(jiǎn)單整型算術(shù)文法exp

expopexp|(exp)|numberop+|-|*請(qǐng)畫出串34-3*42的分析樹!*342-34-343*423)語法樹●ambiguousgrammar二義性文法可生成兩個(gè)不同分析樹的串的文法叫二義性文法?！裣x性規(guī)則◆不修改文法，指定正確的分析樹(或語法樹)；◆修改文法(優(yōu)先級(jí)、結(jié)合性)4/6/2023334.2.4.2Precedenceandassociativity優(yōu)先級(jí)和結(jié)合性●precedencecascade優(yōu)先級(jí)聯(lián)具有相同優(yōu)先級(jí)的算符歸納在一組，并為每一種優(yōu)先級(jí)規(guī)定不同的規(guī)則。例：將“乘法比加法和減法優(yōu)先”添加到簡(jiǎn)單的算術(shù)表達(dá)式文法。expexpaddopexp|termaddop

+|-termtermmulopterm|factormulop

*factor(exp)|number4/6/202334●結(jié)合性例：將“乘法比加法和減法優(yōu)先，并且左結(jié)合”添加到簡(jiǎn)單的算術(shù)表達(dá)式文法。exp

expaddopterm|termaddop+|-term

termmulopfactor|factormulop*factor

(exp)|numberexp

expaddopexp|termleftassociative：exp

expaddopterm|termrightassociative：exp

term

addopexp|term4/6/2023354.2.4.3Thedanglingelseproblem懸掛else問題例：文法是二義性文法嗎？

statement

if-stmt|otherif-stmt

if(exp)statement|if(exp)statementelsestatementexp0|1解：串if(0)if(1)otherelseother的分析樹1：if-stmtexp0statementif()statementif-stmtexp1if()statementotherelsestatementother4/6/202336if-stmtexp0statementif()statementif-stmtexp1if()statementelsestatementotherother

statement

if-stmt|otherif-stmt

if(exp)statement|if(exp)statementelsestatementexp0|1串if(0)if(1)otherelseother的分析樹2：4/6/202337

statement

if-stmt|otherif-stmt

if(exp)statement|if(exp)statementelsestatementexp0|1●mostcloselynestedrule用于懸掛else問題的最近嵌套規(guī)則

(消除二義性的規(guī)則)statement

matched-stmt|unmatched-stmtmatched-stmtif(exp)matched-stmtelsematched-stmt|otherunmatched-stmtif(exp)statement|if(exp)matched-stmtelseunmatched-stmtexp0|1最近嵌套規(guī)則matched-stmt：匹配的語句(不含不帶else的if語句的語句)；unmatched-stmt：不匹配的語句(含不帶else的if語句的語句)；4/6/202338

statement

if-stmt|otherif-stmt

if(exp)statement|if(exp)statementelsestatementexp0|1●消除二義性的規(guī)則方法2if-stmtifconditionthenstatement-sequenceendif

|ifconditionthenstatement-sequenceelse

statement-sequenceendif4/6/2023394.2.4.4Inessentialambuguity無關(guān)緊要二義性文法有二義性，但總生成唯一的抽象的語法樹。例：如下文法是無關(guān)緊要二義性文法！stmt-sequence

stint-sequence;stmt-sequence|stmtstmts4/6/2023404.2.5extendednotations:EBNFandsyntaxdiagrams

擴(kuò)展的表示法：EBNF和語法圖●extendedBNF,orEBNF表示法1)遞歸(重復(fù)：{}表示)左遞歸：A

A|A

* A

{}右遞歸：A

A|A

* A{}文法正則式EBNF4/6/2023412)選擇([]表示)statement

if-stmt|otherif-stmtif(exp)statement[

elsestatement]exp0|1例：stmt-Sequence

stmt;stmt-Sequence|stmtstmts解：stmt-sequence{stmt;}stmt(rightrecursiveform)stmt-sequencestmt{;stmt}(leftrecursiveform)例：stmt-sequence

stmt;stmt-sequence|stmt解：stmt-sequence

stmt[

;stmt-sequence]4/6/2023424.2.6Formalpropertiesofcontext-freelanguage

上下文無關(guān)語言的形式特性4.2.6.1Aformaldefinitionofcontext-freelanguage上下文無關(guān)文法的形式定義G=(T,N,P,S)

◆AsetTofterminals.（終結(jié)符集合T）◆AsetNofnonterminals(disjointfromT)

(非終極符集合N(與T不相交)）◆AsetPofproductions,orgrammarrules,oftheformAa,whereAisanelementofNandaisanelementof(TN)*(產(chǎn)生式或文法規(guī)則Aa集合P，其中A∈N,a∈(TN)*)◆AstartsymbolSfromthesetN(開始(識(shí)別)符號(hào)∈N)thesetofsymmbols(符號(hào)集)：TNT∩N＝ΦA(chǔ)a

，其中|A|=1

|a|>=0注：4/6/202343P={<無符號(hào)整數(shù)><數(shù)字串>；<數(shù)字串>

<數(shù)字串><數(shù)字>；<數(shù)字串><數(shù)字>；

<數(shù)字>

0；

<數(shù)字>

1；

…………

<數(shù)字>

9；}S=<無符號(hào)整數(shù)>；例：無符號(hào)整數(shù)的文法如下，可否化簡(jiǎn)？ G[<無符號(hào)整數(shù)>]=（N，T，P，S） N＝{<無符號(hào)整數(shù)>,<數(shù)字串>,<數(shù)字>} T={0,1,2,3,……9}4/6/202344●文法的簡(jiǎn)化方法：產(chǎn)生式左邊符號(hào)構(gòu)成集合N，且S∈N具有相同的左部的產(chǎn)生式，可以合在一起解：無符號(hào)整數(shù)的文法簡(jiǎn)化為：（產(chǎn)生式集合+開始符號(hào)）G[<無符號(hào)整數(shù)>]<無符號(hào)整數(shù)><數(shù)字串>；<數(shù)字串>

<數(shù)字串><數(shù)字>|<數(shù)字>；<數(shù)字>0|1|2|3|……|94/6/202345●文法G=(T,N,P,S)的相關(guān)術(shù)語G=(T,N,P,S)，其中v=aA，w=a

，A∈N

a,,∈(TN)*

若A

∈P，則aA

=>a

，即v=>w

稱為v直接產(chǎn)生w(或w是v直接推導(dǎo)，或w直接規(guī)約到v)<無符號(hào)整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字><數(shù)字>1<數(shù)字>10(6)=>=>(1)=>(3)(5)=>=>(2)例：已知文法G[<無符號(hào)整數(shù)>](1)<無符號(hào)整數(shù)><數(shù)字串>；(2)<數(shù)字串><數(shù)字串><數(shù)字>(3)<數(shù)字串><數(shù)字>根據(jù)文法G能否推導(dǎo)出10？(4)<數(shù)字>0;(5)<數(shù)字>1;…………(13)<數(shù)字>9;1)直接推導(dǎo)4/6/2023462）+推導(dǎo)G=(T,N,P,S)，a=a1，=an，其中a,

∈(TN)*

若a1

=>a2

a2

=>a3，…，an-1

=>an即a=>+稱為a推導(dǎo)出(產(chǎn)生)(推導(dǎo)長(zhǎng)度為n≥１)(或規(guī)約到a)例：<無符號(hào)整數(shù)>=><數(shù)字串>=><數(shù)字串><數(shù)字>=><數(shù)字><數(shù)字>=>1<數(shù)字>=>10即<無符號(hào)整數(shù)>=>+103）*推導(dǎo)G=(T,N,P,S)，a,

∈(TN)*

若a=>+，或a=

稱為a推導(dǎo)出(產(chǎn)生)(推導(dǎo)長(zhǎng)度為n≥０)(或規(guī)約到a)4/6/2023474）leftmostderivation最左推導(dǎo)G=(T,N,P,S)，S=>*w，每個(gè)推導(dǎo)步驟aA

=>a

，都有A∈N，,∈(TN)*，a∈T*

稱為S=>*w為最左推導(dǎo)。最左推導(dǎo)：若符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，先推左邊的。最右推導(dǎo)：若符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，先推右邊的。5）rightmostderivation最右推導(dǎo)（規(guī)范推導(dǎo)）G=(T,N,P,S)，S=>*w，每個(gè)推導(dǎo)步驟aA

=>a

，都有A∈N，a,

∈(TN)*，∈T*

稱為S=>*w為最右推導(dǎo)。4/6/2023486）sententialform(句型)G=(T,N,P,S)，S=>*a，a∈(TN)*

稱a為句型。7）sentence(句子)G=(T,N,P,S)，S=>*a，a∈T*稱a為句子。

8）文法產(chǎn)生的語言L(G[S])G=(T,N,P,S)，L(G[S])={a|S=>*a，a∈T*}稱L(G[S])為文法G產(chǎn)生的語言。4/6/2023499）短語、簡(jiǎn)單短語G=(T,N,P,S)，w=xuy∈(TN)*

為文法的句型,若S=>xUy,且U=>+u,則u是句型w相對(duì)于U的短語；若S=>xUy,

且U=>u,則u是句型w相對(duì)于U的簡(jiǎn)單短語;其中U∈N，u∈(TN)+,x,y∈(TN)*

10）句柄任一句型的最左簡(jiǎn)單短語稱為該句型的句柄。

短語、簡(jiǎn)單短語是相對(duì)于句型而言，一個(gè)句型可能有多個(gè)短語、簡(jiǎn)單短語，句柄只能有一個(gè)。Note4/6/202350例：有文法G[E]：

ET|E+T|E-T

TF|T*F|T/F

Fi|(E)請(qǐng)判斷(E+T)*i+F是G的一句型嗎？如果是，請(qǐng)畫出它的推導(dǎo)的分析樹，并寫出該樹的短語、簡(jiǎn)單短語、句柄。●Example解：∵E=>*(E+T)*i+F∴(E+T)*i+F是G的一句型4/6/202351簡(jiǎn)單短語(每棵簡(jiǎn)單子樹的葉組成簡(jiǎn)單短語):E+T是句型(E+T)*i+F相對(duì)于E的簡(jiǎn)單短語；i是句型(E+T)*i+F相對(duì)于F的簡(jiǎn)單短語；F是句型(E+T)*i+F相對(duì)于T的簡(jiǎn)單短語。短語(每棵子樹的葉組成短語):(E+T)*i+F是句型(E+T)*i+F相對(duì)于E的短語；(E+T)*I是句型(E+T)*i+F相對(duì)于E、T的短語；(E+T)是句型(E+T)*i+F相對(duì)于T、F的短語；E+T是句型(E+T)*i+F相對(duì)于E的短語；i是句型(E+T)*i+F相對(duì)于F的短語；F是句型(E+T)*i+F相對(duì)于T的短語。句柄(最左簡(jiǎn)單子樹的葉組成句柄):E+T是句型(E+T)*i+F相對(duì)于E的最左簡(jiǎn)單短語。4/6/20235211）文法G的分析樹1.Eachnodeislabeledwithaterminaloranonterminalor.2.TherootnodeislabeledwiththestartsymbolS.3.Eachleafnodeislabeledwithaterminalorwith.4.Eachnonleafnodeislabeledwithanonterminal.5.IfanodewithlabelANhasnchildrenwithlabelsX1,X2,...,Xn(whichmaybeterminalsornonterminals),thenAX1X2...XnP(aproductionofthegrammar).每個(gè)分析樹只有唯一的一個(gè)最左推導(dǎo)和一個(gè)最右推導(dǎo)。最左推導(dǎo)與分析樹的前序編號(hào)相對(duì)應(yīng)；最右推導(dǎo)與分析樹的后序編號(hào)相對(duì)應(yīng)Note4/6/2023534.2.6.2Thechomskyhierarchy喬姆斯基層次文法和語言分類：0型、1型、2型、3型（喬姆斯基層次）

0型文法稱為短語結(jié)構(gòu)文法（非限制）。規(guī)則的左部和右部都可以是符號(hào)串，一個(gè)短語可以產(chǎn)生另一個(gè)短語。0型語言：L0語言可以用圖靈機(jī)(Turing)接受.●0型：P：uv其中u∈(TN)+

，v∈(TN)*

1型文法稱為上下文敏感或上下文有關(guān)文法。也即只有在x,y這樣的上下文中才能把U改寫為u

；1型語言：L1語言可以由一種線性界限自動(dòng)機(jī)接受.●1型：P：xUyxuy其中U∈N，x,y,u∈(TN)*4/6/202354

3型文法稱為正則文法。它是對(duì)2型文法進(jìn)行進(jìn)一步限制。3型語言：L3又稱正則語言(正則集合)可以由有窮自動(dòng)機(jī)接受?！?型：(左線性)P：Ut或UWt其中U、W∈Nt∈T(右線性)P：Ut或UtW其中U、W∈Nt∈T

0型文法稱為上下文無關(guān)文法。也即把U改寫為v時(shí)，不必考慮上下文。

2型文法與BNF表示相等價(jià)。

2型語言：L2語言可以由下推自動(dòng)機(jī)接受.●2型：P：Uv其中U∈N

，v∈(TN)*

4/6/202355●0型、1型、2型、3型比較產(chǎn)生式左部范圍右部范圍|左部||右部|0型uv(TN)+(TN)*>=1>=01型xUyxuy(TN)+(TN)*>=1>=02型UvN(TN)*=1>=03型UtUWtNTN=1<=2●3型：P：Ut或UWt其中U、W∈Nt∈T●2型：P：Uv其中U∈N

，v∈(TN)*

●0型：P：uv其中u∈(TN)+

，v∈(TN)*

●1型：P：xUyxuy其中U∈N，x,y,u∈(TN)*L3L2L1L04/6/202356附：自動(dòng)機(jī)、正則文法、正則表達(dá)式

的相互轉(zhuǎn)化正則文法NFA正則表達(dá)式123456DFA最小化4/6/202357（1）有窮自動(dòng)機(jī)正則文法1.對(duì)轉(zhuǎn)換函數(shù)T(A,t)=B，可寫成一個(gè)產(chǎn)生式:AtB算法:2.對(duì)可接受狀態(tài)Z,增加一個(gè)產(chǎn)生式:Zε3.有窮自動(dòng)機(jī)的初態(tài)對(duì)應(yīng)于文法的開始符號(hào),有窮自動(dòng)機(jī)的字母表為文法的終結(jié)符號(hào)集。ABt4/6/202358例:求出如圖NFA等價(jià)的正則文法G。ABCDstartaaabbbb1.對(duì)轉(zhuǎn)換函數(shù)T(A,t)=B，可寫成一個(gè)產(chǎn)生式:AtB2.對(duì)可接受狀態(tài)Z,增加一個(gè)產(chǎn)生式:Z

ε3.有窮自動(dòng)機(jī)的初態(tài)對(duì)應(yīng)于文法的開始符號(hào),有窮自動(dòng)機(jī)的字母表為文法的終結(jié)符號(hào)集。G=({A,B,C,D},{a,b},P,A)其中P:AaBAbDBbCCaACbDCεDaBDbDDε解：4/6/202359（2）正則文法G有窮自動(dòng)機(jī)M算法:1.字母表與G的終結(jié)符號(hào)相同.2.為G中的每個(gè)非終結(jié)符生成M的一個(gè)狀態(tài),G的開始符號(hào)S是開始狀態(tài)S;3.增加一個(gè)新狀態(tài)Z,作為NFA的終態(tài)4.對(duì)G中的形如AtB的產(chǎn)生式,其中t為終結(jié)符或ε,A和B為非終結(jié)符,構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=B5.對(duì)G中的形如At的產(chǎn)生式,構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=Z4/6/202360例:求與文法G[E]等價(jià)的NFAG[E]:EaA|bB|εAaB|bABaE|bA|εEZABstartaaabbbεε解：1.字母表與G的終結(jié)符號(hào)相同.2.為G中的每個(gè)非終結(jié)符生成M的一個(gè)狀態(tài),G的開始符號(hào)S是開始狀態(tài)S;3.增加一個(gè)新狀態(tài)Z,作為NFA的終態(tài)4.對(duì)G中的形如AtB的產(chǎn)生式,其中t為終結(jié)符或ε,A和B為非終結(jié)符,構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=B5.對(duì)G中的形如At的產(chǎn)生式,構(gòu)造M的一個(gè)轉(zhuǎn)換函數(shù)f(A,t)=Z4/6/202361（3）正則式有窮自動(dòng)機(jī)1.(a)對(duì)于正則式φ,所構(gòu)造NFA:xy(b)對(duì)于正則式ε,所構(gòu)造NFA:xyε(c)對(duì)于正則式a,a∈Σ,則NFA:xya4/6/2023622.若s,t為Σ上的正則式,相應(yīng)的NFA分別為N(s)和N(t);(a)對(duì)于正則式R=s|t,NFA(R)(b)對(duì)正則式R=st,NFA(R)N(s)N(t)εεεεxy或:N(s)xN(t)yxyN(s)N(t)εεε(c)對(duì)于正則式R=s*,NFA(R)(d)對(duì)R=(s),與R=S的NFA一樣.xyN(s)εεεε4/6/202363令r2=b,則有

45b令r3=r1|r2,則有

164532abεεεε令r4=r3則有:

164532abεεεε*0ε7εεε從左到右分解R,令r1=a,第一個(gè)a,則有

23a解:例:為R=(a|b)*abb構(gòu)造NFA,使得L(N)=L(R)4/6/202364令r10=r4r9則最終得到NFAM:

164532abεεεε0ε7εεε1089abb分解R的方法有很多種?。?！令r5=a,令r6=b令r7=b令r8=r5r6令r9=r8r7則有

910b87baR=(a|b)*abb4/6/20236503214starta,ba,ba,bbbaax03412yεεεaa,ba,ba,babb（4）有窮自動(dòng)機(jī)正則式例:M如下，求相應(yīng)的正則表達(dá)式。解:(Ⅰ)加x,y(新的初態(tài)和終態(tài))4/6/202366(Ⅱ)消除M中的所有結(jié)點(diǎn)a|bx024yεεεaabba|ba|bx0yaa(a|b)*bb(a|b)*a|bεxy(a|b)*(aa|bb)(a|b)*x03412yεεεaa,ba,ba,babb解:(Ⅰ)加x,y(新的初態(tài)和終態(tài))4/6/202367利用以下轉(zhuǎn)換規(guī)則,直至只剩下一個(gè)開始符號(hào)定義的產(chǎn)生式,并且產(chǎn)生式的右部不含非終結(jié)符.規(guī)則規(guī)則1規(guī)則2規(guī)則3文法產(chǎn)生式正則式AxB,ByAxA|yAx,AyA=xyA=x*yA=x|y（5）正則文法正則式例:有文法G[s]SaA|aA

aA|dA|a|d求相應(yīng)的正則表達(dá)式解:A=>(aA|dA)|(a|d)

=>(a|d)A|(a|d)=>(a|d)*(a|d)代入規(guī)則1得：S=>a(a|d)*(a|d)|a∴S=a((a|d)*(a|d)|ε)4/6/202368算法:1)對(duì)任何正則式r,選擇一個(gè)非終結(jié)符S作為識(shí)別符號(hào).并產(chǎn)生產(chǎn)生式Sr2)若x,y是正則式,例:將R=a(a|d)*轉(zhuǎn)換成相應(yīng)的正則文法解:1)Sa(a|d)*2)SaAA(a|d)*S

aA

A(a|d)AAεS

aAA

aA|dAAε（6）正則式正則文法規(guī)則規(guī)則1規(guī)則2規(guī)則3文法產(chǎn)生式AxB,ByAxA|yAx,Ay正則式A=xyA=x*yA=x|y4/6/2023694.2.7SyntaxoftheTINYlanguageTINY語言的語法4/6/202370programstmt-sequencestmt-sequencestmt-sequence;statement|statementstatement

if-stmt|repeat-stmt|assign-stmt|read-stmt|write-stmtif-stmt

ifexpthenstmt-sequenceend|ifexpthenstmt-sequenceelsestmt-sequenceendrepeat-stmt

repeatstmt-sequenceuntilexpassign-stmtidentifier:=expread-stmt

readidentifierwrite-stmt

writeexpexpsimple-expcomparison-opsimple-exp|simple-expcomparison-op

<|=simple-expsimple-expaddopterm|termaddop

+|-termtermmulopfactorfactor|factormulop*|/factor

(exp)|number|identifier4.2.7.1Acontext-freegrammarforTINY4/6/202371●TINY基本結(jié)構(gòu)類型：4.2.7.2SyntaxtreestructurefortheTINYcompilerif-statements if語句repeat-statements repeat語句assign-statements assign語句read-statements read語句write-statements write語句operator-expressions 算符表達(dá)式constant-expressions 常量表達(dá)式identifier-expression 標(biāo)識(shí)符表達(dá)式statements語句Expressions表達(dá)式4/6/202372●語法樹結(jié)構(gòu)的圖形描述矩形：表示語句節(jié)點(diǎn)；圓形和橢圓：表示表達(dá)式節(jié)點(diǎn)；三角形：表示額外的非指定的樹結(jié)構(gòu)。語句序列：if語句：iftestelsepartthenpart4/6/202373●語法樹結(jié)構(gòu)的圖形描述repeat語句：repeattestbodyAssign(name)expressionassign語句：write語句：writeexpressionop語句：op(opkind)RightoperandLeftoperand4/6/202374typedefenum{StmtK,ExpK}NodeKind;typedefenum{IfK,RepeatK,AssignK,ReadK,WriteK}StmtKind;typedefenum{OpK,ConstK,IdK}BxpKind;

/*ExpTypeisusedfortypechecking*/typedefenum{Void,Integer,Boolean}ExpType;

●CdeclarationsforaTINYsyntaxtreenode4/6/202375#defineMAXCHILDREN3typedefstructtreeNode{structtreeNode*child[MAXCHILDREN];structtreeNode*sibling;intlineno;NodeKindnodekind;union{StmtKindstmt;ExpKindexp;}kind;union{TokenTypeop;intval;char*name;}attr;ExpTypetype;/*fortypecheckingofexps*/}TreeNode;4/6/2023764.3Top-DownParsing自頂向下的分析4.3.1TOP-DOWNPARSINGBYRECURSIVE-DESCENT使用遞歸下降分析算法進(jìn)行自頂向下的分析4.3.2LL(1)PARSINGLL(1)分析4.3.3FIRSTANDFOLLOWSETSFIRST集合和FOLLOW集合4/6/202377●Parsing語法分析方法Recursive-descentparsing遞歸下降法LL(1)parsingLL(1)分析法Backtrackingparsers回溯分析方法Predictiveparsers預(yù)測(cè)分析方法LR(0)parsingSLR(1)parsingLR(1)parsingLALR(1)parsingTop-downParsing自頂向下分析方法若Z=>*S,則SL(G[Z])否則SL(G[Z])

G[Z]Bottom-upParsing自底向上分析方法若Z*<=S,則SL(G[Z])否則SL(G[Z])

G[Z]4/6/2023784.3.1Top-downParsingbyRecursive-descent

使用遞歸下降分析算法進(jìn)行自頂向下的分析●TheideaofRecursive-DescentParsing遞歸下降法：將一個(gè)非終結(jié)符A的文法規(guī)則看作將識(shí)別A的一個(gè)過程的定義。A的文法規(guī)則的右部指出此過程的代碼結(jié)構(gòu)。4/6/202379expr→expraddopterm∣termaddop→+∣-term→termmulopfactor∣factormulop→*factor→(expr)∣number●exampleProcedurefactorBEGINCasetokenof(:match(();expr;match());number:match(number);elseerror;endcase;ENDfactorProcedurematch(expectedToken);BeginIftoken=expectedTokenthenGetToken;ElseError;Endif;Endmatch已知表達(dá)式文法，及factor的文法規(guī)則，使用遞歸下降法識(shí)別factor。4/6/2023804.3.2LL(1)PARSINGLL(1)分析●MainideaLL(1)Parsingusesanexplicitstackratherthanrecursivecallstoperformaparse.LL(1)分析使用顯式棧而不是遞歸調(diào)用來完成分析。●example已知G:S→(S)S∣ε,請(qǐng)