1、 编译原理课程设计编译原理课程设计 LL(1)LL(1)文法判定文法判定 -c c 语言实现语言实现 2006 年 3 月 6 日 目 录 第一章 前 言 1 1.1 LL(1)文法概述 1 1.2 设计思想概述. 1 第二章 语言文法规则 1 2.1 语言的词法规则. 1 2.2 语言的语法规则. 2 第三章 程序设计 2 3.1 词法分析程序的实现. 2 3.1.1 文法输入规则 2 3.1.2 数据结构 2 3.1.3 程序流程 4 3.2 求解 FIRST 集、FOLLOW 集和 SELECT 集的实现 . 5 3.2.1 求出能推出的非终结符. 5 3.2.2 求解产生式的右部的 F
2、IRST 集. 6 3.2.3 求解非终结符的 FOLLOW 集 7 3.2.4 求解产生式的 SELECT 集 7 3.3 判定是否是 LL(1)文法的实现 . 7 3.4 预测分析表的生成实现. 7 3.5 判定给定符号串是否是文法中的句子的实现. 8 第四章 系统运行及测试 9 4.1 运行和安装环境. 9 4.2 系统运行. 9 4.2 系统测试. 9 4.2.1 测试一. 9 4.2.2 测试二 10 第五章 结 论 11 5.1 系统结论 11 5.2 存在的不足 12 参考文献. 12 附 录. 13 源程序. 13 1 第一章 前 言 本设计使用 C 语言实现了对简单方法描述的
3、 LL(1)文法的判定。 该设计程序 实现了：分别求出每一产生式的右部的 FIRST 集、每一个非终结符的 FOLLOW 集和每一产生式的 SELECT 集；判定是否是 LL(1)文法；画出预测分析表； 对给定的符号串判定是否是文法中的句子，分析过程用计算机打印出来。 1.1 LL(1)文法概述 LL(1)文法是一种 2 型文法，由它所描述的语言可以使用自顶向下语法分析 方法进行语法分析。LL(1)文法的含义是：第一个 L 表明自顶向下分析是从左向 右扫描输入串，第二个 L 表明分析过程中将用最左推导，1 表明只需向右看一个 符号便可决定如何推导即选择哪一个产生式（规则）进行推导。 一个上下文
4、无关文法（即 2 型文法）是 LL（1）文法的充分必要条件是，对 每个非终结符 A 的两个不同产生式，A，A，满足 SELECT（A）SELECT（A）= 其中、不同时能 * 1。 1.2 设计思想概述 首先对输入的文法进行词法分析，识别出所有的文法符号（终结符和非终 结符）并对其编码生成相应 ID，同时用单链表型数据结构存储单个产生式，产 生式的文法符号在单链表中以其相应 ID 表示，即所有的产生式以规定形式存储 在一个单链表集中。第二步，针对单链表型数据结构，设计相应算法计算出每一 个表达式右部的 FIRST 集、每一非终结符的 FOLLOW 集和每一产生式的 SELECT 集，其结果均以
5、单链表集的形式存储。最后，由求出的 SELECT 集经由相应算法 判定出该输入文法是否为 LL(1)文法，若是，则在屏幕上输出预测分析表，并对 给定的符号串判定是否是文法中的句子，分析过程用计算机打印出来。 第二章 语言文法规则 2.1 语言的词法规则 为简单起见，本设计规定非终结符集 VN为所有大写字母的集合，终结符集 VT为所有小写字母、 数字和四则运算符号的集合， 取所有文法符号均为单个字符。 2 2.2 语言的语法规则 由 2 型文法的定义，定义如下： 设 G=（VN，VT，P，S） ，若 P 中的每一个产生式满足： 是一非终结 符， (VNVT) *则此文法称为 2 型的或上下文无关
6、的1。 规定产生式的左部必须为非终结符。 第三章 程序设计 3.1 词法分析程序的实现 3.1.1 文法输入规则 源文法的输入采用文件输入的方式，每读入一个字符就进行文法符号的判 定、记录和编码，同时对产生式以特定格式存储。文件中源产生式的书写格式规 定如下：格式为“左部右部” ，左部为一非终结符，右部的文法符号之间不允许 有空格，右部结束后直接回车或文件结束，规定文件的第一个字符为文法的开始 符号；格式中使用“”而非“-”的原因在于简化词法分析，可以避免在读入 字符“-”时的分情况处理（因为“-”也是一个终结符） 。举例如下： /*file:e:demo1.dat 参考文献 1 例 5.5*/ SAB SbC A char Nch; unsigned int ifgetnull; 3 Vn_type; Vn_type Vn100; int Vn_ID_next; 以上为非终结符的存储结构，对非终结符采用结构体数组存储。结构体中 ID 存储非终结符的编码（关于编码，程序中规定非终结符
