SyntaxAnalysis语法分析学习

SyntaxAnalysis语法分析Chapter4SyntaxAnalysis语法分析4.1

语法分析器的作用4.2

上下文无关文法

4.3

自顶向下语法分析4.4

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

语法分析器的作用词法分析源程序目标程序语法分析语义分析文字表、符号表处理错误处理中间代码优化中间代码生成前端后端●

Thephaseofacompiler编译程序的结构目标代码生成4/6/202334.1

语法分析器的作用语法分析器词法分析器记号流源程序前端其他部分分析树中间表示符号表管理器出错处理器parser分析程序sequenceoftokens记号序列(input)syntaxtree语法树(output)syntaxTree=parse();4/6/20234●源程序中可能出现的错误①词法错误如非法字符或拼写错关键字、标识符等； 如@intege20times②语法错误是指语法结构出错，如少分号、begin/end不配对等。 begin x:=a+b y:=x;4.1

语法分析器的作用4/6/20235●源程序中可能出现的错误①词法错误②语法错误③静态语义错误④动态语义错误（逻辑错误）4.1

语法分析器的作用如非法字符或拼写错关键字、标识符等；@ intege 20times是指语法结构出错，如少分号、begin/end不配对等。begin x:=a+b； y:=x;如无穷递归、变量为零时作除数等。while(t){...};a:=a/b;类型不一致、参数不匹配等；如a,b:integer;x:array[1..10]ofinteger;x:=a+b;4/6/20236●语法错误处理的目标

清楚而准确地报告错误的出现（地点正确、不漏报、不错报也不多报）；迅速地从每个错误中恢复过来（以便分析继续进行）；不应使对语法正确源程序的分析速度降低太多。4.1

语法分析器的作用4/6/202374.2Context-freegrammars上下文无关文法●Thesyntaxofaprogramminglanguageisusuallygivenbythegrammarrulesofacontext-freegrammar.程序设计语言的语法通常是由上下文无关文法规则给出。●Therulesofacontext-freegrammararerecursive.上下文无关文法的规则是递归的。4/6/202384.2.1上下文无关文法概述4.2.1.1Comparisontoregularexpressionnotation与正则表达式比较thecontext-freegrammar:number

number

digit|digit；digit0|1|2|3|……|9theregularexpression:number=digitdigit*digit=0|l|2|3|4|5l6|7|8|9*•|()=无不出现|含义变化(=,::=)thecontext-freegrammar:expexpopexp|(exp)|numberop+|–|*Backus-Naur范式(BNF文法)4/6/202394.2.2.1Specificationofcontext-freegrammarrules

上下文无关文法规则的说明●什么是文法？文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称“语法”）。例:请判断英语句子Thebigelephantatethepeanut.语法上是否正确？4/6/202310<句子><主语><谓语><主语><冠词><形容词><名词><冠词>the<形容词>big<名词>elephant|peanut<谓语><动词><宾语><动词>ate<宾语><冠词><名词>解：(1)已知语法规则(2)由规则推导句子推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。<句子>=><主语><谓语><主语><谓语>=><代词><谓语>……直到所有带<>的符号都由终结符号替代为止。4/6/202311<句子>=><主语><谓语>=><冠词><形容词><名词><谓语>=>the<形容词><名词><谓语>=>thebig<名词><谓语>=>thebigelephant<谓语>=>thebigelephant<动词><宾语>=>thebigelephantate<宾语>=>thebigelephantate<冠词><名词>=>thebigelephantatethe<名词>=>thebigelephantatethepeanut<句子>::=<主语><谓语><主语>::=<冠词><形容词><名词><冠词>::=the<形容词>::=big<名词>::=elephant|peanut<谓语>::=<动词><宾语><动词>::=ate<宾语>::=<冠词><名词>上述推导可写成<句子>=>thebigelephantatethepeanut+4/6/202312(1)有若干语法成分同时存在时，总是从最左的语法成分进行推导，这称之为最左推导，类似的有最右推导（一般推导）。(2)从一组规则可推出不同的句子，如以上规则还可推出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子，它们在语法上都正确，但在语义上都不正确。所谓文法是在形式上对句子结构的定义与描述，而未涉及语义问题。Note4/6/2023134.2.2.2Derivationsandthelanguagedefinedbyagrammar推导及由文法定义的语言1.相应的正则式：2.derivation推导例：根据文法，请判断程序(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}●文法定义的（产生的）语言exp：开始符号thestartsymbol=>*：星推导(=>+：正推导)s：句子expexpopexp|(exp)|numberop+|–|*exp：开始符号thestartsymbolexp

