关闭

关闭

封号提示

内容

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

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

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

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

简介:本文档为《第四章 语法分析(1)ppt》,可适用于高等教育领域,主题内容包含第四章语法分析第四章语法分析本章内容本章内容上下文无关文法自顶向下分析和自底向上分析LL文法和LR文法Yacc语法分析器的作用语法分析器的作用上下文符等。

第四章语法分析第四章语法分析本章内容本章内容上下文无关文法自顶向下分析和自底向上分析LL文法和LR文法Yacc语法分析器的作用语法分析器的作用上下文无关文法上下文无关文法RE的局限性正规式用于定义一些简单的语言能表示给定结构的固定次数的重复或者没有指定次数的重复。例:a(ba),a(ba)*正规式不能用于描述配对或嵌套的结构例:配对括号串的集合{wcw|w是a和b符号串}例如包含递归结构的条件语句不能用正规表达式说明可以用产生式表示:stmtifexprthenstmtelsestmt上下文无关文法的定义上下文无关文法的定义上下文无关文法是四元组(VT,VN,S,P)VT:终结符集合VN:非终结符集合S:开始符号P:产生式集合产生式形式为:AAVN,(VNVT)*例定义算术表达式的文法例定义算术表达式的文法exprexpropexprexpr(expr)exprexprexpridop||*||符号的使用约定符号的使用约定我们一般用大写字母表示非终结符小写字母表示终结符…Terminals:a,b,c,,,punc,,,…,,Blackstrings:id,ifNonTerminals:A,B,C,S,italicstrings文法符号:X,Y,Z终结符号串:u,v,…,zinVT*文法符号串:,in(VTVN)*符号的使用约定符号的使用约定Alternativesofproductionrules:AA…AkA||…|kFirstNTonLHSofstproductionruleisdesignatedasstartsymbol!例的文法改写为:例的文法改写为:EEAE|(E)|E|idA||*||推导推导把产生式看成重写规则用产生式右部的串来代替左部的非终结符。例:EEE|E*E|(E)|E|idEE(E)(EE)(idE)(idid)(idid)是文法的句子。推导的定义推导的定义定义:设有文法G=(VT,VN,S,P)称串A直接推导出如果AP且,(VTVN)*并记作A。直接归约到A。如果存在一个直接推导序列:n(n>),则称推导出n记作n(推导长度为n)。推导推导句型、句子、语言句型、句子、语言对开始符号为S的文法GwL(G)当且仅当称w为G的句子。对开始符号为S的文法G如果   则称为G的句型。句子是不含非终结符的句型。仅含终结符号的句型是一个句子。语言L(G)是由文法G产生的所有句子的集合:若文法G和文法G所产生的语言相同即L(G)=L(G)则称文法G和文法G等价。例:已知文法G=({a,b},{S},S,P)其中P:SaSbab例:已知文法G=({a,b},{S},S,P)其中P:SaSbabSaSbaaSbbaSb……anSbnanbn显然L(G)={anbnn}。最左推导最左推导最左推导:推导过程中任何一步推导都是对中的最左非终结符进行替换。如果是最左推导可以记为如果则称是文法的左句型。最右推导最右推导类似的可以定义最右推导:推导过程中任何一步推导都是对中的最右非终结符进行替换。最右推导也称作规范推导。归约(reduce)归约(reduce)定义:设和均为句型若*则称可以归约为。规范(最右)推导的逆过程称为规范归约。语法分析的核心问题就是对于一个终结符号串x设法从S推导出x或者反过来设法将x归约为S。分析树和推导分析树和推导分析树是推导的图形表示。(idid)的分析树(idid)的分析树例从最左推导构造的分析树例从最左推导构造的分析树句型与分析树的关系句型与分析树的关系设串是文法G的句型则至少存在一棵分析树它的叶子从左至右排列恰好就是。注意分析树的形状与推导顺序无关而与在推导时所选择的对句型中的非终结符号进行替换的产生式有关。每棵分析树都有与之对应的唯一的最左推导和最右推导。但是每个句子不一定只有唯一的分析树。二义性二义性二义性的一些例子Isawamaninthehillwithatelescope球拍卖完了。父在子先亡。文法句子id*idid有两个不同的最左推导:文法句子id*idid有两个不同的最左推导:EE*EEEEid*EE*EEid*EEid*EEid*idEid*idEid*ididid*idid二义性用分析树表示比较直观二义性用分析树表示比较直观EE*EEEEid*EE*EEid*EEid*EEid*idEid*idEid*ididid*idid文法的二义性文法的二义性如果一个文法的句子存在两棵分析树那么该句子是二义性的。如果一个文法包含二义性的句子则说这个文法是二义性文法否则说该文法是无二义性文法。文法的二义性源于这样的事实在一个句型中存在一个非终结符号A对于它有两条产生式可用于替换但A的这些推导最终都产生相同的句型。文法的二义性文法的二义性二义性是文法的性质。程序设计语言是无二义的。(自然语言本质是二义的在一定语境下没有二义)文法的二义性的消除:改写文法验证文法产生的语言验证文法产生的语言例G:S(S)S|L(G)={配对的括号串的集合}按推导步数进行归纳:推出的是配对括号串归纳基础:S归纳假设:少于n步的推导都产生配对的括号串归纳步骤:n步的最左推导如下:S(S)S*(x)S*(x)y按串长进行归纳:配对括号串可由S推出归纳基础:S归纳假设:长度小于n的都可以从S推导出来归纳步骤:考虑长度为n(n)的w=(x)yS(S)S*(x)S*(x)y正规式和上下文无关文法正规式和上下文无关文法正规语言(RL)是上下文无关语言(CFL)的真子集正规表达式所描述的语言可以用上下文无关文法描述。将NFA转换为等价的CFG。将正规表达式(a|b)*ab用CFG表示将正规表达式(a|b)*ab用CFG表示正规式(a|b)*ab文法AaA|bA|aAAbAA构造规则构造规则EachStateihasnonterminalAiIfthenAiaAjIfthenAiAjIfiisanacceptingstate,AiIfiisastartingstate,Aiisthestartsymbola正规文法正规文法若文法G=(VT,VN,S,P)中的每一个产生式形如:AaB或Aa其中A,BVN,aVT{}则称G为右线性文法。若文法G=(VT,VN,S,P)中的每一个产生式形如:ABa或Aa则称G为左线性文法。右线性文法和左线性文法都称为型文法(正规文法)。文法的编写文法的编写文法的优点文法给出了精确的易于理解的语法说明自动产生高效的分析器可以给语言定义出层次结构以文法为基础的语言的实现便于语言的修改文法的问题文法只能描述编程语言的大部分语法为什么要用正规式定义词法为什么要用正规式定义词法为什么不用CFG定义词法词法规则非常简单不必用上下文无关文法。对于词法记号正规表达式描述简洁且易于理解。从正规表达式构造出的词法分析器效率高。把词法分析从语法分析中分离出来的理由简化设计编译器的效率会改进编译器的可移植性加强便于编译器前端的模块划分消除二义性消除二义性stmtifexprthenstmt|ifexprthenstmtelsestmt|other句型ifEthenifEthenSelseS的分析树句型ifEthenifEthenSelseS的分析树Form:Form:改写为无二义的文法(else与最近的then匹配)改写为无二义的文法(else与最近的then匹配)stmtmatchedstmt|unmatchedstmtmatchedstmtifexprthenmatchedstmtelsematchedstmt|otherunmatchedstmtifexprthenstmt|ifexprthenmatchedstmtelseunmatchedstmt消除左递归消除左递归文法左递归AAa直接左递归AAa|b串的特点baa消除直接左递归AbAAaA|例:算术表达文法EET|T(TTT)TT*F|F(F*F*F)F(E)|id消除左递归后文法ETEETE|TFTT*FT|F(E)|id非直接左递归SAa|bASd|先变换成直接左递归SAa|bAAad|bd|再消除左递归SAa|bAbdA|AAadA|间接左递归的消除间接左递归的消除SAc|cABb|bBSa|a将B代入得到:ASab|ab|b将A代入得到:SSabc|abc|bc|c再消除直接左递归:SabcS'|bcS'|cS' SabcS'|Algorithm消除左递归Algorithm消除左递归Input:GrammarGwithnocyclesorproductionsOutput:AnequivalentgrammarwithnoleftrecursionArrangethenonterminalsinsomeorderA,A,…Anfori:=tondobeginforj:=toi–dobeginreplaceeachproductionoftheformAiAjbytheproductionsAi||…|kwhereAj||…|kareallcurrentAjproductionsendeliminatetheimmediateleftrecursionamongAiproductionsend例Applythealgorithmto:SAa|bAAc|Sd|i=:ForAthereisnoleftrecursioni=:AAdbecomesAAad|bdNow,what’sleft:AAa|bAAc|Aad|bd|removeAleftrecursion:AAa|bAbdA|AAcA|adA提左因子提左因子不确定选择哪个规则来替换非终结符例如:stmtifexprthenstmtelsestmt|ifexprthenstmt改写产生式。改写有左因子的文法改写有左因子的文法对于所有形如A||…|n|提左因子改写为AA|A|…|n悬空else的文法悬空else的文法stmtifexprthenstmtelsestmt|ifexprthenstmt|other提取左因子得到:stmtifexprthenstmtoptionalelsepart|otheroptionalelsepartelsestmt|非上下文无关的语言结构非上下文无关的语言结构L={wcw|w属于(a|b)*}检查标识符的声明应先于其引用的抽象L={anbmcndm|n,m}检查形参个数和实参个数应该相同的抽象L={anbncn|n}打字机打印下划线字符的抽象注意:一些类似的语言却是CFG。注意:一些类似的语言却是CFG。L={wcwR|w(a|b)*}SaSa|bSb|cL={anbmcmdn|n,m}SaSd|aAdAbAc|bcL={anbncmdm|nm}SABAaAb|abBcBd|cdL={anbn|n}SaSb|abL是不能用正规式描述的语言的一个范例若存在接受L的DFAD状态数为k个。设D读完,a,aa,…,ak分别到达状态s,s,…,sk至少有两个状态相同例如是si和sj则ajbi属于LL={anbncn|n}是上下文有关文法L={anbncn|n}是上下文有关文法SaSBCSaBCCBBCaBabbBbbbCbccCccanbncn的推导过程如下:S*anS(BC)nan(BC)nanBnCnanbBnCnanbnCnanbncCnanbncn形式语言鸟瞰形式语言鸟瞰Chomsky在创立了形式语言学并将形式语言的文法分为四类:文法G=(VT,VN,S,P)型文法(短语结构文法,PSG),(VNVT)*,||型文法(上下文有关文法,CSG)||||但S可以例外型文法(上下文无关文法,CFG)AAVN,(VNVT)*型文法(正规文法,RG)AaB或AaA,BVN,aVT形式语言鸟瞰形式语言鸟瞰上述文法产生的语言分别称为递归可枚举语言上下文有关语言上下文无关语言正规语言文法的类型文法的类型习题习题P)(尽可能完成各小题)P

精彩专题

职业精品

上传我的资料

热门资料

资料评价:

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

意见
反馈

返回
顶部

Q