语法分析专题培训市公开课金奖市赛课一等奖课件.pptx

第三章第三章语法分析语法分析本章内容本章内容上下文无关文法上下文无关文法自上而下自上而下分析和自下而上分析分析和自下而上分析围绕分析器自动生成展开围绕分析器自动生成展开词词法法分析器分析器记记号号取下一个取下一个记号记号源程序源程序分析分析树树前端前端其余部分其余部分分析器分析器中间中间表示表示符号表符号表第1页第1页3.1上下文无关文法上下文无关文法3.1.1上下文无关文法定义上下文无关文法定义正规式能定义一些简朴语言正规式能定义一些简朴语言，能表示给定结构固能表示给定结构固定次数重复或者没有指定次数重复定次数重复或者没有指定次数重复例：例：a(ba)5,a(ba)*正规式不能用于描述配对或嵌套结构正规式不能用于描述配对或嵌套结构例例1：配对括号串集合配对括号串集合例例2：wcw|w是是a和和b串串 第2页第2页3.1上下文无关文法上下文无关文法上下文无关文法上下文无关文法是四元组（是四元组（VT,VN,S,P）VT:终止符终止符集合集合VN:非非终止符终止符集合集合S:开始符号，非终止符中一个开始符号，非终止符中一个P :产生式产生式集合，集合，产生式形式产生式形式:A 例例 (id,+,(,),expr,op,expr,P)exprexpropexpr expr(expr)expr expr expridop+op 第3页第3页3.1上下文无关文法上下文无关文法简化表示简化表示exprexpropexpr|(expr)|expr|idop+|简化表示简化表示E E A E|(E)|E|idA+|第4页第4页3.1上下文无关文法上下文无关文法3.1.2 推导推导 把产生式当作重写规则，把符号串中非终止符用把产生式当作重写规则，把符号串中非终止符用其产生式右部串来代替其产生式右部串来代替例例 E E+E|E E|(E)|E|id E E (E)(E+E)(id+E)(id+id)概念概念上下文无关语言上下文无关语言、等价等价文法、文法、句型句型记号记号S*、S+w 第5页第5页3.1上下文无关文法上下文无关文法例例E E+E|E E|(E)|E|id 最左最左推导推导E lm E lm(E)lm(E+E)lm(id+E)lm (id+id)最右最右推导（规范推导）推导（规范推导）E rm E rm(E)rm(E+E)rm(E+id)rm (id+id)第6页第6页3.1上下文无关文法上下文无关文法3.1.3分析树分析树例例E E+E|E E|(E)|E|idEE()EEE+idid第7页第7页3.1上下文无关文法上下文无关文法3.1.4 二义性E E E E E+E id E E E+E id E+E id E+E id id+E id id+E id id+id id id+id两个不同最左推导第8页第8页3.1上下文无关文法上下文无关文法3.1.4 二义性E E E E E+E id E E E+E id E+E id E+E id id+E id id+E id id+id id id+id两棵不同语法树EEE*+EEidididEEidE*+EEidid第9页第9页3.2 语言和文法语言和文法 文法长处文法长处文法给出了准确，易于理解语法阐明文法给出了准确，易于理解语法阐明自动产生高效分析器自动产生高效分析器能够给语言定义出层次结构能够给语言定义出层次结构以文法为基础语言实现以文法为基础语言实现便于语言修改便于语言修改文法问题文法问题文法只能描述编程语言大部分语法，不能描述语文法只能描述编程语言大部分语法，不能描述语言中上下文相关语法特性言中上下文相关语法特性第10页第10页3.2 语言和文法语言和文法 3.2.1 正规式和上下文无关文法比较正规式和上下文无关文法比较正规式正规式(a|b)*ab文法文法A0aA0|b A0|aA1A1bA2A2 12开始开始a0abb第11页第11页3.2 语言和文法语言和文法 3.2.2分离词法分析器理由分离词法分析器理由为何要用正规式定义词法为何要用正规式定义词法词法规则非常简朴，不必用上下文无关文法词法规则非常简朴，不必用上下文无关文法对于词法记号，正规式描述简练且易于理解对于词法记号，正规式描述简练且易于理解从正规式结构出词法分析器效率高从正规式结构出词法分析器效率高第12页第12页3.2 语言和文法语言和文法 从软件工程角度看，词法分析和语法分析分从软件工程角度看，词法分析和语法分析分离有下列好处离有下列好处简化设计简化设计编译器效率会改进编译器效率会改进编译器可移植性加强编译器可移植性加强便于编译器前端模块划分便于编译器前端模块划分 第13页第13页3.2 语言和文法语言和文法 能否把词法分析并入到语法分析中，直接从能否把词法分析并入到语法分析中，直接从字符流进行语法分析字符流进行语法分析若把词法分析和语法分析合在一起，则必须将语若把词法分析和语法分析合在一起，则必须将语言注解和空白规则反应在文法中，文法将大大复言注解和空白规则反应在文法中，文法将大大复杂杂注解和空白由自己来处理分析器，比注解和空格注解和空白由自己来处理分析器，比注解和空格已由词法分析器删除分析器要复杂得多已由词法分析器删除分析器要复杂得多第14页第14页3.2 语言和文法语言和文法 3.2.3 验证文法产生语言验证文法产生语言G:S(S)S|L(G)=配正确括号串集合配正确括号串集合第15页第15页3.2 语言和文法语言和文法 3.2.3 验证文法产生语言验证文法产生语言G:S(S)S|L(G)=配正确括号串集合配正确括号串集合按推导步数进行归纳按推导步数进行归纳：推出是：推出是配对括号串配对括号串归纳基归纳基础：础：S 归纳假设：归纳假设：少于少于n步推导都产生配正确括号串步推导都产生配正确括号串归纳环节：归纳环节：n步最左推导步最左推导下列：下列：S(S)S*(x)S*(x)y第16页第16页3.2 语言和文法语言和文法 3.2.3 验证文法产生语言验证文法产生语言G:S(S)S|L(G)=配正确括号串集合配正确括号串集合按串长进行归纳按串长进行归纳：配对括号串可由配对括号串可由S推出推出归纳基归纳基础：础：S 归纳假设：归纳假设：长度小于长度小于2n都能够从都能够从S推导出来推导出来归纳环节：归纳环节：考虑长度为考虑长度为2n(n 1)w=(x)yS(S)S*(x)S*(x)y第17页第17页3.2 语言和文法语言和文法 3.2.4适当表示式文法适当表示式文法用一个层次观点看待表示式用一个层次观点看待表示式id id(id+id)+id id+id第18页第18页3.2 语言和文法语言和文法 3.2.4适当表示式文法适当表示式文法用一个层次观点看待表示式用一个层次观点看待表示式id id(id+id)+id id+idid id(id+id)文法文法exprexpr+term|termterm term factor|factorfactorid|(expr)第19页第19页3.2 语言和文法语言和文法 exprexpr+term|termtermterm factor|factorfactorid|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+id id分析树分析树 id id id分析树分析树 第20页第20页3.2 语言和文法语言和文法 3.2.5消除二义性消除二义性stmtifexprthenstmt|ifexprthenstmtelsestmt|other句型句型：ifexprthenifexprthenstmtelsestmt两个最左推导：两个最左推导：stmt ifexprthenstmt ifexprthenifexprthenstmtelsestmtstmt ifexprthenstmtelsestmt ifexprthenifexprthenstmtelsestmt第21页第21页3.2 语言和文法语言和文法 无二义文法无二义文法stmtmatched_stmt|unmatched_stmtmatched_stmtifexprthenmatched_stmtelsematched_stmt|otherunmatched_stmtif exprthenstmt|ifexprthenmatched_stmtelseunmatched_stmt第22页第22页3.2 语言和文法语言和文法 3.2.6消除左递归消除左递归文法文法左递归左递归A+A 直接左递归直接左递归AA|串特点串特点.消除直接左递归消除直接左递归A A A A|第23页第23页3.2 语言和文法语言和文法 例例算术表示文法算术表示文法EE+T|T（T+T.+T）TT F|F（F F.F）F(E)|id消除左递归后文法消除左递归后文法 ETE E+TE|TFT T F T|F(E)|id第24页第24页3.2 语言和文法语言和文法 非直接左递归非直接左递归SAa|bASd|先变换成直接左递归先变换成直接左递归S Aa|bAAad|bd|再消除左递归再消除左递归S Aa|bA bd A|A A adA|第25页第25页3.2 语言和文法语言和文法 3.2.7 提左因子提左因子有左因子文法有左因子文法A1|2提左因子提左因子A A A 1|2 第26页第26页3.2 语言和文法语言和文法 例例 悬空悬空else文法文法 stmtifexprthenstmtelsestmt|ifexprthenstmt|other提左因子提左因子stmtifexprthenstmtoptional_else_part|otheroptional_else_part elsestmt|第27页第27页3.2 语言和文法语言和文法 3.2.8 非上下文无关语言结构非上下文无关语言结构L1=wcw|w属于属于(a|b)*标识符申明应先于其引用抽象标识符申明应先于其引用抽象L2=anbmcndm|n 0,m 0形参个数和实参个数应当相同抽象形参个数和实参个数应当相同抽象L3=anbncn|n 0早先排版描述一个现象抽象早先排版描述一个现象抽象begin：5个字母键，个字母键，5个回退键，个回退键，5个下划线键个下划线键第28页第28页3.2 语言和文法语言和文法 L1=wcwR|w(a|b)*S aSa|bSb|c L2=anbmcmdn|n 1,m 1SaSd|aAdA bAc|bcL2=anbncmdm|n 1，m 1S ABA aAb|abB cBd|cd第29页第29页3.2 语言和文法语言和文法 L3=anbn|n 1S aSb|abL3 是不能用正规式描述语言一个范例是不能用正规式描述语言一个范例 若存在接受若存在接受L3 DFAD，状态数为状态数为k个个设设D读完读完,a,aa,ak 分别到达状态分别到达状态s0,s1,sk至少有两个状态相同，比如是至少有两个状态相同，比如是si和和sj，则则ajbi属于属于L3 sifs0标识为标识为ai路径路径标识为标识为bi路径路径标识为标识为aj i路径路径第30页第30页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|1第31页第31页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|1短语文法短语文法第32页第32页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 能够例外能够例外短语文法短语文法第33页第33页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 能够例外能够例外短语文法、上下文相关文法短语文法、上下文相关文法第34页第34页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 能够例外能够例外2型文法：型文法：A，A VN,(VN VT)*短语文法、上下文相关文法短语文法、上下文相关文法第35页第35页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 能够例外能够例外2型文法：型文法：A，A VN,(VN VT)*短语文法、上下文相关文法、上下文无关文短语文法、上下文相关文法、上下文无关文法法第36页第36页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 能够例外能够例外2型文法：型文法：A，A VN,(VN VT)*3型文法：型文法：A aB或或A a，A,B VN,a VT短语文法、上下文相关文法、上下文无关文短语文法、上下文相关文法、上下文无关文法法第37页第37页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法：型文法：，,(VN VT)*,|11型文法：型文法：|，但但S 能够例外能够例外2型文法：型文法：A，A VN,(VN VT)*3型文法：型文法：A aB或或A a，A,B VN,a VT短语文法、上下文相关文法、上下文无关文短语文法、上下文相关文法、上下文无关文法、正规文法法、正规文法第38页第38页3.2 语言和文法语言和文法 例例 L3anbncn|n 1上下文相关文法上下文相关文法S aSBC S aBCCBBCaB abbB bbbC bccC ccanbncn推导过程下列：推导过程下列：S*an-1S(BC)n 1用用S aSBC n-1次次S+an(BC)n用用S aBC 1次次S+anBnCn用用CBBC互换相邻互换相邻CBS+anbBn 1Cn用用aBab1次次S+anbnCn用用bB bb n-1次次S+anbncCn-1用用bC bc 1次次S+anbncn用用cCcc n-1次次第39页第39页3.3 自上而下分析自上而下分析 3.3.1自上而下分析普通办法自上而下分析普通办法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SaCbSaCbcdSaCbc不能处理不能处理左递归左递归第40页第40页3.3 自上而下分析自上而下分析不能处理左递归例子不能处理左递归例子算术表示文法算术表示文法EE+T|TTT F|FF(E)|idEE+TE+TE+T 第41页第41页3.3 自上而下分析自上而下分析 3.3.1自上而下分析普通办法自上而下分析普通办法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂回溯技术复杂回溯技术第42页第42页3.3 自上而下分析自上而下分析 3.3.1自上而下分析普通办法自上而下分析普通办法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂回溯技术复杂回溯技术、回溯造成回溯造成语义工作推倒重来语义工作推倒重来第43页第43页3.3 自上而下分析自上而下分析 3.3.1自上而下分析普通办法自上而下分析普通办法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂回溯技术复杂回溯技术、回溯造成回溯造成语义工作推倒重来语义工作推倒重来、难以汇报犯错确实切位难以汇报犯错确实切位置置第44页第44页3.3 自上而下分析自上而下分析 3.3.1自上而下分析普通办法自上而下分析普通办法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂回溯技术复杂回溯技术、回溯造成回溯造成语义工作推倒重来语义工作推倒重来、难以汇报犯错确实切位难以汇报犯错确实切位置置、效率低效率低第45页第45页3.3 自上而下分析自上而下分析 3.3.2 LL(1)文法 对文法加什么样限制能够确保没有回溯？先定义两个和文法相关函数FIRST()=a|*a,a VT 尤其是，*时，要求 FIRST()对A任何两个不同选择i 和j，希望有FIRST(i)FIRST(j)=若FIRST(i)或 FIRST(j)含，还需增加条件第46页第46页3.3 自上而下分析自上而下分析 3.3.2LL(1)文法文法对文法加什么样限制能够确保没有对文法加什么样限制能够确保没有回溯回溯？先定义两个和文法相关函数先定义两个和文法相关函数FIRST()=a|*a,a VT尤其是，尤其是，*时，要求时，要求 FIRST()FOLLOW(A)=a|S*Aa，a VT假假 如如 A是是 某某 个个 句句 型型 最最 右右 符符 号号，那那 么么$属属 于于FOLLOW(A)第47页第47页3.3 自上而下分析自上而下分析 LL(1)文法文法任何两个产生式任何两个产生式A|都满足下列条件：都满足下列条件：FIRST()FIRST()=若若 *，那么，那么FIRST()FOLLOW(A)=比如比如,对于下面文法，面临对于下面文法，面临a时，第时，第2步推导不步推导不知用哪个产生式知用哪个产生式S ABAa b|a FIRST(ab)FOLLOW(A)Ba CC 第48页第48页3.3 自上而下分析自上而下分析 LL(1)文法文法任何两个产生式任何两个产生式A|都满足下列条件：都满足下列条件：FIRST()FIRST()=若若 *，那么，那么FIRST()FOLLOW(A)=LL(1)文法有一些明显性质文法有一些明显性质没有公共左因子没有公共左因子不是二义不是二义不含左递归不含左递归第49页第49页3.3 自上而下分析自上而下分析 例例 ETE E +TE|TFT T FT|F(E)|idFIRST(E)=FIRST(T)=FIRST(F)=(,idFIRST(E )=+,FRIST(T )=,FOLLOW(E)=FOLLOW(E )=),$FOLLOW(T)=FOLLOW(T )=+,),$FOLLOW(F)=+,),$第50页第50页3.3 自上而下分析自上而下分析 3.3.3递归下降预测分析递归下降预测分析为每一个非终止符写一个分析过程为每一个非终止符写一个分析过程这些过程也许是递归这些过程也许是递归例例type simple|id|arraysimpleoftypesimple integer|char|numdotdotnum第51页第51页3.3 自上而下分析自上而下分析 一个辅助过程一个辅助过程voidmatch(terminalt)if(lookahead=t)lookahead=nextToken();elseerror();第52页第52页3.3 自上而下分析自上而下分析 voidtype()if(lookahead=integer)|(lookahead=char)|(lookahead=num)simple();else if(lookahead=)match();match(id);elseif(lookahead=array)match(array);match();simple();match();match(of);type();elseerror();type simple|id|arraysimpleoftype第53页第53页3.3 自上而下分析自上而下分析 voidsimple()if(lookahead=integer)match(integer);elseif(lookahead=char)match(char);elseif(lookahead=num)match(num);match(dotdot);match(num);elseerror();simple integer|char|numdotdotnum第54页第54页3.3 自上而下分析自上而下分析3.3.4非递归预测分析非递归预测分析a+b$输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈第55页第55页3.3 自上而下分析自上而下分析非终非终结符结符输输入入符符号号 id+.E ETE E E +TE TTFT T T T FT FFid分析表一部分分析表一部分第56页第56页3.3 自上而下分析自上而下分析栈栈输输入入 输输出出$E id id+id$预测预测分析器接受输入分析器接受输入id*id+id前一部分动作前一部分动作 第57页第57页3.3 自上而下分析自上而下分析栈栈输输入入 输输出出$E id id+id$E T id id+id$ETE 预测预测分析器接受输入分析器接受输入id*id+id前一部分动作前一部分动作 第58页第58页3.3 自上而下分析自上而下分析栈栈输输入入 输输出出$E id id+id$E T id id+id$ETE$E T F id id+id$TFT 预测预测分析器接受输入分析器接受输入id*id+id前一部分动作前一部分动作 第59页第59页3.3 自上而下分析自上而下分析栈栈输输入入 输输出出$E id id+id$E T id id+id$ETE$E T F id id+id$TFT$E T id id id+id$Fid 预测预测分析器接受输入分析器接受输入id*id+id前一部分动作前一部分动作 第60页第60页3.3 自上而下分析自上而下分析栈栈输输入入 输输出出$E id id+id$E T id id+id$ETE$E T F id id+id$TFT$E T id id id+id$Fid$E T id+id$预测预测分析器接受输入分析器接受输入id*id+id前一部分动作前一部分动作 第61页第61页3.3 自上而下分析自上而下分析栈栈输输入入 输输出出$E id id+id$E T id id+id$ETE$E T F id id+id$TFT$E T id id id+id$Fid$E T id+id$E T F id+id$T FT 预测预测分析器接受输入分析器接受输入id*id+id前一部分动作前一部分动作 第62页第62页3.3 自上而下分析自上而下分析栈栈输输入入 输输出出$E id id+id$E T id id+id$ETE$E T F id id+id$TFT$E T id id id+id$Fid$E T id+id$E T F id+id$T FT$E T F id+id$预测预测分析器接受输入分析器接受输入id*id+id前一部分动作前一部分动作 第63页第63页3.3 自上而下分析自上而下分析栈栈输输入入 输输出出$E id id+id$E T id id+id$ETE$E T F id id+id$TFT$E T id id id+id$Fid$E T id+id$E T F id+id$T FT$E T F id+id$E T id id+id$Fid 预测预测分析器接受输入分析器接受输入id*id+id前一部分动作前一部分动作 第64页第64页3.3 自上而下分析自上而下分析3.3.5结构预测分析表结构预测分析表（1）对文法每个产生式对文法每个产生式A ，执行执行(2)和和(3)（2）对）对FIRST()每个终止符每个终止符a，把把A 加入加入MA,a（3）假假如如 在在FIRST()中中，对对FOLLOW(A)每每个个终终止止符符b（包括包括$）,把把A 加入加入MA,b（4）M中中其它没有定义条目都是其它没有定义条目都是error第65页第65页3.3 自上而下分析自上而下分析非终非终结符结符 输输入入符符号号 other b else.stmt stmt other e_part e_partelsestmte_part expr expr b 多重定义条目多重定义条目第66页第66页3.3 自上而下分析自上而下分析非终非终结符结符 输输入入符符号号 other b else.stmt stmt other e_part e_partelsestmtexpr expr b 消去多重定义消去多重定义第67页第67页3.3 自上而下分析自上而下分析3.3.6 预测分析错误恢复预测分析错误恢复1、先对编译器错误处理做一个概述先对编译器错误处理做一个概述词法错误，如标识符、关键字或算符拼写错词法错误，如标识符、关键字或算符拼写错语法错误，如算术表示式括号不配对语法错误，如算术表示式括号不配对语义错误，如算符作用于不相容运算对象语义错误，如算符作用于不相容运算对象逻辑错误，如无穷递归调用逻辑错误，如无穷递归调用第68页第68页3.3 自上而下分析自上而下分析2、分析器对错误处理基本目标清楚而准确地汇报错误出现，并尽也许少出现伪错误快速地从每个错误中恢复过来，方便诊疗后面错误它不应该使正确程序处理速度降低太多 第69页第69页3.3 自上而下分析自上而下分析3、非递归预测分析在什么场合下发觉错误、非递归预测分析在什么场合下发觉错误栈顶终止符和下一个输入符号不匹配栈顶终止符和下一个输入符号不匹配a+b$输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈第70页第70页3.3 自上而下分析自上而下分析3、非递归预测分析在什么场合下发觉错误、非递归预测分析在什么场合下发觉错误栈顶是非终止符栈顶是非终止符A，输入符号是输入符号是a，而而MA,a是是空白空白a+b$输入输入预测分析程序预测分析程序分析表分析表M输出输出 XYZ$栈栈第71页第71页3.3 自上而下分析自上而下分析4、非递归预测分析：采取紧急方式错误恢复发觉错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定同时记号集合为止5、同时词法分析器当前提供记号流能够组成语法结构，正是语法分析器所盼望不同时例子语法分析器盼望剩下前缀组成过程调用语句，而实际剩下前缀形成赋值语句 第72页第72页3.3 自上而下分析自上而下分析6、同时记号集合选择、同时记号集合选择把把FOLLOW(A)所有终止符放入非终止符所有终止符放入非终止符A同时同时记号集合记号集合第73页第73页3.3 自上而下分析自上而下分析6、同时记号集合选择、同时记号集合选择把把FOLLOW(A)所有终止符放入非终止符所有终止符放入非终止符A同时同时记号集合记号集合ifexpr thenstmt（then和分号等记号是和分号等记号是expr同时记号）同时记号）第74页第74页3.3 自上而下分析自上而下分析6、同时记号集合选择、同时记号集合选择把把FOLLOW(A)所有终止符放入非终止符所有终止符放入非终止符A同时同时记号集合记号集合把高层结构开始符号加到低层结构同时记号集合把高层结构开始符号加到低层结构同时记号集合中中第75页第75页3.3 自上而下分析自上而下分析6、同时记号集合选择、同时记号集合选择把把FOLLOW(A)所有终止符放入非终止符所有终止符放入非终止符A同时同时记号集合记号集合把高层结构开始符号加到低层结构同时记号集合把高层结构开始符号加到低层结构同时记号集合中中a=expr;if(语句开始符号作为表示式同时记号，以免表示式语句开始符号作为表示式同时记号，以免表示式犯错又漏掉分号时忽略犯错又漏掉分号时忽略if语句等一大段程序语句等一大段程序)第76页第76页3.3 自上而下分析自上而下分析6、同时记号集合选择、同时记号集合选择把把FOLLOW(A)所有终止符放入非终止符所有终止符放入非终止符A同时同时记号集合记号集合把高层结构开始符号加到低层结构同时记号集合把高层结构开始符号加到低层结构同时记号集合中中把把FIRST(A)终止符加入终止符加入A同时记号集合同时记号集合a=expr;,if（语句开始符号作为语句同时符号，以免多出一个语句开始符号作为语句同时符号，以免多出一个逗号时会把逗号时会把if语句忽略了）语句忽略了）第77页第77页3.3 自上而下分析自上而下分析6、同时记号集合选择、同时记号集合选择把把FOLLOW(A)所有终止符放入非终止符所有终止符放入非终止符A同时同时记号集合记号集合把高层结构开始符号加到低层结构同时记号集合把高层结构开始符号加到低层结构同时记号集合中中把把FIRST(A)终止符加入终止符加入A同时记号集合同时记号集合假如非终止符能够产生空串，若犯错时栈顶是这假如非终止符能够产生空串，若犯错时栈顶是这样非终止符，则能够使用推出空串产生式样非终止符，则能够使用推出空串产生式第78页第78页3.3 自上而下分析自上而下分析非终非终结符结符 输输入入符符号号 id+.EETE E E+TE TTFT T 犯错T T FT .例例 栈顶为栈顶为T ，面临，面临id时犯错时犯错第79页第79页3.3 自上而下分析自上而下分析非终非终结符结符 输输入入符符号号 id+.EETE E E+TE TTFT T 犯错，用T T T FT .T 能够产生空串，报错并用能够产生空串，报错并用T 第80页第80页3.3 自上而下分析自上而下分析同时记号集合选择同时记号集合选择把把FOLLOW(A)所有终止符放入非终止符所有终止符放入非终止符A同时同时记号集合记号集合把高层结构开始符号加到低层结构同时记号集合把高层结构开始符号加到低层结构同时记号集合中中把把FIRST(A)终止符加入终止符加入A同时记号集合同时记号集合假如非终止符能够产生空串，若犯错时栈顶是这假如非终止符能够产生空串，若犯错时栈顶是这样非终止符，则能够使用推出空串产生式样非终止符，则能够使用推出空串产生式假如终止符在栈顶而不能匹配，弹出此终止符假如终止符在栈顶而不能匹配，弹出此终止符 第81页第81页3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB d 第82页第82页3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcde（读入（读入ab）ab第83页第83页3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcde（归约）（归约）abA第84页第84页3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcde（再读入（再读入bc）abAbc第85页第85页3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcdeaAde（归约）（归约）abAbAc第86页第86页3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcdeaAde（再读入（再读入d）abAbdAc第87页第87页3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcdeaAdeaABe（归约）（归约）abAbdAcB第88页第88页3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcdeaAdeaABe(再读入再读入e)eabAbdAcB第89页第89页3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcdeaAdeaABeS（归约）（归约）SeabAbdAcB第90页第90页3.4 自下而上分析自下而上分析 3.4.1 归约归约例例 S aABeA Abc|bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm abbcdeSeabAbdAcB第91页第91页3.4 自下而上分析自下而上分析 3.4.2 句柄句柄句型句型句柄句柄是和某产生式右部匹配子串，并且，是和某产生式右部匹配子串，并且，把它归约成该产生式左部非终止符代表了最把它归约成该产生式左部非终止符代表了最右推导过程逆过程一步右推导过程逆过程一步S aABeA Abc|bB dS rm aABe rm aAde rm aAbcde rm abbcde句柄右边仅含终止符句柄右边仅含终止符假如文法二义，那么句柄也许不唯一假如文法二义，那么句柄也许不唯一第92页第92页3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E+E|E E|(E)|id第93页第93页3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E+E|E E|(E)|idE rm E Erm E E+Erm E E+id3rm E id2+id3 rm id1 id2+id3 第94页第94页3.4 自下而上分析自下而上分析 例例 句柄不唯一句柄不唯一E E+E|E E|(E)|idE rm E E E rm E+Erm E E+Erm E+id3rm E E+id3rm E E+id3rm E id2+id3 rm E id2+id3 rm id1 id2+id3 rm id1 id2+id3 在句型在句型E E+id3中，句柄不唯一中，句柄不唯一第95页第95页3.4 自下而上分析自下而上分析 3.4.3用栈实现移进用栈实现移进 归约分析归约分析先通过先通过移进移进 归约分析器在分析输入串归约分析器在分析输入串id1 id2+id3时时动作序列动作序列来理解移进来理解移进 归约分析工作方式归约分析工作方式第96页第96页3.4 自下而上分析自下而上分析 栈栈输输入入 动动作作$id1 id2+id3$第97页第97页3.4 自下而上分析自下而上分析 栈栈输输入入 动动作作$id1 id2+id3$移进移进 第98页第98页3.4 自下而上分析自下而上分析 栈栈输输入入 动动作作$id1 id2+id3$移进移进$id1 id2+id3$第99页第99页3.4 自下而上分析自下而上分析 栈栈输输入入 动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约 第100页第100页3.4 自下而上分析自下而上分析 栈栈输输入入 动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$第101页第101页3.4 自下而上分析自下而上分析 栈栈输输入入 动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进第102页第102页3.4 自下而上分析自下而上分析 栈栈输输入入 动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$第103页第103页3.4 自下而上分析自下而上分析 栈栈输输入入 动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进第104页第104页3.4 自下而上分析自下而上分析 栈栈输输入入 动动作作$id1 id2+id3$移进移进$id1 id2+id3$按按Eid归约归约$E id2+id3$移进移进$E id2+id3$移进移进$E id2+id3$第105页第105页3.4 自下而上分析自下而上分析 栈栈输输入入 动动作作$id1 id2