number：产生式Nonterminals(非终结符)Terminals(终结符)●文法4/6/202315●Example1)已知文法G：E(E)|a，请问文法定义的语言是什么？L(G)={a,(a),((a)),(((a))),…}={(na)n|naninteger>=0}2)已知文法G：E(E)，请问文法定义的语言是什么？空3)已知文法G：EE+a|a，请问文法定义的语言是什么？L(G)={a,a+a,a+a+a,a+a+a+a,...}4)已知正则式为a+，请问相应的文法及定义的语言是什么？G:AAa|aorAaA|aL(a*)={an|naninteger>=0}leftrecursiverightrecursive5)已知正则式为a*，请问相应的文法是什么？G:AAa|orAaA|Recursive递归Grammar文法AA|

A

A|

4/6/202316●Example6)已知文法定义的语言如下(C的嵌套if语句)，请写出该文法？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|，请问(()(()))()语法正确吗？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如下，请问文法定义的语言是什么？stmt-sequence

stmt;stmt-sequence|stmtstmtsL(G)={s,s;s,s;s;s,...)若例8中允许语句序列为空，即定义的语言为

L(G‘)={

,s;,s;s;,s;s;s;,...)，则相应的文法是什么？stmt-sequence

stmt;stmt-sequence|

stmt

s若例8中允许语句序列为空，但要求分号作为语句分隔符，即定义的语言为

L(G‘)={,s,s;s,s;s;s,...)，则相应的文法是什么？stmt-sequencenonempty-stmt-sequence|

nonempty-stmt-sequencestmt；nonempty-stmt-sequence|stmtstmts4/6/202319●Example若例8中允许语句序列为空，但要求分号作为语句结束符，

即定义的语言为

L(G‘)={

;,s;,;s;,s;s;,;s;s;,s;s;s;,...)，则相应的文法是什么？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推导最右推导最左推导4/6/2023211)推导(1)exp=>expopexp(2)=>numberopexp(3)=>number+exp(4)=>number+number(1)exp=>expopexp(2)=>expopnumber(3)=>exp+number

(4)=>number+number

●分析树(与推导相对应的作了标记的树)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推导numberexp*opexpexpnumber14exp()opexpexp-number235678numberexp*opexpexpnumber12exp()opexpexp-number8736544/6/2023231)表达式3+4的分析树：●Abstractsyntaxtrees抽象语法树(简称语法树)exp+opexpexpnumbernumber3 4+342)语法树：expOpExp(op,exp,exp)|ConstExp(integer)opPlus|Minus|Times3)

简单的算术表达式抽象语法树的文法:例1：简单表达式的抽象语法树解：4/6/202324typedefenum{Plus,Minus,Times}OpKind

typedefenum{OpK.ConstK}ExpKind;

typedefstructstreenode

{ExpKindkind;

OpKindop;structstreenode*lchild,*rchild;intval;}STreeNode;typedefSTreeNode*SyntaxTree;4)简单的算术表达式抽象语法树的存储结构：4/6/202325解：分析树例2：if语句的抽象语法树1)已知简化了的if语句的文法：statementif-stmt|otherif-stmtif(exp)statement|if(exp)statementelsestatementexp0|1请画出串if(0)otherelseother的语法树!if-stmtelseexpstatement0statementif()statementotherother4/6/202326解：分析树2)已知文法：statementif-stmt|otherif-stmtif(exp)statementelse-partelse-partelsestatement|exp0|1请画出串if(0)otherelseother的语法树!if-stmtelseexpstatement0statementif()statementotherotherelse-part4/6/2023273)if语句的抽象语法树：if0otherother4)if语句的存储表示：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：顺序结构的语句的抽象语法树1)已知顺序结构的语句的文法：

stmt-sequence

stmt;stmt-sequence|stmtstmts请画出串s;s;s的语法树!stmt-sequence;stmtstmt-sequences;stmtssstmt-sequencestmt4/6/2023292)顺序结构的语句的抽象语法树;ss;sseqsssseqsssseqssssss≌OR4/6/2023304.2.4Ambiguity二义性4.2.4.1AmbiguousGrammars二义性文法例：已知简单整型算术文法，exp

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

请画出串34-3*42的语法树!解：1)推导2)分析树3)语法树4/6/202331解：1)最左推导例：已知简单整型算术文法exp

expopexp|(exp)|numberop+|-|*请画出串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例：已知简单整型算术文法exp

