华北电力大学编译课程设计报告书

1 课程设计报告课程设计报告 2011 2012 年度第 1 学期 名 称 编译技术课程设计 B 题 目 词法分析器设计 算符优先分析程序设计 基于算符优先分析方法的语法制导翻译程序设计 院 系 计算机系 班 级 网络 学 号 学生姓名 指导教师 岳燕 黄建才 设计周数 1 周 成 绩 日期 2012 年 1 月 6 日 1 一 课程设计的目的与要求一 课程设计的目的与要求 1 词法分析器设计的目的与要求 1 1 词法分析器设计的目的 实验是为计算机科学与技术专业的学生在学习 编译技术 课程后 为加深对课堂教 学内容的理解 培养解决实际问题能力而设置的实践环节 通过这个实验 使学生应用编 译程序设计的原理和技术设计出词法分析器 了解扫描器的组成结构 不同种类单词的识 别方法 能使得学生在设计和调试编译程序的能力方面有所提高 为将来设计 分析编译 程序打下良好的基础 1 2 词法分析器设计的要求 设计一个扫描器 该扫描器是一个子程序 其输入是源程序字符串 每调用一次识别 并输出一个单词符号 为了避免超前搜索 提高运行效率 简化扫描器的设计 假设该程 序设计语言中 基本字 也称关键词 不能做一般标识符用 如果基本字 标识符和常数 之间没有确定的运算符或界符作间隔 则用空白作间隔 单词符号及其内部表示如表 1 1 所示 单词符号中标识符由一个字母后跟多个字母 数字组成 常数由多个十进制数字组成 单词符号的内部表示 即单词的输出形式为二元 式 种别编码 单词的属性值 表 1 1 单词符号及其内部表示 单词符号种别编码单词的属性值 BEGIN IF THEN ELSE END 标识符 整型常数 1 2 3 4 5 6 7 8 9 10 11 12 在名字表中的地址 十进制整数 2 2 算符优先分析程序设计的目的与要求 2 1 算符优先分析程序设计的目的 本实验是为计算机科学与技术专业的学生在学习 编译技术 课程后 为加深对课堂 教学内容的理解 培养解决实际问题能力而设置的实践环节 通过这个实验 使学生应用 编译程序设计的原理和技术 设计 编写和调试算符优先分析程序 了解算符优先分析程 序的组成结构 掌握实现通用算符优先分析算法的方法 能使得学生在设计和调试编译程 序的能力方面有所提高 为将来设计 分析编译程序打下良好的基础 2 2 算符优先分析程序设计的要求 算符优先分析属于自下而上的分析方法 该语法分析程序的输入是终结符号串 即单 词符号串 以一个 结尾 如果输入串是句子则输出 YES 否则输出 NO 和错 误信息 算符优先分析过程与非终结符号无关 当由文法产生了优先关系之后文法也就失去了 作用 本题目给出文法的目的是为了便于对语法分析结果进行验证 1 文法文法 设算符优先文法为 G TTEE FFTT PFPF iEP 说明 i 为整型常数或者为标识符表示整型变量 使用中 用 表示 2 优先关系表优先关系表 设优先关系表如表 1 2 所示 表 1 2 优先关系表 i i 3 3 基于算符优先分析方法的语法制导翻译程序的设计的目的和要求 3 1 基于算符优先分析方法的语法制导翻译程序的设计的目的 本实验是为计算机科学与技术专业的学生在学习 编译技术 课程后 为加深对 课堂教学内容的理解 培养解决实际问题能力而设置的实践环节 通过这个实验 使 学生应用编译程序设计的原理和技术 通过设计 编写和调试语法制导翻译程序 掌握 从一种语句的语法和语义出发 构造相应的语义子程序 实现基于算符优先分析方法 的语法制导翻译的方法 能使得学生在设计和调试编译程序的能力方面有所提高 为 将来设计 分析编译程序打下良好的基础 3 2 基于算符优先分析方法的语法制导翻译程序的设计的要求 算符优先分析方法是通过反复把输入符号移进分析栈 使用优先关系表在分析栈顶寻 找最左素短语 将其归约为一个非终结符号而实现的 这个分析过程与非终结符号无关 当由文法产生了优先关系之后文法也就失去了作用 所以本题目无需给出文法 基于算符优先分析方法的语法制导翻译是在算符优先语法分析的基础上进行翻译工作 即语义分析 每当将一个最左素短语归约为一个非终结符号时 就调用对应产生式的语 义子程序 去完成相应的语义翻译工作 这步归约使用的产生式对非终结符号不加区分 即将所有的非终结符号用一个通用的非终结符号表示 语法制导翻译程序的输入是终结符号串 即单词符号串 以一个 结尾 如果输 入符号串是句子 则按照其语义进行翻译 输出等价的四元式序列 作为练习应显示输出 二 课程设计正文二 课程设计正文 1 词法分析器设计 1 1 设计思想 对输入的字符串逐个分类处理 若所取字符为字母 检验其是关键字或标识符 返回其种别码 标识符还要记录其在名字表中地址并输出 若所取字符为数字 记录 其在常数表中的位置 返回种别码及其位置 若所取字符是运算符 返回其相应的种 别码 1 2 使用的相关函数及变量 1 void scanner 在这个函数部分进行单词符号的识别 开始进行第一次扫描的 时候 对数组 token 进行初始化 然后 ch 得到输入的字符串的第一个字符 对 ch 进行 判断 a 若 ch 是字母 则将 ch 存入 token 数组 然后指针 p 和指针 m 向后移动 ch 一直在 变化 一直将 ch 存入 token 直到 ch 不是字母或者数字的时候 然后分析 token 存 入的单词 将该单词和关键字进行比较 若是关键字 则输出 关键字在 table 中 4 的的位置 若不是关键字则当做标识符来处理 b 若 ch 是数字 则当做常数处理 c 若 ch 是 则单独处理 2 isdigit ch 用来判断 ch 中存放的是否是数字型字符 3 isalpha ch 用来判断 ch 中存放的是否是字母型字符 4 void main 用来输入要进行识别的语句 5 token 8 字符数组 存放构成单词符号的字符串 6 prog 80 字符数组 存放所有用户输入的字符 7 syn 整数 存放当前单词的种别码 8 sum 存放无符号整数 2 算符优先分析程序设计 2 1 设计思想 1 首先建立 char Terminal 7 2 pop 出栈函数 3 change char ch 将字符转为数字 以得到算符优先值 4 fenxi 比较函数 比较字符优先级并产生相应四元式 三 课程设计总结或结论三 课程设计总结或结论 1 词法分析器设计 词法分析在此次课设中相对容易 所需识别的单词符号比较少 难点在于关键字 与标识符的区别 设计时借助字符数组 char rwtab 6 begin if then else end 将存入 token 的字符与之比较 若匹配 则返回二元组 若不匹配 则作为标识符处理 扫描时 不同的情况赋予相应的扫描码 用 syn 记录 在输出时 利用扫描码编号进 行输出 switch syn case 7 printf d d n syn b break 输出常量 case 6 printf d d n syn a break 输出标识符 case 1 break 错误时跳转 case 0 break 结尾时的 default printf d n syn 输出其余运算符 实验心得 实验心得 在做实验时 我觉得首先要明白关键字 标示符 常数 运算符和分界符的区别 进 而再去写出算法将他们分开 我解决此问题用的方法是 先开始在自己编写函数 但是通 过看一些编程书 我发现 include ctype h 这个头文件里包含了我所要用到的 int isdigit int ch 和 int isalpha int ch 用上之后 是我的程序相对简洁了好多 程序本身用完全独立模 式 通过指针 j 和 k 的加减来实现超前搜索 通过数组 token 和其指针实现最长匹配 在输 出种别码和属性方面 实现定义好 编程中还有一个问题就是 的问题 这就用到超 前搜索了 先判断是否为 在内层循环中判断 如果只是小于 则指针退回 改变 相应的种别码和属性 但是最后在错误处理方面 只是报错 并没有指明是哪个错误 所 以我觉得这个程序还是可以完善的更好的 通过这次课设 我对之前学过的内容有了更深 的理解 了解了扫描器的组成结构 不同种类单词的识别方法 如何设计 编制并调试词 法分析程序 加深了对词法分析原理的理解 熟悉了构造词法分析程序的相关原理 使用 6 C 直接编写词法分析程序 另外 也让我重新熟悉了 C 语言的相关内容 加深了对 C 语言的头文件的用途的理解 2 算符优先分析程序设计 算符优先文法的程序设计最重要的函数是 void analy char tmp 分析函数 此函数将 传入的字符串逐个分析 与算符优先关系表比对 if cmp syn s j ch cmp syn s j ch 移进操作 for int h 0 h k h cout s h cout t t ch t tmp1 移进 endl if ch if Is Vt s j 1 1 j else j j 2 while cmp syn s j str cmp syn s j str 格式输出 for int h 0 h k h cout s h cout t t ch t tmp1 归约 时 进行归约操作 实验心得 实验心得 用过本次试验我明白了 算符是一种自下而上的分析方法 它借助某种优先关系寻找 可规约串进行规约 但是这种规约不是严格的最左规约 所以它不是一种规范规约 对于 算符优先文法 该程序的主要难点在于何时规约和何地规约 以及规约前后对几个指针位 7 置的处理 在实验编程中 存在几个问题 首先构造算符优先关系表 没有优先关系用 表示 其次 在移进和规约的编写时 要用到前面通过 syn i j 返回的符号进行查找 最后 我又添加了一个标志位 程序执行成功标志位不变 否则 标志位置 1 输出有错 编程 中一些小的问题通过百度都改了 总体来说比较具体的 通过这次实验 我了解了算符优 先分析器的组成结构以及对文法的要求 加深了对算符优先程序有了比较深的理解 在实 验过程中遇到了一些问题 但是通过自己的思考 最终得以解决 在一定程度上提高了软 件开发能力 3 基于算符优先分析方法的语法制导翻译程序的设计 主要部分归约的程序设计如下 if curcmp i 当前比较为 i 出栈一次 pop d w a w push F 归约到 N k 1 else 当前比较不为 i 出栈三次 pop pop b w pop c w push F 归约到 N k 1 if x 0 cout endl 产生的四元式为 b a d T x else cout endl 产生的四元式为 b a T x 1 T x x 8 实验心得 实验心得 开始设计这个程序的时候 还不太清楚什么时候产生四元式 以什么方式产生四元式 通过看书 我发现四元式的产生一般都是在有中间变量 回填 对运算符的规约的时候 用栈这个数据结构来实现输入缓冲区 当前比较串存放区和四元式的存放和输出 通过百 度知道 Lchar malloc sizeof LLchar 这个 C 内部集成的函数 Malloc 向系统申请分配指 定 size 个字节的内存空间 返回类型是 void 类型 在后面用到了很多 用 a 和 b 代表四 元式中的变量 在程序中已经返回 最后 每当规约要产生相应的四元式时便紧随之产生 就不在后面重新列出四元式列表 通过本次实验 对于基于算符优先分析方法的语法制导 翻译我有了更深一步的认识 语法制导翻译中的表示中间代码的四元式的这种结构是很有 其特点和优势的 这次实验基本达到了实验目的 但是在试验中也遇到了很多编程上的困 难 在以后学习中要更加努力 关于语法制导的内容之前未在课堂上有学过 首先锻炼了我的自学能力 通过学习和 实践掌握了从一种语句的语法和语义出发 构造相应的语义子程序 实现语法制导翻译的 方法 四 参考文献四 参考文献 1 陈火旺 刘春玲 程序设计语言 编译原理 国防工业出版社 2 宋雨 程晓荣 计算机综合实践指导 清华大学出版社 9 附录 设计流程图 程序 运行结果等 附录 设计流程图 程序 运行结果等 一 流程图 1 词法分析器 开始 结束 初始化 读入需要分析的句子 还有单词未分析 否 是 是字母 是 否 其他单词分析程序 是数字 否 输出单词二元式 关键字或标识 符分析程序 读一个字符 是常数分 析程序 10 2 算符优先文法 y y n n Y