LL(1)动作文法的编译器的自动生成器的设计与实现.doc

论文分类号 TP31 单 位 代 码 10183 密 级 内部 研 究 生 学 号 20015352033 吉 林 大 学 硕 士 学 位 论 文 LL 1 LL 1 动作文法的编译器的自动生成器的设计与实现动作文法的编译器的自动生成器的设计与实现 The Design and Implementation of LL 1 Action Grammar Compiler s Automatical Constructor 作者姓名 成作者姓名 成 会会 明明 专专 业 计算机软件与理论业 计算机软件与理论 导师姓名导师姓名 金金 成成 植植 及及 职职 称称 教教 授授 论文起止年月 论文起止年月 20032003 年年 1 1 月至月至 20042004 年年 4 4 月月 提提 要要 编译器的构造工具比如 YACC BISON 根据语言的高级描述生成语 言处理器 编译器 解释器 转换器 根据用户输入的语言的文法 编 译器的构造工具可以生成程序来处理以用户输入的文法书写的文本 随 着计算机应用范围的扩大 在软件自动生成 文档处理 特定专业的语 言等领域 编译器的构造工具这一技术显得越来越重要 类 YACC 的编译器的构造工具是基于 LALR 1 方法 这一方法在 时间和空间代价方面是有效的 而且所能解析的语言也覆盖了大部分语 言 因些大多数的编译器的编译器都是针对 LALR 1 的 而很少有针对 LL 1 文法的 本文所做的工作是用 VC 要建立一个针对 LL 1 文法的编译器的编 译器 本文以定义好的文法书写的文件作为输入 其中包括语法及语义 动作 鉴于输入文件的所用的文法可以用 LL 1 分析 于是对输入的文 件用递归下降的分析方法在内存中建立它的存储结构 然后分别计算所 输入的文法的非终结符号是否可以生成空 每个非终结符号的 first 集合 每个非终结符号的 follow 集合 以及每个规则的 predict 集合 接着判 断任意一个非终结符号的任意两个规则的 Predict 集的交集是不是都为 空 如果是则输入文法可以用递归下降法分析 否则不可以 用户应该 对所输入的文法作适当的修改 使其满足 LL 1 文法分析的要求 如果 所输入的文法可以用递归下降法分析 生成相应文法的语法分析程序 目录 1 目目 录录 第一章第一章 前言前言 1 1 1 1 编译器的结构 1 1 2 编译器的实现 3 1 3 主要完成的工作 5 第二章第二章 LL 1 LL 1 文法以及属性文法文法以及属性文法 6 6 2 1 LL 1 文法及其分析器 6 2 2 动作文法 8 第三章第三章 输入文件的结构及词法输入文件的结构及词法 1111 3 1 词法工具的使用说明 11 3 2 输入文件的语法结构 12 3 3 输入文件的词法结构及其实现 14 第四章第四章 系统设计与实现系统设计与实现 1818 4 1 规则的存储结构 18 4 2 建立规则的存储 19 4 3 非终结符推出空 20 目录 2 4 4 计算FIRST集 20 4 5 计算FOLLOW集 21 4 6 计算PREDICT集 21 4 7 判断是否 LL 1 21 4 8 输出文件中函数的格式 21 第五章第五章 实实 例例 2424 参考文献参考文献 3333 致致 谢谢 摘摘 要要 1 1 ABSTRACTABSTRACT 1 1 前言 1 第一章第一章 前言前言 1 1 编译器的结构 不同的编译器都有自己的组织和工作方式 它们都是根据源语言的 具体特点和对目标语言的具体要求来决定和设计出来的 因此 并没有 一种固定的编译器的结构 但从功能结构几乎都是一致的 这里说的功 能结构是指编译器内部都做哪些工作 以及它们彼此之间的关系 图 1 说明了一般的编译程序的功能结构 其中各部分完成的主要任务如下 词法分析 词法分析 根据语言的词法规则 扫描源程序的 ASCII 码序列 把它识别为一个一个具有独立意义的最小语法单位 即 单词 并识别出与其相关的属性 如标识符 界限符 常数等等 并 把每个单词的 ASCII 码序列替换为统一的标准形式 所谓的 目标程目标程 序序 词词 法法 分分 析析 语语 法法 分分 析析 语语 义义 分析分析 中间代码生成中间代码生成 中间代码优化中间代码优化 目标代码生成目标代码生成 源源 程程 序序 表表 格格 处处 理理 错错 误误 处处 理理 图 1 编译器的功能结构图 前言 2 机内表示 TOKEN 形式 这种形式既刻画了单词本身 又刻画 了它所具有的属性 同时完成词法错误的检查以及去掉注释等 词法分析阶段不依赖于语言的语法定义 语法分析 语法分析 根据语言的语法规则 逐一地扫描源程序的 ASCII 码序列或者是词法分析后的 TOKEN 序列 前者情形 词法分 析程序将作为语法分析程序的子程序 以确定它们是怎样构成 声明和语句的 以及声明和语句是怎样构成程序的 分析时如 发现有不符合语法规则的地方 则打印出错位置和错误类型 以便程序员进行修改 如果未发现语法错误 则将源程序转换 成能够表示程序结构的语法树的形式 很多编译程序在进行语 法分析的同时还要完成其他的工作 但要注意到如果语法有错 误那么其他工作也白做 语义分析 语义分析 根据语言的语义规则对语法分析得到的语法树进行 语义检查 确定类型 类型和运算的合法性检查等 并建立标 识符的符号表等各种信息表 如果有语义错误 则不用进行下 面的编译工作 只有当没有语义错误时才继续下面的编译过程 语义分为静态语义和动态语义 编译阶段一般只检查静态语义 而静态语义检查中重点是类型检查 中间代码生成 中间代码生成 扫描对象通常是语义分析后的结果 这一部分 把源程序的 TOKEN 序列转换成更接近于目标代码的中间代码 如三元式或四元式的序列 如果不搞优化 那么这部分的工 作可以不要 中间代码优化 中间代码优化 扫描对象是中间代码 任务是把原中间代码转 换成可产生高质量目标代码的中间代码 其中的优化工作包括 常表达式优化 公共子表达式优化 不变表达式外提和削减运 算强度等 前言 3 1 2 编译器的实现 编译程序是一个相当复杂的系统程序 通常有上万甚至几万条 指令 随着编译技术的发展 编译程序的开发周期也在逐渐缩短 但仍然需要很多人年 而且工作很艰巨 正确性也不易保证 要实 现一个编译程序 通常需要做到 1 对源语言的语法和语义要有准确无误的理解 否则难以保证编译 程序的正确性 2 对目标语言和编译技术也要有很好的了解 否则会生成质量不高 的目标代码 3 确定对编译程序的要求 如搞不搞优化 搞优化搞到哪一级 等 等 4 根据编译程序的规模 确定编译程序的扫描次数 每次扫描的具 体任务和所要采用的技术 5 设计各遍扫描程序的算法并加以实现 一般开发编译程序有如下几种可能途径 转换法 预处理法 假如我们要实现 L 语言 现在有 L 语言的编译器 那么可以 把 L 语言程序转换成 L 语言的程序 再利用 L 语言的编译器实 现 L 语言 这种方法通常用于语言的扩充 如把 C 程序转换成 C 程序 我们用 C 语言的编译器进行编译 常见的宏定义和宏使用都 属于这种典型 移植法 假设在 A 机器上已有 L 语言的编译程序 想在 B 机器上开发一 个 L 语言的编译程序 这里有两种实现方法 实现方法一 最直接的办法就是将 A 机的代码直接转换成 B 机 代码 前言 4 实现方法二 假设 A 机和 B 机上都有高级程序设计语言 W 的编 译程序 并且 A 机上的 L 语言编译程序是用 W 语言写的 我们可以 修改 L 编译程序的后端 即把从中间代码生成 A 机目标代码部分改 为生成 B 机的目标代码 这种在 A 机上产生 B 机目标代码的编译程 序称为交叉编译程序 Cross Compiler 自展法 实现思想 先用目标机的汇编语言或机器语言书写源语言的一 个子集的编译程序 然后再用这个子集作为书写语言 实现源语言 的编译程序 通常这个过程会分成若干步 像滚雪球一样直到生成 预计源语言的编译程序为止 我们把这样的实现方式称为自展技术 工具法 70 年代随着诸多种类的高级程序设计语言的出现和软件开发自 动化技术的提高 编译程序的构造工具陆续诞生 如 70 年代 Bell 试验室推出的 LEX YACC 至今还在广泛使用 其中 LEX 是词法分析 器的自动生成工具 YACC 是语法分析器的自动生成工具 然而 这 些工具大都是用于编译器的前端 即与目标机有关的代码生成和代 码优化部分由于对语义和目标机形式化描述方面所存在的困难 虽 有不少生成工具被研制 但还没有广泛应用 自动生成法 如果能根据对编译程序的描述 由计算机自动生成编译程序 是最理想的方法 但需要对语言的语法语义有较好的形式化描述工 具 才能自动生成高质量的编译程序 目前 语法分析的自动生成 前言 5 工具比较成熟 如前面提到的 YACC 等 但是整个编译程序的自动 生成技术还不是很成熟 虽然有基于属性文法的编译程序自动生成 器和基于指称语义的编译程序自动生成器 但产生目标程序的效率 很低 离实用尚有一段距离 因此 要想真正的实现自动化 必须 建立形式化描述理论 1 3 主要完成的工作 本文所做的工作是用 VC 要建立一个针对 LL 1 文法的编译器的编 译器 本文以定义好的文法书写的文件作为输入 其中包括语法及语义 动作 鉴于输入文件的所用的文法可以用 LL 1 分析 于是对输入的文 件用递归下降的分析方法在内存中建立它的存储结构 然后分别计算所 输入的文法的非终结符号是否可以生成空 每个非终结符号的 first 集合 每个非终结符号的 follow 集合 以及每个规则的 predict 集合 接着判 断任意一个非终结符号的任意两个规则的 Predict 集的交集是不是都为 空 如果是则输入文法可以用递归下降法分析 否则不可以 用户应该 对所输入的文法作适当的修改 使其满足 LL 1 文法分析的要求 如果 所输入的文法可以用递归下降法分析 生成相应文法的语法分析程序 LL 1 文法以及属性文法 6 第二章第二章 LL 1 LL 1 文法以及属性文法文法以及属性文法 2 1 LL 1 文法及其分析器 文法分析的基本问题之一是确定那些非终结符号导 空串 这一信 息很重要 因为可导出 空串 的非终结符号在语法分析的时候可能消失 可以 用以下算 法判定一个非终结符号是否可以导出 空串 设 S Lambda 表示可 导出 空串 的 非终结符号集 则求它的算法如下 1 令 S Lambda Aj Aj Production 2 对每一个产生式 p Ap X1 Xn 若 X1 Xn S Lambda 3 重复第二步的循环 直至 S Lambda 收敛为止 文法分析中最的用的技术是求以下种集合 终结符集 的技术 这三 种集合的具 体定义如下 其中 VN VT A VN First a VT a if then else Follow A a VT S Aa if S A then else Predict A First 当 First 不含有 First Follow A 当 First 含有 其中 表示输入的结束符号 first 表示 串所能推导的终极 符串的头终结符集 如果 能推导出空串 则令 First 包括 follow A 表示所有那些终结符的集合 这些终极在某个句型中出现在 A LL 1 文法以及属性文法 7 的紧后面 这种集合主要用于求 predict A 的集合 LL 1 语法分析方法是一种自顶向下的语法分析方法 它是 LL k 分 析方法的特例 其中的 k 表示向前看 k 个符号的意思 和递归下降法有 相同的问题 即在推导过程中如何唯一选择产生式的问题 因此 LL 1 语法分析方法与递归下降法一样对文法做了相同的限制 即 假设 A 的全部产生式为 A 1 2 n 则有 Predict A i Predict A j I j 有了上面的限制条件 可以保证选择产生式的唯一性 满足上面条 件的文法称为 LL 1 文法 LL 1 语法分析程序是由两部分组成的 第一部分是语法分析表 也称为 LL 1 分析矩阵 第二部分是语法分析驱动程序 LL 1 矩阵的作用是如何选择语法规则 它的行表是由所有非终极 符组成 它的列表是由所有终极符即特殊符号 结束符 矩阵的值有 两种 一种是产生式编号 另外一种是错误编号 其一般形式可定义为 LL A a k 其中 A Vn a Vt k 为规则编号 P 或错误编号 error k 设有规则 A k 若 a Predict A 那么有 LL A a k 若 a 不属于任何一个以 A 为左部的规则的 Predict 集 则 LL A a 错误编 号 LL 1 分析程序工作原理是首先初始化 即把开始符压入栈中 以 后的每步分析必为下面的四种情况之一 1 析栈的栈顶元素是终极符 则看其是否与输入流的头符相匹配 如果匹配成功 去掉栈顶元素 并读下一个单词 若匹配不成 功 则报错 LL 1 文法以及属性文法 8 2 栈顶是非终极符 则用栈顶和输入流的当前单词去查当前矩阵 如果查得的值是产生式编号 则把对应的产生式右部逆序压入 栈中 如果查得的值为错误信息 则报错 1 栈已空 输入流不空 这时输入流报错 2 若栈已空 输入流也空 则语法分析成功 由上可以看出 LL 1 语法分析驱动程序对于任何文法都是一样 的 所不同的是不同的文法 LL 1 矩阵是不相同的 所以构造 LL 1 语法分析程序关键是如何构造文法的 LL 1 矩阵 LL 1 的构造可以 是手工操作的 也可以是自动生成的 2 2 动作文法 编译器中语义分析和中间代码生成等部分是比较细致而复杂的 部分 因此希望能用比较规范抽象的方式把这些部分描述出来 当前 所用的主要方法是 把语义信息附加到文法中 使得它既描述文法 同 时还指出动作信息 这种描述方法不仅能简化细节并增强可读性 而 且可自动化 动作符 Action Symbol 动作符主要用于构造动作文法 它可以出现于产生式中 但没有任何 语法意义 而且 能出现于具体程序中 由于它不起任何语法作用 所以 必须与实际的语法符号 相区别 比如动作符号的结构可定义成 Name 的形式 其中 表示是非语法符号 并且 Name 是某种形式的字符串 具体 规定可由具体系统来定义 动作符可出现于产生式右部的任何地方 其主要作用是用来 指明某 种语义动作 即动作符 Name 中的 Name 代表某语义子程序 因此在使用 动作符时必须给出每个动作符所对应的语义子程序 动作符的作用对 LL 分析显得十分突出 如果想用 LL 分析法 那么 Yacc 就无能为力 但 动作文 法可方便地被应用 如果把 Yacc 说成是针对 LR 分析的 那么 把动作文法说成是针对 LL 分析的 也并不过份 形式上说 动作文法是这样一种文法 即在产生式的右部带动作符 其 LL 1 文法以及属性文法 9 中动作符可出现于产生式右部的任何地方 包括产生式右部的开始和尾 部 动作文法中的每个动作符号都有相应的语义子程序 因此 动作符实 际上是一个无参过程的子程序名字 在什么地方插入动作符以及动作符 所对应的子程序应写成什么样子 完全由用户决定 动作文法的主要用途是描述语义动作 作为例子考虑下面文法 L D L D a b 显然 L 代表的由 a 和 b 组成的串或空串 我们要构造的是这样一 个语义处理器 它将输入 L 串并将其中 b 的个数打印出来 因为处理方式可以有 多种 动作文法也可以有多种 我们考虑这样一种方案 即开始令 S 0 以后每输入一个 b 就作 S S 1 当结束输入时将 S 的值打印出来 下面是按上述思想写出来的 动作文法 L D L L Out D a D b Add 其中动作符有 Add 和 Out 它们所对应的动作子程序分别如下 Add S S 1 Out Print S 假定给定 L 串 bab 则用 LL 分析法实现上述动作文法的过程如下 在运行前令 S 0 并把开始符压入语法分析栈 之后进行 LL 分析 此时每当动作符成为栈顶符号时 将执行相应的动作子程序 具体 实现过程如下图 LL 1 文法以及属性文法 10 SyntexStack InputStreamAction L Bab DL Bab BLBab LAb S S 1 LAb DLAb ALAb Lb DLb BLb L S S 1 L Print S 输入文件的结构及词法 11 第三章第三章 输入文件的结构及词法输入文件的结构及词法 3 1 词法工具的使用说明 Flex 是 Lex 的的改进版本 Lex 是词法分析器的自动生成工具 它 从基于正规式的专门表示构造词法分析器 并已广泛用于说明各种语言 的词法分析器 Flex 程序包括三个部分 声明 翻译规则 辅助过程 声明部分包括变量 显明常量和正规定义 显明常量是表示常量的 标识符 Flex 程序的翻译规则为形如 P1 动作 1 P2 动作 2 Pn 动作 n 的语句 这里 每个 Pi 是正规式 每个动作 i 是描述模式 pi 匹配 单词时词法分析器应执行的程序段 第三部分包括了动作所需要的辅助过程 这些过程也可以分别编译 然后和词法分析器一同装入 由 Flex 建立的词法分析器和分析器联系的方式是 词法分析器被 分析器激活时 开始逐个字符地读它的剩余输入 直到它发现能和正规 式 pi 匹配的输入的最长前缀为止 然后执行动作 i 典型的 动作 i 将把控制返回分析器 如果不是这样 词法分析器继续寻找下面的单词 直到有一个动作引起控制回到分析器为止 这种重复的搜索单词 直到 显示的返回的方式允许词法分析器方便的处理空白和注解 输入文件的结构及词法 12 词法分析器仅返回一个值 记号 给分析器 为了传递记号的属性 值 可以将值置于全程变量 yylval 中 3 2 输入文件的语法结构 下面是用户输入的动作文法所采用的语法结构 并且该文法可以 用 LL 1 方法分析 grammar global prelude part token declaration part rule part global prelude part global prelude empty global prelude prelude block global prelude 主要包括动作文法中的动作要用到的数据结构 函数过程 全局变量 预定主常量 block c code block 主要生成动作文法中要加入的语义动作 以及一个非终结符号的 local prelude empty token declaration part token token declaration list empty token declaraton list token declaration tail token declaration list token declaration token declaration identifier rule part rule list 输入文件的结构及词法 13 rule list rule rule list rule rule left hand side right hand side left hand side nonterminal formal parameter spec nonterminal identifier formal parameter spec empty in 参数用于值传参数 out参数用于引用传递 parameter spec list parameter spec parameter spec list parameter spec parameter spec parameter type parameter name parameter type identifier parameter name parameter name right hand side local prelude option alternative list local prelude option local prelude empty local prelude prelude block local prelude的内容插入到处理左边的非终结符号的函数的开头部分 alternative list member list member list member member list member item item symbol literal semantic action symbol symbol name actual parameters option symbol name identifier actual parameters option actual parameters empty actual parameters actual parameter list actual parameter 输入文件的结构及词法 14 actual parameter list actual parameter literal char constant semantic action block 3 3 输入文件的词法结构及其实现 输入文件的词法结构主要包括两部分 一部分是用户输入的规则的 所用到的词法 另一部分是语义动作用到的词法 语义动作用到的词法 是 C 语言所使用的词法 当在处理用户输入的动作文法的时候 如果遇到 了 表明遇到了 C 语言块 对 的计数加 1 转入到 C 语言的词法分析部 分 在 C 语言的词法分析部分 若遇到单词 对 的计数加 1 若遇到 则对 的计数减 1 如果些时计数为零 切换词法分析程序所匹配的规则到 文法所用的规则 下面举个例子来说明使用方法 刚打开文件匹配的时候 匹配的是前 面没有四个规则 当匹配到 时 执行 BEGIN qq 是就开始匹配前面 带有的规则 如果遇到 执行 BEGIN 0 后面接着开始匹配前面没 有的规则 x qq prelude return 90 token return 100 BEGIN QQ A Za z 输入文件的结构及词法 15 return 101 return 102 return 103 return 104 return 105 BEGIN 0 下面是读用户输入文件的词法 为了对用户输入文件出现错误的地方 进行定位 需要在匹配完每个单词要对当前的单词在文法中的位置进行 定位 其中 yyleng 是当前匹配单词的长度 column 是当前的列 position 是当前匹配的字符串在文件中的位置 规则部分前面加的部分是用来 c 语言的词法 前面不加的是规 则的词法 x cc ccc prelude printf word s length d yytext yyleng 输入文件的结构及词法 16 position position yyleng column column yyleng return PRELUDE A token position position yyleng column column yyleng return TOKEN A position yyleng column yyleng right curly 1 BEGIN cc return LEFT CURLY auto position yyleng column yyleng break position yyleng column yyleng case position yyleng 输入文件的结构及词法 17 column yyleng position yyleng column yyleng right curly if right curly 0 BEGIN 0 回到原来的部分 return RIGHT CURLY 系统设计与实现 18 第四章第四章 系统设计与实现系统设计与实现 4 1 规则的存储结构 下面这个数组结构存储的是一个非终结符号所对应的所有的规则 class CRule public in parameters out parameters 这个非终结符号所对应输入与输出 参数集合 in parameters 是值参 out parameters 是引用参数其 中每个数 组的第 i i 2 0 表示类型 i 2 1 表示这个串是参数名 CStringArray in parameters out parameters int initialized 表示这个非终结符号名字 CString nonterminal 指针数组 每个指针指向一个 CObList 对象 每个对象存储这个非 终结符号的一个规则 CPtrArray right parts 这一规则所对应的 local prelude block 在文件中的定位 如果这 两个值为 1 的话 就是说这个非终结符没有这样 local prelude block 否 则有 int local prelude block begin position int local prelude block end position int local prelude block begin line int local prelude block begin column p i 0 1 2 分别表示当前的计算结果第 i 个规则未知能否生成空 能 生成空 不能生成空 int status 当前已有多少个规则已有确定的结果 系统设计与实现 19 int finished rules select set i 表示这个非终结符号的第 i 个规则的 select 集 CDWordArray select class CRightSymbol 这个数组结构用来存储规则右部的一个符号的信息 public 表示这个类存储的是字符 语义动作 还是 TOKEN A 用户定义 的符号串常量 CHARACTER SEMANTIC ACTION int type 存储一个非终结符号可能的参数 CStringArray actual parameters 如果类型是语义动作 存储在文件中的起始与结束地址 int semantic action begin line semantic action begin column int semantic action end line semantic action end column int semantic action end position int semantic action begin position 如果是 token 和非终结符时所对应的值 也有可能是一个终结字 符 int value 4 2 建立规则的存储 根据计算可得输入文件的文法是满足 LL 1 分析方法的文法 对该 文法写一个递归下降分析程序 建立对这些规则的存储 4 3 非终结符推出空 1 初始化所有的非终结符号以及每个非终结符号的所有规则未知其 系统设计与实现 20 能否生成空 2 置迭代标志为 1 i 0 3 如果迭代标志为 1 转 4 否则计算结束 4 如果第 i 个非终结符号已计算得到能生成空或生不成空则转 6 5 分析第 i 个非终结符号的每一个没有确定其是否能生成空的规则 如果这个规则右部为空 或全部是已确定能推出空的非终结符号 则标记 第 i 个非终结符号可以生成空 并置迭代表记为 1 转 6 如果这个规则的分 析中遇到了非终结符号或遇到了已确定不能生成空的非终结符号 则标 记该规则不能推出空 当这个规则第 i 个非终结符号的最后一个不能确定 生成空的规则 则标记第 I 个非终结符号不能生成空 转 6 6 i i 1 如果 i rules GetSize 转 3 否则转 4 4 4 计算 first 集 1 初始化所有的非终结符号的 first 集为空 2 置 changed 1 3 如果 changed 为 1 转 4 否则转结束 4 changed 0 i 0 5 如果 i rules GetSize 转 6 否则转 3 6 从左到右分析第 i 个非终结符号的每个规则的右部 如果遇到一 个终结符号 则把这个非终结符号加到第 i 个非终结符号的 first 集中 加 入后若改变这个非终结符号 first 集则置 changed 为 1 接着分析其它规则 如 果遇到一个非终结符号则把这个非终结符号的 first 集并到第 i 个非终结 符号的 first 集当中 此时若改变了第 i 个非终结符号的 first 集置 changed 为 1 若这个规则可以导出空 则继续分析这个规则的后面的符号 7 i i 1 转 5 4 5 计算 follow 集 1 初始化所有的非终结符号的 follow 集为空 2 置 changed 1 系统设计与实现 21 3 如果 changed 为 1 转 4 否则计算结束 4 changed 0 i 0 5 如果 i rules GetSize 转 6 否则转 3 6 从左到右分析第 i 个非终结符号的每个规则的右部 对于在这个 规则右部的每一个非终结符号 1 计算这个符号后面符号串的 first 集 把 它并入到这个符号的 follow 集 如果并运算改变了这个符号的 follow 集 则置 changed 为 1 2 计算这个符号后面的符号串能否推出空 若能推出 空 则把第 i 个非终结符号的 follow 集并入到这个非终结符号的 follow 集 如果改变了这个非终结符号的 follow 集 则置 changed 为 1 7 i i 1 转 5 4 6 计算 predict 集 每个规则的 predict 计算如下 如果这个非终结符号右部的串能导 出空 则这个规则的 predict 集为这个规则左部非终结符号 follow 集并上 这个规则右部串的 first 集 并去掉空串 如果这个规则的右部导不出空 则 这个规则的 predict 集为这个规则右部串的 first 集 4 7 判断是否 LL 1 计算任意一个非终结符号的任意两个规则的 predict 集的交集是不 是为空 如果存在某一个非终结符号的某两个规则的 predict 集的交集 为不为空 则该文法不能用 LL 1 方法分析 4 8 输出文件中函数的格式 下面是某动作文法系统中的一条规则 假设计算所得 select expr list expression expr tail IDENTIFIER NUM select expr list B expr list 系统设计与实现 22 p writeparameter P WRITEPARAMETER new struct writeparameter P EXPRESSION P WRITEPARAMETER expression expr tail p writeparameter NULL 处理这个非终结符号所对应的程序如下 int expr list P WRITEPARAMETERp writeparameter int P EXPRESSION P WRITEPARAMETER ret expression p expr tok if ret 0 return 0 ret expr tail p write parameters tail tok if ret 0 return 0 return 1 根据 select 选把规则 2 系统设计与实现 23 if tok B p writeparameter NULL return 1 return 0 如果参数 tok 不属于这个非终结符任何一个规则的 select 集 就出错 实 例 24 第五章第五章 实实 例例 下面这个例子输入的是一个语言动作文法 该动作文法是要建立对这 个文法的语言在内存中的存储 以便作更进一步的处理 一个这样的 文件是用一个语句链表存储 读语句的参数是用一个字符串数组存储 write 语句的表达式序列用表达式链存储 prelude struct expression char op 0 integer 1 variable name or union struct expression left right two sub expressions int value constant CString var name variable name node 用来存储一个表达式 typedef struct expression EXPRESSION P EXPRESSION struct writeparameter P EXPRESSION p expr struct writeparameter next typedef struct writeparameter WRITEPARAMETER P WRITEPARAMETER struct assign CString id struct expression p exp typedef struct assign ASSIGN 实 例 25 struct statement int type 0 read 1 write 2 assign union CStringArray parameters parameters of read ASSIGN assign assign sentence P WRITEPARAMETERS p writeparameters value struct statement next typedef struct statement STATEMENT P STATEMENT token BEGIN END READ WRITE IDENTIFIER NUM program BEGIN statement list END statement list statement P STATEMENT statement tail statement tail statement P STATEMENT statement tail p statement NULL 实 例 26 statement IDENTIFIER p statement new struct statement p statement type 2 p statement value assign id Copy yytext P EXPRESSION expression READ p statement new struct statement p statement type 0 read sentence CStringArray id list WRITE p statement new struct statement p statement type 1 write sentence P WRITEPARAMETER expr list id list IDENTIFIER parameters Add yytext id tail id tail IDENTIFIER 实 例 27 parameters Add yytext id tail expr list p writeparameter P WRITEPARAMETER new struct writeparameter P EXPRESSION P WRITEPARAMETER expression expr tail expr tail p writeparameter new WRITEPARAMETER P EXPRESSION P WRITEPARAMETER expression expr tail p writeparameter NULL expression P EXPRESSION p temp P EXPRESSION p temp1 实 例 28 primaryprimary tail primary tail prelude P EXPRESSION p temp1 p temp2 p temp3 add op primary primary tail if p temp3 NULL p tmep1 node right p temp2 p expr p temp1 else p temp3 node left p temp2 p temp1 node right t temp3 p expr p temp1 p expr NULL primary IDENTIFIER p expr P EXPRESSION new struct expression p expr op 1 variable name p expr node varname Copy yytext 实 例 29 NUM p expr P EXPRESSION new struct expression p expr op 0 integer p expr node value atoi yytext expression add op p exp P EXPRESSION new struct expression p exp op p exp P EXPRESSION new struct expression p exp op 计算可得该动作文法可以用 LL 1 方法分析 下在这个函数是由系 统自动生成的一个函数 这个函数用来处理非终结符 statement 的规则 int statement P STATEMENTp statement int tok yylex p statement new struct statement 实 例 30 p statement type 2 p statement value assign id Copy yytext P EXPRESSION if tok return 0 tok yylex if tok return 0 tok yylex ret expression p exp tok if ret 0 return 0 if tok return 0 tok yylex return 1 if tok READ 当前要处理的语句是读语句 if tok READ return 1 tok yylex p statement new struct statement p statement type 0 read sentence CStringArray if tok return 0 tok yylex ret id list parameters tok if ret 0 实 例 31 return 0 if tok return 0 tok yylex if tok return 0 tok yylex return 1 if tok WRITE 当前要处理的语句是写语句 if tok WRITE return 1 tok yylex p statement new struct statement p statement type 1 write sentence P WRITEPARAMETER if tok return 0 tok yylex ret expr list p writeparameter tok if ret 0 return 0 if tok return 0 tok yylex if tok return 0 tok yylex 实 例 32 return 1 return 0 参考文献 33 参考文献参考文献 1 ISBN 7 04 007492 3 金成植 高等教育出版社 2001 6 第二版 2 ISBN 7 312 00889 5 陈意云 中国科学技术大学 出版社 1997 12 3 程序设计语言编译原理 ISBN 7 118 02207 1 陈火旺 刘春林 谭庆平 赵克佳 刘越 国防科技大学出版社 吉林大学硕士学位论文原创性声明吉林大学硕士学位论文原创性声明 本人郑重声明 所呈交的硕士学位论文 是本人在指导教师 的指导下 独立进行研究工作所取得的成果 除文中已经注明引 用的内容外 本论文不包含任何其他个人或集体已经发表或撰写 过的作品成果 对本文的研究做出重要贡献的个人和集体 均已 在文中以明确方式标明 本人完全意识到本声明的法律结果由本 人承担 学位论文作者签名 日期 年 月 日 中国优秀博硕士学位论文全文数据库中国优秀博硕士学位论文全文数据库 投投 稿声明稿声明 研究生院 本人同意 中国优秀博硕士学位论文全文数据库 出版 章程的内容 愿意将本人的学位论文委托研究生院向中国学 术期刊 光盘版 电子杂志社的 中国优秀博硕士学位论文 全文数据库 投稿 希望 中国优秀博硕士学位论文全文数 据库 给予出版 并同意在 中国博硕士学位论文评价数据 库 和 CNKI 系列数据库中使用 同意按章程规定享受相关 权益 论文级别 硕士 博士 学科专业 论文题目 作者签名 指导教师签名 年 月 日 作者联系地址 邮编 作者联系电话 致致 谢谢 本文是在我的导师金成植教授的精心指导下完成的 金老师严谨的治学态度和孜孜不倦的学风对我影响至深 令我终身 难忘 在论文期间 金老师的谆谆教诲和一丝不苟的敬业精神不仅对我 论文的完成起了很大的督促作用 而且对我今后的生活 工作和学习必 将产生至关重要的影响 正是在金老师的严格要求和全身心的帮助下 才使我的理论水平和实践能力有了较大的提高 在论文完成之际 谨向 我和导师致以深深的谢意和崇高的敬意 同时还要向刘磊教授表示衷心的感谢 刘老师对我的论文进展情况 很关心 经常提出宝贵的意见 并在各方面都给予了极大的帮助 刘老 师对事物的洞察力和对新事物和新技术的敏锐嗅觉 一直是我学习的榜 样 感谢我的家人和朋友对我的关心和支持 没有他们的鼓励和支持 我的论文就不会圆满的完成 最后 谨向其他所有帮助过我的老师和同学表示衷心的感谢 1 摘摘 要要 编译器的构造工具比如 YACC BISON 根据语言的高级描述生成语 言处理器 编译器 解释器 转换器 根据用户输入的语言的文法 编 译器的构造工具可以生成程序来处理以用户输入的文法书写的文本 这 一程序把输入文本解析成短语 对每个短语 你可以附加上语义动作 在软件自动生成 文档处理 特定专业的语言等领域 编译器的构造工 具这一技术显得越来越重要 类 YACC 的编译器的构造工具是基于 LALR 1 方法 这一方法在时 间和空间代价方面是是很节省的 而且所能解析的语言也覆盖了大部分 语言的语法 因此大多数的编译器都是针对 LALR 1 的 而很少有针对 LL 1 文法的 本文所做的工作是用 VC 要建立一个针对 LL 1 文法的编译器 本 文以定义好的文法书写的文件作为输入 其中包括语法及语义动作 鉴 于输入文件的所用的文法可以用 LL 1 分析 于是对输入的文件用递归下 降的分析方法在内存中建立它的存储结构 然后分别计算所输入的文法 的非终结符号是否可以