expopexp|(exp)|numberop+|-|*请画出串34-3*42的分析树!*342-34-343*423)语法树●ambiguousgrammar二义性文法可生成两个不同分析树的串的文法叫二义性文法。●消除二义性规则◆不修改文法，指定正确的分析树(或语法树)；◆修改文法(优先级、结合性)4/6/2023334.2.4.2Precedenceandassociativity优先级和结合性●precedencecascade优先级联具有相同优先级的算符归纳在一组，并为每一种优先级规定不同的规则。例：将“乘法比加法和减法优先”添加到简单的算术表达式文法。expexpaddopexp|termaddop

+|-termtermmulopterm|factormulop

*factor(exp)|number4/6/202334●结合性例：将“乘法比加法和减法优先，并且左结合”添加到简单的算术表达式文法。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问题的最近嵌套规则

(消除二义性的规则)statement

matched-stmt|unmatched-stmtmatched-stmtif(exp)matched-stmtelsematched-stmt|otherunmatched-stmtif(exp)statement|if(exp)matched-stmtelseunmatched-stmtexp0|1最近嵌套规则matched-stmt：匹配的语句(不含不带else的if语句的语句)；unmatched-stmt：不匹配的语句(含不带else的if语句的语句)；4/6/202338

statement

if-stmt|otherif-stmt

if(exp)statement|if(exp)statementelsestatementexp0|1●消除二义性的规则方法2if-stmtifconditionthenstatement-sequenceendif

|ifconditionthenstatement-sequenceelse

statement-sequenceendif4/6/2023394.2.4.4Inessentialambuguity无关紧要二义性文法有二义性，但总生成唯一的抽象的语法树。例：如下文法是无关紧要二义性文法！stmt-sequence

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

扩展的表示法：EBNF和语法图●extendedBNF,orEBNF表示法1)递归(重复：{}表示)左递归：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

上下文无关语言的形式特性4.2.6.1Aformaldefinitionofcontext-freelanguage上下文无关文法的形式定义G=(T,N,P,S)

◆AsetTofterminals.（终结符集合T）◆AsetNofnonterminals(disjointfromT)

(非终极符集合N(与T不相交)）◆AsetPofproductions,orgrammarrules,oftheformAa,whereAisanelementofNandaisanelementof(TN)*(产生式或文法规则Aa集合P，其中A∈N,a∈(TN)*)◆AstartsymbolSfromthesetN(开始(识别)符号∈N)thesetofsymmbols(符号集)：TNT∩N＝ΦAa

，其中|A|=1

|a|>=0注：4/6/202343P={<无符号整数><数字串>；<数字串>

<数字串><数字>；<数字串><数字>；

<数字>

0；

<数字>

1；

…………

<数字>

9；}S=<无符号整数>；例：无符号整数的文法如下，可否化简？ G[<无符号整数>]=（N，T，P，S） N＝{<无符号整数>,<数字串>,<数字>} T={0,1,2,3,……9}4/6/202344●文法的简化方法：产生式左边符号构成集合N，且S∈N具有相同的左部的产生式，可以合在一起解：无符号整数的文法简化为：（产生式集合+开始符号）G[<无符号整数>]<无符号整数><数字串>；<数字串>

<数字串><数字>|<数字>；<数字>0|1|2|3|……|94/6/202345●文法G=(T,N,P,S)的相关术语G=(T,N,P,S)，其中v=aA，w=a

，A∈N

a,,∈(TN)*

若A

∈P，则aA

=>a

，即v=>w

称为v直接产生w(或w是v直接推导，或w直接规约到v)<无符号整数><数字串><数字串><数字><数字><数字>1<数字>10(6)=>=>(1)=>(3)(5)=>=>(2)例：已知文法G[<无符号整数>](1)<无符号整数><数字串>；(2)<数字串><数字串><数字>(3)<数字串><数字>根据文法G能否推导出10？(4)<数字>0;(5)<数字>1;…………(13)<数字>9;1)直接推导4/6/2023462）+推导G=(T,N,P,S)，a=a1，=an，其中a,

∈(TN)*

若a1

=>a2

a2

=>a3，…，an-1

=>an即a=>+称为a推导出(产生)(推导长度为n≥１)(或规约到a)例：<无符号整数>=><数字串>=><数字串><数字>=><数字><数字>=>1<数字>=>10即<无符号整数>=>+103）*推导G=(T,N,P,S)，a,

∈(TN)*

若a=>+，或a=

称为a推导出(产生)(推导长度为n≥０)(或规约到a)4/6/2023474）leftmostderivation最左推导G=(T,N,P,S)，S=>*w，每个推导步骤aA

=>a

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

