LL(1)文法分析

《LL(1)文法分析》由会员分享，可在线阅读，更多相关《LL(1)文法分析（20页珍藏版）》请在金锄头文库上搜索。

1、编译原理课程设计报告编译原理课程设计报告 选题名称选题名称 LL 1 语法分析 系 院 系 院 计 算 机 工 程 系 专专 业业 计算机科学与技术 学年学期学年学期 2010 2011 学年 第 1 学期 2010年 12 月 30 日 设计任务书设计任务书 课题课题 名称名称 LL 1 语法分析 设计设计 目的目的 LL 1 分析法的基本思想是 自顶向下分析时从左向右扫描输入串 分析 过程中将采用最左推导 并且只需向右看一个符号就可决定如何推导 通过 对给定的文法构造预测分析表和实现某个符号串的分析 掌握 LL 1 分析法 的基本思想和实现过程 实验实验 环境环境 1 微型电子计算机 PC

2、 2 Windows XP 操作系统 Visual C 6 0 开发工具 任务任务 要求要求 1 录入合法的 LL 1 文法 2 构造并输出预测分析表 3 对输入的符号串进行语法分析 工作进度计划工作进度计划 序号序号起止日期起止日期工工 作作 内内 容容 110 12 27 10 12 27选定题目 明确题目要求 210 12 28 10 12 28课题深入调研 细化工作 系统方案设计 310 12 29 10 12 29程序录入 调试 整合 410 12 30 10 12 31上机演示 课程设计分组答辩 完成课程设计报告 指导教师 签章 指导教师 签章 年年 月月 日日 摘要 语法分析是编

3、译程序的核心部分 语法分析的作用是识别由词法分析给出的单词 符号序列是否是给定的文法的正确句子 目前语法分析常用的方法右自顶向下分析和 自底向上分析两大类 确定的自顶向下方法 是从文法的开始符号 考虑如何根据当 前的输入符号 单词 唯一的确定选用哪个产生式替换相应非终结符往下推导 LL 1 文法是一种确定的自顶向下的分析方法 LL 1 分析法的功能是利用 LL 1 控制 程序根据显示栈顶内容 向前看符号以及 LL 1 分析表 对输入符号串自上而下的分 析过程 可通过消除左递归 提取左因子把非 LL 1 文法改造成 LL 1 文法 当文法 满足条件后 分别构造出文法的每个非终结符的 FIRST

4、FOLLOW 集合和 SELECT 集 根据 SELECT 集合判断是否是 LL 1 文法 在 LL 1 预测分析程序设计过程中 最重要 的两个问题是预测分析表的构造和相关数据结构的设计 而预测分析表的构造首先必 须计算文法每个非终结符的 FIRST 集和 FOLLOW 集 要知道一串符号是不是该文法的 一个句子 只要判断是否能从文法的开始符号出发推导出这个输入串 语法分析可以 分为两类 一类是自上而下的分析法 一类是自下而上的分析法 自上而下的主旨是 对任何输入串 试图用一切可能的办法 从文法开始符号出发 自上而下的为输入串 建立一棵语法树 或者说 为输入串寻找一个最左推倒 这种分析过程的本

5、质是一种 试探过程 是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程 关键词 语法分析 LL 1 分析 FIRST 集合 FOLLOW 集合 自上而下分析 目录目录 1 课题综述 1 1 1 课题来源和意义 1 1 2 预期目标 1 1 3 解决问题 1 2 系统分析 1 2 1 涉及的知识基础 1 2 1 1 LL 1 文法 1 2 1 2 确定的自顶向下分析思想 2 2 1 3 左递归的消除 3 2 1 4 消除回溯 提左因子 4 2 1 5 计算FIRST集合 FOLLOW集合和SELECT集合 4 2 2 解决问题的基本思路 5 2 3 功能模块框图 5 3 系统设计 5

