关闭

关闭

封号提示

内容

首页 第四章 语法分析(2).ppt

第四章 语法分析(2).ppt

第四章 语法分析(2).ppt

上传者: arile0212 2012-03-30 评分 5 0 145 20 658 暂无简介 简介 举报

简介:本文档为《第四章 语法分析(2)ppt》,可适用于高等教育领域,主题内容包含第四章语法分析()*第四章语法分析()自顶向下语法分析自顶向下语法分析*自顶向下语法分析自顶向下(topdown)的语法分析算法是通过最左推导来分析符等。

第四章语法分析()*第四章语法分析()自顶向下语法分析自顶向下语法分析*自顶向下语法分析自顶向下(topdown)的语法分析算法是通过最左推导来分析输入的单词序列(tokens)自顶向下的分析算法有两类递归下降分析(recursivedescentparsing)LL()分析(LL()parsing)例idid*id的语法分析树构造过程*例idid*id的语法分析树构造过程对应文法ETEETE|TFTT*FT|F(E)|id**递归下降语法分析的一般方法*递归下降语法分析的一般方法为输入tokens寻找最左推导。递归下降分析的基本方法将一个非终结符A的文法规则看作识别A的过程的定义。A的文法规则的右部指示过程的代码结构匹配文法规则中出现的终结符a:match(a)调用文法规则中出现的非终结符非终结符对应的典型过程*非终结符对应的典型过程例文法*考虑文法ScAdAab|a为输入串w=cad建立分析树。例文法缺点*缺点不能处理左递归复杂的回溯技术回溯导致语义工作推倒重来难以报告出错的确切位置效率低预测语法分析器(PredictiveParsing)*预测语法分析器(PredictiveParsing)通过改写文法消除左递归提取左因子也许可以得到不带回溯的递归下降分析器。对A||…|n通过观测候选式所推导出的第一个符号能够选择合适的产生式来扩展例:stmtifexprthenstmtelsestmt|whileexprdostmt|beginstmtlistend非递归的预测分析*非递归的预测分析可以使用显式的栈而不是递归调用来完成分析。成功的自顶向下的分析的一般示意法:*成功的自顶向下的分析的一般示意法:两个基本动作:利用文法选择A将栈顶部的非终结符A替换成串。将栈顶的记号和下一个输入记号匹配。分析栈输入动作$StartSymbolInputString$…………$$接受例:生成配对括号的文法S(S)S|*例:生成配对括号的文法S(S)S|对串()下表给出自顶向下的分析程序的动作:分析栈输入动作$S()$S(S)S$S)S(()$匹配$S)S)$S$S))$匹配$S$S$$接受自顶向下的分析程序的动作*算法非递归预测分析方法*输入:输入符号串w和文法G的分析表M输出:若wL(G)则输出w的最左推导否则报告出错信息。方法:初始状态:$在栈底S在栈顶w$在输入缓冲区中。预测分析程序利用预测分析表M对于输入作出分析。算法非递归预测分析方法*Setiptopointtothefirstsymbolofw$repeatletXbethetopstacksymbolandathesymbolpointedtobyipifXisterminalor$thenifX=athenpopXfromthestackandadvanceipelseerror()else*Xisanonterminal*ifMX,a=XYY…YkthenbeginpopXfromstackpushYk,Yk,…,Yontostack,withYontopoutputtheproductionXYY…Ykendelseerror()untilX=$*stackisempty*InputpointerMayalsoexecuteothercodebasedontheproductionused*置ip指向w$的第一个符号repeat令X是栈顶符号,a是ip所指向的符号ifX是一个终结符号或$thenifX=athen从栈中弹出Xip指向下一个符号elseerror()else*X是非终结符号*ifMX,a=XYYYkthenbegin从栈中弹出X将Yk,Yk,,Y压入栈中即Y在栈顶输出产生式XYYYkendelseerror()untilX=$*栈为空*图预测分析程序例图文法的分析表M*例图文法的分析表MNonterminalETEETE|TFTT*FT|F(E)|id图预测分析器在输入idid*id上的动作*图预测分析器在输入idid*id上的动作$E$E’T$E’T’F$E’T’id$E’T’$E’$E’T$E’Tidid*id$idid*id$idid*id$idid*id$id*id$id*id$id*id$id*id$ETE’TFT’FidT’E’TE’STACKINPUTOUTPUT图预测分析器在输入idid*id上的动作(续)*图预测分析器在输入idid*id上的动作(续)STACKINPUTOUTPUT$E’T’F$E’T’id$E’T’$E’T’F*$E’T’F$E’T’id$E’T’$E’$id*id$id*id$*id$*id$id$id$$$$TFT’FidT’*FT’FidT’E’LeftmostDerivationfortheExample*LeftmostDerivationfortheExampleETE’FT’E’idT’E’idE’idTE’idFT’E’ididT’E’idid*FT’E’idid*idT’E’idid*idE’idid*id已经扫描过的输入符号加上栈中的文法符号(fromtoptobottom)构成该推导的左句型。HowtoconstructtheParsingTableM*HowtoconstructtheParsingTableMst:CalculateFirstFollowforGrammarnd:ApplyConstructionAlgorithmforParsingTableFIRST和FOLLOW函数*FIRST和FOLLOW函数对文法加什么样的限制可以保证没有回溯?先定义两个和文法有关的函数FIRST()FOLLOW(A)FIRST()*FIRST()FIRST()是从推导出的串的起始终结符的集合。FIRST()={a|*a…,aVT}特别是*时规定FIRST()对A的任何两个不同的选择i和j希望有FIRST(i)FIRST(j)=但有一个前提FIRST(i)和FIRST(j)都不含FOLLOW(A)*FOLLOW(A)FOLLOW(A)是在所有句型中紧跟在A后面的终结符集合。FOLLOW(A)={a|S*…Aa…aVT}S*Aa约定:如果A是某个句型的最右符号(S*A)那么$属于FOLLOW(A)计算FIRST(X)*计算FIRST(X)若XVT则FIRST(X)={X}。若X则将加入FIRST(X)。若XVN且XYY…Yk则将FIRST(Y)加入FIRST(X)若Y*将FIRST(Y)加入FIRST(X)若Y*将FIRST(Y)加入FIRST(X)……若Yk*将FIRST(Yk)加入FIRST(X)若对所有的j=,,…,k,Yj*将加入FIRST(X)计算FOLLOW(A)*计算FOLLOW(A)给定一个非终结符号A则集合FOLLOW(A)由终结符号或$组成定义如下:若A是文法开始符号则$在FOLLOW(A)中若存在产生式AB则FIRST(){}在Follow(B)中若存在产生式AB或AB且*则FOLLOW(B)包括FOLLOW(A)。(若AB则所有包含A的串中A可以被B代替)*注意:$标记输入结束。永远也不是FOLLOW集合中的元素。FOLLOW仅针对非终结符定义。例 已知文法产生式:*例 已知文法产生式:SiEtSS’|aS’eS|EbFIRST(S)={i,a}FIRST(S’)={e,}FIRST(E)={b}FOLLOW(S)包含$SiEtSS’将FIRST(S’)–{}即{e}加入FOLLOW(S)S’eS将FOLLOW(S’)加入FOLLOW(S)SiEtSS’将FOLLOW(S)加入FOLLOW(S’)因此有FOLLOW(S’)=FOLLOW(S)={e,$}FOLLOW(E)={t}例计算FIRST集和FOLLOW集*ETEETE|TFTT*FT|F(E)|id例计算FIRST集和FOLLOW集FIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}FOLLOW(T)=FOLLOW(T)={,),$}FOLLOW(F)={,*,),$}预测分析表的构造*预测分析表的构造算法预测分析表的构造输入:文法G输出:分析表M方法:()对文法的每个产生式A执行()和()。()对FIRST()的每个终结符a把A加入MA,a。()如果在FIRST()中对FOLLOW(A)的每个终结符b(包括$)把A加入MA,b。()M的其它没有定义的条目都是error。例*例FIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}FOLLOW(T)=FOLLOW(T)={,),$}FOLLOW(F)={,*,),$}ETEETE|TFTT*FT|F(E)|idLL()文法*LL()文法L:ScaninputfromLefttoRightL:ConstructaLeftmostDerivation:Use“”inputsymbolaslookaheadinconjunctionwithstacktodecideontheparsingaction分析表中没有多重定义的表目的文法称为LL()文法。例多重定义的条目*例多重定义的条目SiEtSS|aSeS|EbFIRST(S)={i,a}FIRST(S)={e,}FIRST(E)={b}FOLLOW(S)=FOLLOW(S)={e,$}FOLLOW(E)={t}*该文法是具有二义性的:遇到e(else)时不知该选择哪个产生式。消除二义性可以只选择SeS遵循与e最近的t(then)配对的原则LL()文法*LL()文法LL()文法中的任何两个产生式A|都满足下列条件:FIRST()FIRST()=不存在终结符a使得和导出的串都以a开始。若*那么FIRST()FOLLOW(A)=和至多一个能导出空串如果导出空串那么不能导出以FOLLOW(A)中终结符开始的任何串。LL()文法*LL()文法LL()文法具有的特殊性质没有公共左因子不是二义的不含左递归出错恢复(ErrorRecovery)*出错恢复(ErrorRecovery)词法错误如标识符、关键字或算符的拼写错语法错误如算术表达式的括号不配对语义错误如算符作用于不相容的运算对象逻辑错误如无穷的递归调用分析器对错误处理的基本目标*分析器对错误处理的基本目标清楚而准确地报告错误的出现迅速地从每个错误中恢复过来以便诊断后面的错误并尽量少出现伪错误不应该使正确程序的处理速度降低太多非递归预测分析在什么场合下发现错误*栈顶的终结符和下一个输入符号不匹配栈顶是非终结符A输入符号是a而MA,a是空白–Noallowableactions非递归预测分析在什么场合下发现错误PanicModeRecovery(应急方式)*PanicModeRecovery(应急方式)非递归预测分析采用紧急方式的错误恢复发现错误时分析器抛弃一些输入记号直到输入记号属于某个指定的同步记号集合为止。选择同步记号集合的启发式方法*选择同步记号集合的启发式方法把FOLLOW(A)的所有终结符放入非终结符A的同步记号集合中。ifexprthen(then是expr的一个同步记号)选择同步记号集合的启发式方法*选择同步记号集合的启发式方法把高层结构的开始符号加到低层结构的同步记号集合中。assignstmt:=exprif…(赋值语句的开始符号作为表达式的同步符号以免遗漏分号时忽略一大段程序。)选择同步记号集合的启发式方法*选择同步记号集合的启发式方法把FIRST(A)的终结符加入A的同步记号集合。如果A*可以将产生空串的产生式作为默认选择如果栈顶的终结符不能被匹配弹出该记号相当于所有其它记号都在同步记号集合中。RevisedParsingTableExample*RevisedParsingTableExamplesynchFromFollowsetsPopstackentry–TorNTSkipinputsymbol习题*习题PP

精彩专题

职业精品

上传我的资料

热门资料

资料评价:

/ 46
所需积分:2 立即下载

意见
反馈

返回
顶部

Q