称为S=>*w为最左推导。最左推导：若符号串中有两个以上的非终结符时，先推左边的。最右推导：若符号串中有两个以上的非终结符时，先推右边的。5）rightmostderivation最右推导（规范推导）G=(T,N,P,S)，S=>*w，每个推导步骤aA

=>a

，都有A∈N，a,

∈(TN)*，∈T*

称为S=>*w为最右推导。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）文法产生的语言L(G[S])G=(T,N,P,S)，L(G[S])={a|S=>*a，a∈T*}称L(G[S])为文法G产生的语言。4/6/2023499）短语、简单短语G=(T,N,P,S)，w=xuy∈(TN)*

为文法的句型,若S=>xUy,且U=>+u,则u是句型w相对于U的短语；若S=>xUy,

且U=>u,则u是句型w相对于U的简单短语;其中U∈N，u∈(TN)+,x,y∈(TN)*

10）句柄任一句型的最左简单短语称为该句型的句柄。

短语、简单短语是相对于句型而言，一个句型可能有多个短语、简单短语，句柄只能有一个。Note4/6/202350例：有文法G[E]：

ET|E+T|E-T

TF|T*F|T/F

Fi|(E)请判断(E+T)*i+F是G的一句型吗？如果是，请画出它的推导的分析树，并写出该树的短语、简单短语、句柄。●Example解：∵E=>*(E+T)*i+F∴(E+T)*i+F是G的一句型4/6/202351简单短语(每棵简单子树的叶组成简单短语):E+T是句型(E+T)*i+F相对于E的简单短语；i是句型(E+T)*i+F相对于F的简单短语；F是句型(E+T)*i+F相对于T的简单短语。短语(每棵子树的叶组成短语):(E+T)*i+F是句型(E+T)*i+F相对于E的短语；(E+T)*I是句型(E+T)*i+F相对于E、T的短语；(E+T)是句型(E+T)*i+F相对于T、F的短语；E+T是句型(E+T)*i+F相对于E的短语；i是句型(E+T)*i+F相对于F的短语；F是句型(E+T)*i+F相对于T的短语。句柄(最左简单子树的叶组成句柄):E+T是句型(E+T)*i+F相对于E的最左简单短语。4/6/20235211）文法G的分析树1.Eachnodeislabeledwithaterminaloranonterminalor.2.TherootnodeislabeledwiththestartsymbolS.3.Eachleafnodeislabeledwithaterminalorwith.4.Eachnonleafnodeislabeledwithanonterminal.5.IfanodewithlabelANhasnchildrenwithlabelsX1,X2,...,Xn(whichmaybeterminalsornonterminals),thenAX1X2...XnP(aproductionofthegrammar).每个分析树只有唯一的一个最左推导和一个最右推导。最左推导与分析树的前序编号相对应；最右推导与分析树的后序编号相对应Note4/6/2023534.2.6.2Thechomskyhierarchy乔姆斯基层次文法和语言分类：0型、1型、2型、3型（乔姆斯基层次）

0型文法称为短语结构文法（非限制）。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。0型语言：L0语言可以用图灵机(Turing)接受.●0型：P：uv其中u∈(TN)+

，v∈(TN)*

1型文法称为上下文敏感或上下文有关文法。也即只有在x,y这样的上下文中才能把U改写为u

；1型语言：L1语言可以由一种线性界限自动机接受.●1型：P：xUyxuy其中U∈N，x,y,u∈(TN)*4/6/202354

3型文法称为正则文法。它是对2型文法进行进一步限制。3型语言：L3又称正则语言(正则集合)可以由有穷自动机接受。●3型：(左线性)P：Ut或UWt其中U、W∈Nt∈T(右线性)P：Ut或UtW其中U、W∈Nt∈T

0型文法称为上下文无关文法。也即把U改写为v时，不必考虑上下文。

2型文法与BNF表示相等价。

2型语言：L2语言可以由下推自动机接受.●2型：P：Uv其中U∈N

，v∈(TN)*

4/6/202355●0型、1型、2型、3型比较产生式左部范围右部范围|左部||右部|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附：自动机、正则文法、正则表达式

的相互转化正则文法NFA正则表达式123456DFA最小化4/6/202357（1）有穷自动机正则文法1.对转换函数T(A,t)=B，可写成一个产生式:AtB算法:2.对可接受状态Z,增加一个产生式:Zε3.有穷自动机的初态对应于文法的开始符号,有穷自动机的字母表为文法的终结符号集。ABt4/6/202358例:求出如图NFA等价的正则文法G。ABCDstartaaabbbb1.对转换函数T(A,t)=B，可写成一个产生式:AtB2.对可接受状态Z,增加一个产生式:Z