6、 3 1 LL 1 文法输入设计 6 3 2 LL 1 语法分析详细流程图 6 3 3 算法描述 7 3 3 1 消除左递归的算法 7 3 4 系统流程 图 8 4 代码编写 9 4 1 相关代码 9 4 4 运行结果 12 总 结 14 致 谢 15 参 考 文 献 16 编译原理 课程设计报告 1 1 课题综述课题综述 编译原理的设计一般都是从文法和语言的基础知识开始 沿着词法分析 语法分 析 语义分析 语法翻译 中间代码生成及符号表组织序列进行 本课题的总体设计 完全依据编译原理的教学内容 即上下文无关文法基础及词法分析 语法分析技术研 究 语法推导的语义翻译 代码优化及目标代码生成 但

7、是在本课题中只涉及到了关 于文法分析的相关知识 1 1 课题来源课题来源和意义和意义 LL 1 文法是一种简单易行的 自顶向下的 且较易实现的文法 它的原理在 编译原理的书上已有详细叙述 本文着重于介绍其实现过程中的一些细节及思考 LL 1 表明自顶向下分析技术是从左向右扫描输入串 分析过程中将用最左推导 以及只需向右看一个符号便可决定如何推导的一种文法 首先必须判断所给文法是否 是 LL 1 文法 然后编写构造 LL 1 语法分析程序 因而对任给文法需计算 FIRST FOLLOW SELECT 集合 进而判别文法是否为 LL 1 文法 设计中实现语 法分析使用的语言是 C 使程序能达到上述

8、目标 1 2 预期目标预期目标 熟练掌握运用 VC 建立工程 并用 VC 语言进行程序编写 掌握编程思想和算 法 熟练掌握 LL 1 文法的分析方法 利用 FIRST 集合 FOLLOW 集合以及 SELECT 集合得到预测分析表 并且各集合的计算方法也是设计的目标 1 3 解决解决问题问题 1 对于一个输入文法 消除文法的左递归 2 理解计算 FIRST FOLLOW 集合和 SELECT 集合的方法 3 理解文法分析表的构造 2 2 系统分析系统分析 2 1 涉及的知识基础涉及的知识基础 2 1 1 LL 1 文法 LL 1 文法是一类可以进行确定的自顶向下语法分析的文法 一个用来描述语言

9、语 法结构的文法G 2 可形式地定义如下 编译原理 课程设计报告 2 一个文法G S 可表示成形如 VN VT P S 的四元式 其中VN VT P均为非 空的有限集 分别称为非终结符集 终结符集和产生式集 具体来说 VN 一系列需要定义的语法范畴 VT 若干基本符号 不需要进一步定义 P 用 连接起来的有序对 A 的集合 称为规则 也叫产生式 其中A是一 个非终结符 是一个由终结符或非终结符组成的符号串 即 VN VT S 是文法的开始符号 S VN 此外 我们还将出现在产生式左 右侧的全部符号的集合称为词汇表 记为V 显然 V VN VT VN VT 更确切地说 上面给出的是上下文无关文法

10、的定义 这是因为由符号串a去替换A 时 并不考虑A所处的环境 即与A的上下文无关 除非另做说明 我们以后所说的 文法均指上下文无关文法 LL 1 的含义 第一个 L 表示从左至右扫描输入符号串 第二个 L 表示生成输入串的一个最左推导 1 表示在决定分析程序的每步动作时 向前看一个符号 2 1 2 确定的自顶向下分析思想 LL 1 文法是一类可以进行确定的自顶而下语法分析的文法 而自顶而下分析法 的基本思想是从文法的开始符号出发采用最左推导 根据当前的输入符号 单词符号 惟一地确定选用哪个产生式替换相应非终结符以下推导 这种分析过程实质是一种试 探过程 是反复使用不同产生式匹配输入符号串的过程

11、 若有文法 S cAd A ab a 输入串W cad 为建立分析树 首先建立只有标记S单个结点树 输入指针指向W 的第一个符号c 然后用S的第一个产生式来扩展该树 得到的树如图2 1所示 编译原理 课程设计报告 3 S cAd S cAd S ab S cAd a a b c 图2 1 1语法分析树 最左边的叶子标记为c 匹配W的第一个符号 于是 推进输入指针到W的第二个 符号a 并考虑下一个标记为A的叶子 用A的第一个选择来扩展A 得到如图 b 的树 现在匹配第二个输入符号a 再推进输入指针到d 把它和下一个标记为b的叶子比较 因为b和d不匹配 报告失败 回到A 看它是否还有别的选择尚未尝

