欢迎来到麦多课文档分享! | 帮助中心 海量文档,免费浏览,给你所需,享你所想!
麦多课文档分享
全部分类
  • 标准规范>
  • 教学课件>
  • 考试资料>
  • 办公文档>
  • 学术论文>
  • 行业资料>
  • 易语言源码>
  • ImageVerifierCode 换一换
    首页 麦多课文档分享 > 资源分类 > PPT文档下载
    分享到微信 分享到微博 分享到QQ空间

    第四章 语法分析.ppt

    • 资源ID:374259       资源大小:535.50KB        全文页数:39页
    • 资源格式: PPT        下载积分:2000积分
    快捷下载 游客一键下载
    账号登录下载
    微信登录下载
    二维码
    微信扫一扫登录
    下载资源需要2000积分(如需开发票,请勿充值!)
    邮箱/手机:
    温馨提示:
    如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如需开发票,请勿充值!如填写123,账号就是123,密码也是123。
    支付方式: 支付宝扫码支付    微信扫码支付   
    验证码:   换一换

    加入VIP,交流精品资源
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    第四章 语法分析.ppt

    1、第四章 语法分析,第四章 语法分析,本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开,上下文无关文法,4.14.3,4.1 上下文无关文法,4.1.1 上下文无关文法的定义正则式能定义一些简单的语言,能表示给定结构的固定次数的重复或者没有指定次数的重复例:a (ba)5, a (ba)*正则式不能用于描述配对或嵌套的结构例1:配对括号串的集合例2:wcw | w是a和b的串,4.1 上下文无关文法,上下文无关文法是四元组(VT , VN , S, P) VT : 终结符集合 VN : 非终结符集合 S : 开始符号,非终结符中的一个 P : 产生式集合, 产生式形

    2、式 : A 例 ( id, +, , , (, ), expr, op, expr, P ) expr expr op expr expr (expr) expr expr expr id op + op ,4.1 上下文无关文法,简化表示 expr expr op expr | (expr) | expr | id op + | 简化表示 E E A E | (E ) | E | id A + | ,4.1 上下文无关文法,文法书写上的约定 终结符 字母表中的小写字母,如 a,b,c 黑体串,如 id, while 数字 0, 1, , 9 标点符号,如括号,逗号等 运算符号,如+, -等

    3、非终结符 字母表中的大写字母,如A, B, C 字母S,并且通常代表开始符号 小写字母的名字(斜体),如expr, stmt,4.1 上下文无关文法,文法书写上的约定 字母表中后面的大写字母,如X,Y,Z,可以是终结符或非终结符 字母表中后面的小写字母,如u,v z 可代表终结符号串 小写希腊字母,如a,b,可代表文法的符号串 对于A a1,A a2,. A an可以写成A a1 | a2 | | an,4.1 上下文无关文法,4.1.2 推导(自顶向下) 把产生式看成重写规则,把符号串中的非终结符用其产生式右部的串来代替 例 E E + E | E E | (E ) | E | id E E

    4、 (E) (E + E) (id + E) (id + id) 概念 S *、 S + w ,于是 * * b, 且 b , 则 * ,4.1 上下文无关文法,4.1.2 推导 概念 上下文无关语言 A, 且a、b是任意符号串,则aAb ab 由上下文无关文法生成的语言是上下文无关语言 等价的文法 如果两个文法产生同样的语言,则两个文法等价 句型 文法G的开始符为S,S *, 可能含有非终结符,则叫做文法G的句型。,4.1 上下文无关文法,例 E E + E | E E | (E ) | E | id 最左推导E lm E lm (E) lm (E + E) lm (id + E) lm (i

    5、d + id) 最右推导E rm E rm (E) rm (E + E) rm (E + id) rm (id + id),4.1 上下文无关文法,4.1.3 分析树 例 E E + E | E E | (E ) | E | id,E,E,(,),E,E,E,+,id,id,4.1 上下文无关文法,4.1.4 二义性 id id + idE 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两个不同的最左推导,4.1 上下文无关文法,4.1.4 二义性 id id + idE E

    6、 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两棵不同的语法树,4.2语言和文法,文法的优点 文法给出了精确的,易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改文法的问题 文法只能描述编程语言的大部分语法,不能描述语言中上下文有关的语法特征,4.2 语言和文法,4.2.1 正则式和上下文无关文法的比较 正则式 (a|b)*ab文法 A0 a A0 | b A0 | a A1 A1 b A2 A2 ,4.2 语言和文法,4

    7、.2.2 分离词法分析器理由为什么要用正则式定义词法 词法规则非常简单,不必用上下文无关文法 对于词法记号,正则式描述简洁且易于理解 从正则式构造出的词法分析器效率高,4.2 语言和文法,从软件工程角度看,词法分析和语法分析的分离有如下好处简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分,4.2 语言和文法,能否把词法分析并入到语法分析中,直接从字符流进行语法分析若把词法分析和语法分析合在一起,则必须将语言的注解和空白的规则反映在文法中,文法将大大复杂 注解和空白由自己来处理的分析器,比注解和空格已由词法分析器删除的分析器要复杂得多,4.2 语言和文法,4.2.3

    8、验证文法产生的语言 G : S (S) S | L(G) = 配对的括号串的集合,4.2 语言和文法,4.2.3 验证文法产生的语言 G : S (S) S | L(G) = 配对的括号串的集合按推导步数进行归纳:推出的是配对括号串 归纳基础: S 归纳假设:少于n步的推导都产生配对的括号串 归纳步骤:n步的最左推导如下:S (S)S * (x) S * (x) y,4.2 语言和文法,4.2.3 验证文法产生的语言 G : S (S) S | L(G) = 配对的括号串的集合按串长进行归纳:配对括号串可由S推出 归纳基础: S 归纳假设:长度小于2n的都可以从S推导出来 归纳步骤:考虑长度为

    9、2n(n 1)的w = (x) yS (S)S * (x) S * (x) y,4.2 语言和文法,4.2.4 适当的表达式文法 用一种层次观点看待表达式id id (id+id) + id id + id,4.2 语言和文法,4.2.4 适当的表达式文法 用一种层次观点看待表达式id id (id+id) + id id + idid id (id+id) 文法expr expr + term | termterm term factor | factor factor id | (expr),4.2 语言和文法,expr expr + term | term term term facto

    10、r | factor factor id | (expr),id + id id 分析树,id id id 分析树,4.2 语言和文法,4.2.5 消除二义性 stmt if expr then stmt| if expr then stmt else stmt| other 句型:if expr then if expr then stmt else stmt 两个最左推导:stmt if expr then stmt if expr then if expr then stmt else stmtstmt if expr then stmt else stmt if expr then i

    11、f expr then stmt else stmt,4.2 语言和文法,无二义的文法stmt matched _stmt | unmatched_stmtmatched_stmt if expr then matched_stmt else matched_stmt | otherunmatched_stmt if expr then stmt| if expr then matched_stmt else unmatched_stmt,4.2 语言和文法,4.2.6 消除左递归 消除左递归 A A | A R R R | ,4.2 语言和文法,4.2.6 消除左递归文法左递归 A+Aa 直

    12、接左递归 AAa |b 串的特点 ba . . . a消除直接左递归A b AA a A | ,4.2 语言和文法,例 算术表达文法 E E + T | T ( T + T . . . + T )T T F | F ( F F . . . F )F ( E ) | id 消除左递归后文法E TE E + TE | T FT T F T | F ( E ) | id,4.2 语言和文法,非直接左递归S Aa | bA Sd | 先变换成直接左递归S Aa | bA Aad | bd | 再消除左递归S Aa | bA bd A | AA adA | ,4.2 语言和文法,4.2.7 提左因子有左

    13、因子的文法A 1 | 2提左因子A AA 1 | 2,4.2 语言和文法,例 悬空else的文法 stmt if expr then stmt else stmt | if expr then stmt| other提左因子stmt if expr then stmt optional_else_part| otheroptional_else_part else stmt| ,形式语言,产生式形式为:xAy -xy,产生式形式为:A-aB , A-a , A-,产生式形式为:A - , 2 型语言 由 2型文法定义, 1 型语言 由 1型文法定义, 0 型语言 由 0型文法定义,产生式形式为

    14、: - , 3 型语言 由 3型文法定义,又称 无限制文法!,又称 上下文有关文法!,又称 上下文无关文法!,又称 正规文法!,【注】 四类语言为 包含关系,且有 L0 L1 L2 L3;,编译处理中,主要应用后两种文法!,乔姆斯基,艾弗拉姆诺姆乔姆斯基(英语:Avram Noam Chomsky,1928年12月7日) 美国哲学家、语言学家、认知学家、逻辑学家、政治评论家。乔姆斯基是麻省理工学院语言学的荣誉退休教授,他的生成语法被认为是20世纪理论语言学研究上的重要贡献。,句法结构,句法结构是乔姆斯基介绍转换生成语法的语言学理论的逻辑结构一书的精华版。这一理论认为说话的方式(词序)遵循一定的

    15、句法,这种句法是以形式的语法为特征的,具体而言就是一种不受语境影响并带有转换生成规则的语法。 儿童被假定为天生具有适用于所有人类语言的基本语法结构的知识。这种与生俱来的知识通常被称作普遍语法。,练习,文法 S-aSbS | bSaS | 产生的语言是什么?该文法是否有二义性? 下面的二义文法描述命题验算公式的语法,为他写一个等价的非二义文法 S-S and S | S or S| not S| p | q | (S),练习,文法 R-R|R | RR | R* | (R) | a | b 产生字母表a,b上所有不含的正则式。为该文法写一个等价的非二义文法。,练习,考虑文法 S-(L) | a L-L,S | S 建立句子(a,(a,a)和(a,(a,a),(a,a)的分析树 为(a)的两个句子构造最左推导 为(a)的两个句子构造最右推导 这个文法产生的语言是什么?,


    注意事项

    本文(第四章 语法分析.ppt)为本站会员(sumcourage256)主动上传,麦多课文档分享仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文档分享(点击联系客服),我们立即给予删除!




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
    备案/许可证编号:苏ICP备17064731号-1 

    收起
    展开