电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

语法分析程序的设计与实现ppt课件

22页
  • 卖家[上传人]:我***
  • 文档编号:148664930
  • 上传时间:2020-10-21
  • 文档格式:PPT
  • 文档大小:58.50KB
  • / 22 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、语法分析器的设计与实现自上而下的语法分析,阎 艳 2010.11,编译原理实验2,语法分析器的实质(ch4.1),功能:验证源程序是否符合语法规则。 输入:词法分析器生成的单词符号序列-种别 输出:语法分析树;如有错,则指明错误的性质和位置。,词法分析器,语法分析器,编译程序后续部分,符号表,语法分析器的分类,按照语法树的建立方法,分为 自上而下分析法 递归下降 预测分析 自下而上分析法 算符优先,自上而下语法分析器的实现,1 从语言定义中整理出语法规则,语法的定义,语法规则 通常用上下文无关文法描述(ch2.5),micro语言定义,仅有的数据类型是整型INT。 所有的标识符采用显式声明,且长度不超过32个字符。标识符必须以字母开头并由字母、数字和下划线组成。 整型常量由一串数字组成。 注释由“-”开始,并在当前行尾结束。 语句类型为: 赋值语句:ID := Expression;Expression是由标识符、文字常量、+ - * / 运算符组成的中缀表达式结构,其中允许含有括号。 输入输出语句:read( List of IDs);write(List of Expression

      2、s); begin、end、read、write、INT都是保留字。 每条语句以分号(;)结束。程序体由begin和end界定。 词法记号不能跨行。,1 从语言定义中整理出语法规则,/程序体由begin和end界定 $begin $end /每条语句以分号(;)结束 $semicolon | | | | | .,例1 $begin $end bool program() symbol=scanner(); if ( symbol = $begin) then /调用词法分析器获取下一个单词 symbol=scanner(); if ( statements() ) then if ( symbol = $end) return true; return false; ,例2 $add | $sub | bool expression() ,expression() $add term(),expression() $sub term(),term(),问题:左递归 回溯 解决:对语法规则加以限制 自上而下的语法要求:LL(1)文法,自上而下语法分析器的实现,2 将语法规则改造为LL(1

      3、)文法,LL(1)文法的条件,1)文法不含左递归 2)对于文法中每个非终结符A的各产生式的候选首符集不相交。即若A 1 | 2 | n 则 FIRST(i) FIRST(j) = (i j ) 3)对文法中每一个终结符A,若它存在某个候选首符集包含,则FIRST(A) FLLOW(A)= ,LL(1)文法消除左递归 ch4.3.1,直接左递归的消除方法 若 A A| ,其中不以A开头 则修改规则为:A A A A|,LL(1)文法消除左递归 ch4.3.1,消除左递归算法(解决间接左递归) 对文法G的所有非终结符进行排序 按上述顺序对每一个非终结符Pi依次执行: for( j=1; j i-1;j+) 将Pj代入Pi的产生式(若可代入的话); 消除关于Pi的直接左递归; 化简上述所得文法,将间接左递归转化为直接左递归,例3 消除表达式语法规则的左递归 $add | $sub | $mul | $div | $id | $num | $lpar $rpar,排序: E E $add E | $sub E | T T $mul T | $div T | $id | $num | $lpar

      4、 $rpar,LL(1)文法消除回溯,提左公因子(ch4.3.2) 假定 A 1| 2| |n| 1| 2| |m 则,改写成 A A| 1| 2| |m A 1 | 2 | | n,LL(1)文法消除回溯,对存在产生式的非终结符分析FIRST和FOLLOW (ch4.3.3),FIRST集的构造 若XVT,则FIRST(X)=X。 若XVN,且Xa,则把a加入到FIRST(X)中;若X,则把加入FIRST(X)中。 若XY,则把FIRST(Y)中的所有非-元素都加到FIRST(X)中; 若XY1Y2Yk,对任何j (1ji-1), FIRST(Yj)都含有(即Y1Yi-1 *),则把FIRST(Yi)中的所有非元素都加到FIRST(X)中;若所有的FIRST(Yj)均含有则把加到FIRST(X)中。,FOLLOW集的构造 连续使用下面的规则,至每个FOLLOW不再增大: 1)对于文法的开始符号S,置#于FOLLOW(S)中; 2)若AB即是一个产生式,则把FIRST()加至FOLLOW(B)中; 3)若AB是一个产生式,或AB即是一个产生式而 (即FIRST()),则把FOLLOW(

      5、A)加至FOLLOW(B)中。,语法规则,micro语言定义,LL(1)文法,整理 (手动),改造(手动或自动),自上而下语法分析器的实现,编程,语法分析 (错误处理机制),3 编程实现语法分析算法,递归下降分析程序(ch4.4,P74-76),每一非终结符对应一个布尔子过程: if 某个候选式与输入串匹配 then 按此式扩充语法树; 指针移过已匹配子串; return true; else return false。,可能存在的缺陷? 效率,错误处理 解决:非递归化预测分析,预测分析程序,数据结构 栈 预测分析表M,预测分析表的构造: (1)对文法G的每个产生式A执行第二步和第三步; (2)对于每个终结符aFIRST(),把A加到MA,a中; (3)若FIRST() ,则对任何的b FOLLOW(A)把A加至Ma,b中; (4)把所有无定义的MA,a标上“出错标志”或“同步符号”,初始:#、文法开始符 入栈,预测分析算法,根据STACK栈顶符号X和当前的输入符号a完成语法分析工作 1) 若X = a = #,则语法分析成功,停止分析过程。 2) 若X = a #,则X出栈,让a指向下一个输入符号。 3) 若X是一个非终结符,则查找分析表M。若MA,a中存放着关于X的一个产生式,则:先X出栈,然后将产生式的右部符号串按反序入栈。 4) 否则, 完成相关的出错处理。,错误处理机制(ch4.6),目的 遇到错误时,使语法分析程序可以继续下去。 思想 栈顶为非终结符:跳过输入符号至同步符号/ 栈顶为终结符号:弹出该终结符 / 跳过输入串/ 同步符号 FOLLOW集 ,语法规则,micro语言定义,LL(1)文法,整理 (手动),自上而下语法分析器的实现,语法分析 (错误处理机制),4 用正例和反例对语法分析程序进行测试,单词序列,词法分析器,输入字符,源程序,编程实现 -自动语法分析器,文档存储,语法分析结果,

      《语法分析程序的设计与实现ppt课件》由会员我***分享,可在线阅读,更多相关《语法分析程序的设计与实现ppt课件》请在金锄头文库上搜索。

      点击阅读更多内容
    TA的资源
  • 2020届中考英语备考复习-作文课件

    2020届中考英语备考复习-作文课件

  • 2019年中考英语复习-专题十五-交际运用(试卷部分)课件

    2019年中考英语复习-专题十五-交际运用(试卷部分)课件

  • 2019届二轮复习-高中英语-情态动词和虚拟语气课件

    2019届二轮复习-高中英语-情态动词和虚拟语气课件

  • 2019届一轮复习苏教版物质的跨膜运输课件

    2019届一轮复习苏教版物质的跨膜运输课件

  • 2019年北师大版英语单元复习课件::Unit17Laughter课件北师大版选修6

    2019年北师大版英语单元复习课件::Unit17Laughter课件北师大版选修6

  • 2021届新中考物理冲刺备考复习-力-弹力-重力课件

    2021届新中考物理冲刺备考复习-力-弹力-重力课件

  • 2019届一轮复习人教版种群的特征和数量变化课件

    2019届一轮复习人教版种群的特征和数量变化课件

  • 2020年高考地理一轮复习--等高线地形图-课件

    2020年高考地理一轮复习--等高线地形图-课件

  • 2019版高考英语一轮复习-Unit-1-Living-well课件

    2019版高考英语一轮复习-Unit-1-Living-well课件

  • 2019届一轮复习人教版孟德尔的遗传定律——基因分离定律课件

    2019届一轮复习人教版孟德尔的遗传定律——基因分离定律课件

  • 2019届高三第二轮复习专题二万有引力定律及其应用课件

    2019届高三第二轮复习专题二万有引力定律及其应用课件

  • 2020最新部编版语文五年级上册23-鸟的天堂课件含课后练习

    2020最新部编版语文五年级上册23-鸟的天堂课件含课后练习

  • 2020版高考(浙江)一轮复习:第7讲-细胞呼吸课件

    2020版高考(浙江)一轮复习:第7讲-细胞呼吸课件

  • 2020年新教材高中英语UNIT4HISTORYANDTRADITIONSSectionⅢDiscoveringUsefulStructures课件必修第二册

    2020年新教材高中英语UNIT4HISTORYANDTRADITIONSSectionⅢDiscoveringUsefulStructures课件必修第二册

  • 2019届高考历史二轮复习阶段三专题十三罗斯福新政与当代资本主义的新变化课件2

    2019届高考历史二轮复习阶段三专题十三罗斯福新政与当代资本主义的新变化课件2

  • 2019版高考生物二轮复习-专题三-细胞的生命历程-考点9-细胞分裂过程图像和坐标曲线的识别课件

    2019版高考生物二轮复习-专题三-细胞的生命历程-考点9-细胞分裂过程图像和坐标曲线的识别课件

  • (通史版)2021版高考历史一轮复习第4部分高考讲座(三)2高考非选择题(12分开放探究题)规范答题讲练课件

    (通史版)2021版高考历史一轮复习第4部分高考讲座(三)2高考非选择题(12分开放探究题)规范答题讲练课件

  • 2019届高三地理复习第五讲--《区际联系与区域协调发展》课件

    2019届高三地理复习第五讲--《区际联系与区域协调发展》课件

  • 2021人教部编版历史九年级上册习题课件:第18课美国的独立

    2021人教部编版历史九年级上册习题课件:第18课美国的独立

  • 2020学年新教材高中英语Unit1FoodforthoughtPeriodTwoStartingout课件

    2020学年新教材高中英语Unit1FoodforthoughtPeriodTwoStartingout课件

  • 点击查看更多
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.