12、试 在回到A时 必须重置指针于第二个符号 即第一次进入A的位置 现在尝试A的第二个选择 得 到图 c 的分析树 叶子a匹配W的第二个符号 叶子d匹配W的第三个符号 这样 产 生了W的分析树 从而宣告分析完全成功 2 1 3 左递归的消除 直接消除产生式中的左递归是比较容易的 假定关于非终结符P的规则为P Pa b 其中 P是开头 那么我们可以把P的规则改写为如下的非直接左递归形式 P bR R aR 为空字 这种形式和原来的形式是等价的 也就是说 从P推出的符号串是相同的 一般而言 假定P关于的全部产生式是P P 1 P 2 P m 1 2 n其中 每个 i 1 i m 都不等于 1 n都不以

13、P开头 那么消除P的直接左递归就是把这些规则改写 成 P 1R 2R nR R 1R 2R mR 使用这个方法 我们容易把见诸于表面的所有直接左递归都消除掉 也就是说 把直接左递归都改成直接右递归 对于间接左递归的消除需先通过产生式非终结符置 换 把间接左递归变成直接左递归 例如有文法 S A 1 A S 2 因为S A S 所以S是一个间接递归的非终结符 为了消除这种间接左递归 将 2 式代人 1 式 即可得到与原方法等价的方法 S S 3 3 式是直接左递归的 可以采用消除直接左递归的方法对文法进行改写 可的 编译原理 课程设计报告 4 文法 S S S S 由此可见 为了消除间接左递归

14、可首先查出那些具有左递归的非终结符号 然 后对以这些非终结符为左部的产生式 通过逐步置换有关产生式的方法将它们化为直 接左递归的产生式 最后在消除其中的全部直接左递归 2 1 4 消除回溯 提左因子 为了消除回溯就必须保证 对文法的任何非终结符 当要它去匹配输入串时 能 够根据它所面临的输入符号准确地指派它的一个侯选去执行任务 并且次侯选的工作 结果是确信无疑的 也就是说 若此侯选获得成功匹配 那么 这种匹配不会是虚假 的 若此侯选无法完成任务 则任何其它侯选也肯定也无法完成任务 换句话说 假 定现在轮到非终结符 A 去执行匹配任务 A 共有 n 个侯选 1 2 n 即 A 1 2 n A 能

15、够根据不同的输入符号指派相应的 i 作为全权代表去执行 任务 那就肯定无需回溯了 在这里 A 已不再是让某个侯选去试探地执行任务 而是 根据所面临的输入符号 准确地指派唯一的一个侯选 其次 被指派侯选的工作成 败也完全代表了 A 2 1 52 1 5 计算计算FIRSTFIRST集合 集合 FOLLOWFOLLOW集合和集合和SELECTSELECT集合集合 FIRST集合 令G S VT VN S P 则 FIRST a a a VT V 若 则 FIRST 对每以文法符号X 计算FIRST X 过程如下 a 若X VT 则FIRST X X b 若X VN 且有产生式X a a VT 则把

16、a加入到FIRST X 中 c 若X VN 若X 也是一条产生式 则把 也加到FIRST X 中 d 若X VN 有产生式X Y1Y2 Yn Y1 Yi都是非终结符 对于任何 j 1 j i 1 FIRST Yj 都含有 则把FIRST Yj 中的所有非 元素都加到 FIRST X 中 FIRST Yi 的元素加入到FIRST X 特别地 若所有的FIRST Yj j 1 2 n 均含有 则把 FIRST Yj 中的所有非 元素都加到FRIST X 中 FOLLOW集合 编译原理 课程设计报告 5 设G S VT VN S P 是上下文无关文法 a 设S为开始符号 则 FOLLOW S b 若有产生式A B 则FIRST FOLLOW B C 若 可理解为A B 则FIRST FOLLOW A FOLLOW B SELECT集合 A 的可选集SELECT 则SELECT A FIRST 则SELECT A FIRST FOLLOW A 2 22 2 解决问题的基本思路解决问题的基本思路 首先根据一定的规则输入一个合法的文法 化简成LL 1 文法 利用一定的算法消 除文法中的左递归 然后