ε3.有穷自动机的初态对应于文法的开始符号,有穷自动机的字母表为文法的终结符号集。G=({A,B,C,D},{a,b},P,A)其中P:AaBAbDBbCCaACbDCεDaBDbDDε解：4/6/202359（2）正则文法G有穷自动机M算法:1.字母表与G的终结符号相同.2.为G中的每个非终结符生成M的一个状态,G的开始符号S是开始状态S;3.增加一个新状态Z,作为NFA的终态4.对G中的形如AtB的产生式,其中t为终结符或ε,A和B为非终结符,构造M的一个转换函数f(A,t)=B5.对G中的形如At的产生式,构造M的一个转换函数f(A,t)=Z4/6/202360例:求与文法G[E]等价的NFAG[E]:EaA|bB|εAaB|bABaE|bA|εEZABstartaaabbbεε解：1.字母表与G的终结符号相同.2.为G中的每个非终结符生成M的一个状态,G的开始符号S是开始状态S;3.增加一个新状态Z,作为NFA的终态4.对G中的形如AtB的产生式,其中t为终结符或ε,A和B为非终结符,构造M的一个转换函数f(A,t)=B5.对G中的形如At的产生式,构造M的一个转换函数f(A,t)=Z4/6/202361（3）正则式有穷自动机1.(a)对于正则式φ,所构造NFA:xy(b)对于正则式ε,所构造NFA:xyε(c)对于正则式a,a∈Σ,则NFA:xya4/6/2023622.若s,t为Σ上的正则式,相应的NFA分别为N(s)和N(t);(a)对于正则式R=s|t,NFA(R)(b)对正则式R=st,NFA(R)N(s)N(t)εεεεxy或:N(s)xN(t)yxyN(s)N(t)εεε(c)对于正则式R=s*,NFA(R)(d)对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,第一个a,则有

23a解:例:为R=(a|b)*abb构造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）有穷自动机正则式例:M如下，求相应的正则表达式。解:(Ⅰ)加x,y(新的初态和终态)4/6/202366(Ⅱ)消除M中的所有结点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(新的初态和终态)4/6/202367利用以下转换规则,直至只剩下一个开始符号定义的产生式,并且产生式的右部不含非终结符.规则规则1规则2规则3文法产生式正则式AxB,ByAxA|yAx,AyA=xyA=x*yA=x|y（5）正则文法正则式例:有文法G[s]SaA|aA

aA|dA|a|d求相应的正则表达式解:A=>(aA|dA)|(a|d)

=>(a|d)A|(a|d)=>(a|d)*(a|d)代入规则1得：S=>a(a|d)*(a|d)|a∴S=a((a|d)*(a|d)|ε)4/6/202368算法:1)对任何正则式r,选择一个非终结符S作为识别符号.并产生产生式Sr2)若x,y是正则式,例:将R=a(a|d)*转换成相应的正则文法解:1)Sa(a|d)*2)SaAA(a|d)*S

aA

A(a|d)AAεS

aAA

aA|dAAε（6）正则式正则文法规则规则1规则2规则3文法产生式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基本结构类型：4.2.7.2SyntaxtreestructurefortheTINYcompilerif-statements if语句repeat-statements repeat语句assign-statements assign语句read-statements read语句write-statements write语句operator-expressions 算符表达式constant-expressions 常量表达式identifier-expression 标识符表达式statements语句Expressions表达式4/6/202372●语法树结构的图形描述矩形：表示语句节点；圆形和椭圆：表示表达式节点；三角形：表示额外的非指定的树结构。语句序列：if语句：iftestelsepartthenpart4/6/202373●语法树结构的图形描述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使用递归下降分析算法进行自顶向下的分析4.3.2LL(1)PARSINGLL(1)分析4.3.3FIRSTANDFOLLOWSETSFIRST集合和FOLLOW集合4/6/202377●Parsing语法分析方法Recursive-descentparsing递归下降法LL(1)parsingLL(1)分析法Backtrackingparsers回溯分析方法Predictiveparsers预测分析方法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

使用递归下降分析算法进行自顶向下的分析●TheideaofRecursive-DescentParsing递归下降法：将一个非终结符A的文法规则看作将识别A的一个过程的定义。A的文法规则的右部指出此过程的代码结构。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已知表达式文法，及factor的文法规则，使用递归下降法识别factor。4/6/2023804.3.2LL(1)PARSINGLL(1)分析●MainideaLL(1)Parsingusesanexplicitstackratherthanrecursivecallstoperformaparse.LL(1)分析使用显式栈而不是递归调用来完成分析。●example已知G:S→(S)S∣ε,请