首页 范文大全 古典文学 职场知识 中国文学 公文书信 外国名著 寓言童话 百家讲坛 散文/诗歌 美文欣赏 礼仪知识 民俗风情
  • 工作总结
  • 工作计划
  • 心得体会
  • 竞聘演讲
  • 会议发言
  • 爱国演讲
  • 就职演说
  • 开业开幕
  • 思想学习
  • 征文演讲
  • 经验材料
  • 述职报告
  • 调研报告
  • 工作汇报
  • 年终总结
  • 申报材料
  • 学习体会
  • 企划方案
  • 活动方案
  • 技巧经验
  • 模板范例
  • 思想宣传
  • 经济工作
  • 工作报告
  • 组织人事
  • 反腐倡廉
  • 慰问贺电
  • 先进事迹
  • 思想汇报
  • 入党申请书
  • 党会发言
  • 先进性教育
  • 入团申请书
  • 个人简历
  • 演讲稿
  • 调查报告
  • 实习报告
  • 和谐社会
  • 观后感
  • 读后感
  • 作文范文
  • 自我鉴定
  • 讲话稿
  • 自查报告
    • 蒲公英阅读网 > 范文大全 > 开业开幕 > 正文

    判断LL1型文法实验报告-A版

    时间：2020-09-29 11:51:14 来源：蒲公英阅读网 本文已影响人 蒲公英阅读网手机站

    相关热词搜索：文法 判断 实验

    　一、实验目的 首先能让用户输入一个文法，然后让计算机自动判断是否是一个 LL(1)文法，通过实验教学， 加深学生对所学的关于编译的理论知识的理解，增强学生对所学知识的综合应用能力，并通 过实践达到对所学的知识进行验证。

    　二、实验环境 供 Windows 系统的PC 机，可用C++/C#/Java 等编程工具编写 三、实验内容 1、让计算机接受一个文法，示例如：

    　G[S] 为: S→AB S→bC A→ε A→b B→ε B→aD C→AD C→b D→aS D→c 1. 2、编程实现对上述文法是否是LL(1)文法的判断，是则给出肯定回答，否则给出否 定回答。

    　2. 判别是否是 LL(1)文法 实验流程图如下：

    　以链表或数组等数 据结构保存文法. 求出能推出 ε 的非 终结符. 计算 FIRST 集,FOLLOW 集和 SELECT 集 是 SELECT(A→α )∩S 输出肯定 ELECT(A→β )=Φ ? 回答 否 输出否定回答

    　四、概要设计 （1）、LL（1）文法的定义

    　LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个 L 表明自顶向下分 析是从左向右扫描输入串，第2 个 L 表明分析过程中将使用最左推导，1 表明只需向右看一 个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。

    　LL(1)文法的判别需要依次计算FIRST集 、FOLLOW集和SELLECT集,然后判断是否为LL(1) 文法,最后再进行句子分析。

    　需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶出现 非终极符时，要预测用哪个产生式的右部去替换该非终极符；当出现终结符时，判断其与剩 余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错。LL(1)分析方法要求 文法满足如下条件：对于任一非终极符A的两个不同产生式A ,A ，都要满足下面条件：

    　SELECT(A )∩SELECT(A )=

    　（2）、预测分析表构造 LL(1)分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导。

    　它的行对应文法的非终极符，列对应终极符，表中的值有两种：一是产生式的右部的字符串， 一是 null。若用 M 表示 LL(1)分析表，则 M 可表示如下：

    　M: VN×VTP∪{Error} M(A, t) = Aα ，当 t select(Aα ) ，否则 M(A, t) = Error 其中 P 表示所有产生式的集合。

    　（3）、语法分析程序构造

    　LL(1)分析中X为符号栈栈顶元素，a为输入流当前字符，E为给定测试数据的开始符号， #为句子括号即输入串的括号。分析表用一个二位数组 M 表示，数组元素 M[A，a]中的下标 A 表示非终结符，a 为终结符或句子括号‘#’，二维数组中存放的是一条关于A 的产生式， 表明当非终结符 A 向下推导时，面临输入符 a 时，所采用的候选产生式，当元素内容无产生 式时，则表明用 A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理 的信息。

    　LL(1)分析过程主要包括以下四个动作：

    　替换：当 X VN时选相应产生式的右部 去替换 X。此时 X 出栈， 逆序入栈。

    　匹配：当 X VT时它与 a 进行匹配，其结果可能成功，也可能失败，如果成功则符号栈 中将 X 退栈并将输入流指针向前移动一位，否则报错。

    　接受：当格局为（#，空#）时报告分析成功。

    　报错：出错后，停止分析。并给出相应的错误提示信息。

    　五、详细设计 【流程图】

    　1. 总体思路分析及流程图

    　给定一个正规文法 G，在 LL(1)预测分析中，必须先求出 First 集和 Follow 集，然后求 出 Select 集，通过Select 集判断是否是 LL1 文法，如果是的话，构造预测分析表。求出预 测分析表之后，再输入一个字符串，依据LL1 分析表单步输出字符串的分析过程。

    　读取正规文法 求文法的First集 求文法的Follow集 求文法的Select集 键盘输入字符串 字符串分析 功能模块分解图

    　（1）主程序流程图 开始 输入文法 判断文法是否为 LL(1)文法 Y

    　N 构造预测分析

    　表 输入要分析的 符号串 出错处理

    　出错处理 N

    　判断该符号串是否可被 该文法识别 Y 提示i*i+i#为 可接受的字符

    　串 结束 （2）核心算法流程图 1.计算非终结符的 First集的算法及流程：

    　First集合的构造算法：

    　（1）若 X∈VT，则 First（X）={X}。

    　（2）若 X∈VN，且有产生式 X→a……，则把 a 加入到 First (X)中；若 X→ε 也是一条 产生式，则把ε 也加到 First (X)中。

    　（3）若 X→Y……是一个产生式且 Y∈VN，则把 First (Y)中的所有非ε -元素都加到 First (X)中；若 X→Y1Y2…Yk是一个产生式，Y1，…，Yi-1都是非终结符，而且，对于任 何 j，1≤j≤i-1，First (Yj)都含有ε （即 Y1…Yi-1* ε ），则把 First (Yj)中的所有非 ε -元素都加到 First (X)中；特别是，若所有的 First (Yj)均含有ε ，j=1,2,…，k，则把 ε 加到 First (X)中。

    　连续使用上面的规则，直至每个集合 First不再增大为止。

    　开始 读取一个非终 结符V 遍历所有产生 式，查找左部

    　是V的产生式

    　添加一个删除 空的标志为 true

    　取出得到的一

    　条产生式

    　V*是不是有推导规 则V*->空

    　产生式右部第一个符 号V*是终结符？ 将该终结符V* 加入V的First集 中 空标志为真 删除空，得到 V的First集 剩有非终结符？ 结束 2.计算非终结符的 Follow 集：

    　Follow 集合的具体构造算法如下：

    　（1）对于文法的开始符号 S，置#于 Follow(S)中； （2）若 A→α Bβ 是一个产生式，则把 First(β )|{ε }加至 Follow(B)中；

    　（3）若 A→α B 是一个产生式，或 A→α Bβ 是一个产生式而β ε（即ε ∈First(β )）， 则把 Follow(A)加至 Follow(B)中。

    　连续使用上面的规则，直至每个集合 Follow 不再增大为止。

    　开始 取得一个非终结符 V 查找产生式的右部 含有V的产生式 Y

    　V是不是最后一个字符 N

    　V后一个字符V*是 否为终结符 Y

    　Y

    　添加#到V的Follow 集中 Y N

    　是否遍历完所有右 部含有V的产生式

    　添加V*到V的Follow中 Y 将V*的First集加入到V的

    　Follow集中

    　是否有未求解过的 非终结符

    　N 完成

    　六、结果分析 七、 实验感想

    　本次实验用 C 语言操作判断 LL1 型文法，判断 LL1 型文法实验最主要的地方 在于需要依次计算 FIRST 集、FOLLOW 集和 SELLECT 集,然后判断是否为 LL(1)文 法,最后再进行句子分析。由于代码的精确性造成了前几次操作结果的误差，不 过在分析之后，对代码内的冗余进行了删除，纠正了实验结果。本次实验收货颇 多。

  • 【女人最好的排毒养颜粥有什么】早上喝什么
  • 2018年是什么生肖年运程:麦玲玲2018年生肖运程
  • 成功的滋味作文500字_五年级成功的滋味作文
  • 中英文对照小笑话短文:中英文对照小说
  • 电脑系统内存使用情况怎么查看:查看jvm内存
  • 享受成功的快乐作文|享受什么的快乐作文
  • 【二年级北京课文反思】 二年级上册语文书
  • 属龙的2017年命运 属龙的2017年1月运程
  • word文档如何添加页码【word文档中页码怎么
    • 范文大全
    • 职场知识
    • 精美散文
    • 名著
    • 讲坛
    • 诗歌
    • 礼仪知识
    最新文章

    推荐访问

    大反思大讨论活动 保安全” 筑防线 “查思想 贡献伟大时代” “以青春之我 工作评议报告 创建活动综述 市社保局党支部 自述报告 “党员先锋示范岗” 党建德育工作 达标创星活动 “星级党支部”创建 评星定级管理 社会组织党支部 第四巡察组 新进年轻干部 委厅机关 党性教育培训班 履职能力建设专题培训班 新考录社区工作者 “头雁领航”重点培训班 党组织业务培训 能力提升培训会 赋能经济高质量发展 “五好”园区 三年攻坚行动 行政管理能力建设提升班 高质量发展能力提升培训班 市疾控系统 中基层管理人员 专业能力提升专题培训班 新发展预备党员 进驻工作 迎接审计组 讲评推进大会 “三抓三促”行动动员 “永不过时的红岩精神” 市委党史研究室 科学绿化现场会 深化以案促改 一体推进不敢腐不能腐不想腐 奋斗精神 专题辅导讲稿 坚守使命追求 涉密 《党史学习教育工作条例》 百年新征程 “百年定位” 党课教育

    本文判断LL1型文法实验报告-A版由蒲公英阅读网整理提供，版权归原作者、原出处所有。

    Copyright © 蒲公英阅读网 All Rights Reserved.