LL文法判定-c语言实现.doc

编译原理课程设计 LL(1)文法判定 ---c语言实现 专业班号____计算机021_____ 学生姓名____3122020130____ 指导教师____齐林海________ 联系电话：010邮箱地址：zhangyufeng628@ 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 求解产生式的右部的FIRST集 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 第一章 前 言 本设计使用C语言实现了对简单方法描述的LL(1)文法的判定。该设计程序实现了：⑴分别求出每一产生式的右部的FIRST 集、每一个非终结符的FOLLOW集和每一产生式的SELECT集；⑵判定是否是LL(1)文法；⑶画出预测分析表；⑷对给定的符号串判定是否是文法中的句子，分析过程用计算机打印出来。 1.1 LL(1)文法概述 LL(1)文法是一种2型文法 ，由它所描述的语言可以使用自顶向下语法分析方法进行语法分析。LL(1)文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可决定如何推导即选择哪一个产生式（规则）进行推导。 一个上下文无关文法（即2型文法）是LL（1）文法的充分必要条件是，对每个非终结符A的两个不同产生式，A→α，A→β，满足 SELECT（A→α）∩SELECT（A→β）= ? 其中α、β不同时能ε[1]。 1.2 设计思想概述 首先对输入的文法进行词法分析，识别出所有的文法符号（终结符和非终结符）并对其编码生成相应ID，同时用单链表型数据结构存储单个产生式，产生式的文法符号在单链表中以其相应ID表示，即所有的产生式以规定形式存储在一个单链表集中。第二步，针对单链表型数据结构，设计相应算法计算出每一个表达式右部的FIRST 集、每一非终结符的FOLLOW集和每一产生式的SELECT集，其结果均以单链表集的形式存储。最后，由求出的SELECT集经由相应算法判定出该输入文法是否为LL(1)文法，若是，则在屏幕上输出预测分析表，并对给定的符号串判定是否是文法中的句子，分析过程用计算机打印出来。 第二章 语言文法规则 2.1 语言的词法规则 为简单起见，本设计规定非终结符集VN为所有大写字母的集合，终结符集VT为所有小写字母、数字和四则运算符号的集合，取所有文法符号均为单个字符。 2.2 语言的语法规则 由2型文法的定义，定义如下： 设G=（VN，VT，P，S），若P中的每一个产生式α→β满足： α是一非终结符， β∈(VN∪VT)*则此文法称为2型的或上下文无关的[1]。 规定产生式的左部必须为非终结符。 第三章 程序设计 3.1 词法分析程序的实现 3.1.1 文法输入规则 源文法的输入采用文件输入的方式，每读入一个字符就进行文法符号的判定、记录和编码，同时对产生式以特定格式存储。文件中源产生式的书写格式规定如下：格式为“左部右部”，左部为一非终结符，右部的文法符号之间不允许有空格，右部结束后直接回车或文件结束，规定文件的第一个字符为文法的开始符号；格式中使用“”而非“-”的原因在于简化词法分析，可以避免在读入字符“-”时的分情况处理（因为“-”也是一个终结符）。举例如下： /*file:e:\demo1.dat参考文献1例5.5*/ SAB SbC A Ab B BaD CAD Cb DaS Dc 3.1.2 数据结构 对非终结符和终结符分别采用以下的数据结构存储： typedef struct Vn_stru{ unsigned