7 语法分析 语法树 二义性文法.ppt

  1. 1、本文档共18页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
7语法分析语法树二义性文法整理ppt

第三章:语法分析 语法树 二义性文法 正则文法与自动机 内容介绍 语法树 文法的二义性 正则文法与自动机 1.1 语言树的定义 语法树:设G是给定的语法,称满足下列条件的树为G的一棵语法树: 1. 树的每个节点都标有G的一个语法符号,且根节点标有初始符S。 2. 如果一个非叶节点A按从左到右顺序有n个儿子节点B1、B2、…、Bn,则: A?B1B2…Bn 一定是G的一个产生式. 1.1 语言树的定义 例子:有文法 E ?E+T E ?T T ? T *F T ?F F ? ( E ) | i 1.2 语法树的作用 作用主要有两点: 语法树反映出我们推导的过程,每一步节点的生长过程都可以对应到我们的一步推导。 语法树反应出串的语法结构。 1.3 语法树和语法概念的关系 子树:某语法树T中的某一节点A和它所有分支组成的树T,则称T是T的一颗子树。 简单子树:某一节点A与其子节点(单层节点)组成的树。从严格意义上来说,A应该有且仅有一层子节点。 1.3 语法树和语法概念的关系 结论 语法树的所有叶节点(从左到右)组成的是一个句型 语法树的子树所有叶节点(从左到右)组成的是一个短语 简单子树所有叶节点(从左到右)构成一个简单短语 最左简单子树叶节点对应的是一个句柄 1.3 语法树和语法概念的关系 例子:(T+i)*F+i 2.1 文法的二义性 定义:设存在文法G,若G的某一个句子存在两棵不同的语法树,则称G为二义性文法。 例1:表达式文法E ?E+E|E*E|(E)|i 对于i+i*i有: 2.1 文法的二义性 例2,PASCAL语言中的条件语句: 正常 if (E) then S1 else S2 简写 if (E) then S1 二义性:if (E1) then S1 if (E2) then S2 else S3 2.2 文法二义性的判定和利用 文法二义性的判断 目前,不存在一个一般性的方法来判断一个现有文法是否为二义性文法。 常用的经验性判断: S?SS|a 可以推导出SSS串,必有二义性 S?S+S 可以推导出S+S+S,必有二义性 2.2 文法二义性的判定和利用 文法二义性的利用 对二义性文法进行修改,消除其二义性会导致文法的复杂程度和符号数目迅速升高。 可以利用二义性文法状态少,分析快的特点,使用二义性文法,对具体问题加入语义规则,约束其二义性即可。 3.1 正则文法和DFA间的关系 定理:正则文法(3型文法)与DFA等价 构造性证明:给定一个正则文法G(VN, VT, P, S) 构造一个等价的DFA A(?,S,S0,f, Z),使得L(G)=L(A)。 3.2正则文法到DFA的转换 构造方法: 令S=VN∪{k}; ?=VT ; S0=Z; F={k}; 转换函数f 如果有X?aY 则构建f(X,a)=Y 如果有X?a 则构建f(X,a)=k 例子: Z?aZ|bB|c B?dB|b 3.3 DFA到正则文法的转换 构造方法 令Z={A|A∈Z,A没有输出边}; S=S0; VN=S-Z; VT=?; 规则P: 若有f(X,a)=Y,且Y?Z,则构建X?aY; 若有f(X,a)=Y,且Y∈Z ,则构建X?a; 若干历年考试题 构造一个文法G,使L(G)={anbmck|m=n+k,n≥1,m1,k≥1} G[S]: S?AB ???????? A?aAb| ab ???????? B?bBc| bc 若干历年考试题 ?已知文法G[Z]: Z?WV? W?aB?|?aW?|?a??? B?b?|?bB? V?bV?|?dD? D?d?|?dD 判断文法G[Z]是否为二义性文法,如果是请举例 句子abdd有两棵语法树。 若干历年考试题 设有一个文法G[S]: S-V V-T|ViT T-F|T+F F-V*|[ 句型F+Fi[的短语,简单短语和句柄分别为: 首F,F+F, F+Fi[, [ 首F,[; 首F。 * * 上一次课给大家介绍了形式语言的一些基础知识,提出了一些基础概念,同学们可以从两个角度来理解,1、我们从文法的开始符出发,推导出一个符号串,按照定义来说这个串是一个句子,这个句子映射到我们程序设计语言中就是用户写的一个程序,要验证这个程序有没有语法错误,就是从开始符出发一步一步推导看看能不能把这个程序推导出来,这里的定义就涉及到句型 句子 语言,2、从另外一个角度来看,我们要验证一个串是不是文法的句子可以反过

文档评论(0)

zyzsaa + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档