编译课程设计报告

《编译课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华北电力大学（北京）编译原理课程设计LL(1)文法判定---c语言实现专业班号____计算机021_____学生姓名____3122020130____指导教师____齐林海________2006年3月6日33华北电力大学（北京）目录第一章前言11.1LL(1)文法概述11.2设计思想概述1第二章语言文法规则12.1语言的词法规则12.2语言的语法规则2第三章程序设计23.1词法分析程序的实现23.1.1文法输入规则23.1.2数据结构23.1.3程序流程43.2求解FIRST集、FOLLOW集和SELECT集的实现53.2.1求出能推出的非终结符ε53.2.2求解产生式的

2、右部的FIRST集63.2.3求解非终结符的FOLLOW集73.2.4求解产生式的SELECT集73.3判定是否是LL(1)文法的实现73.4预测分析表的生成实现73.5判定给定符号串是否是文法中的句子的实现8第四章系统运行及测试94.1运行和安装环境94.2系统运行94.2系统测试94.2.1测试一94.2.2测试二10第五章结论115.1系统结论115.2存在的不足12参考文献12附录13源程序1333华北电力大学（北京）第一章前言本设计使用C语言实现了对简单方法描述的LL(1)文法的判定。该设计程序实现了：⑴分别求出每一产生式的右部的FIRST集、每一个非终结符的FOL

3、LOW集和每一产生式的SELECT集；⑵判定是否是LL(1)文法；⑶画出预测分析表；⑷对给定的符号串判定是否是文法中的句子，分析过程用计算机打印出来。1.1LL(1)文法概述LL(1)文法是一种2型文法，由它所描述的语言可以使用自顶向下语法分析方法进行语法分析。LL(1)文法的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第二个L表明分析过程中将用最左推导，1表明只需向右看一个符号便可决定如何推导即选择哪一个产生式（规则）进行推导。一个上下文无关文法（即2型文法）是LL（1）文法的充分必要条件是，对每个非终结符A的两个不同产生式，A→α，A→β，满足SELECT（A→

4、α）∩SELECT（A→β）=ø其中α、β不同时能ε[1]。1.2设计思想概述首先对输入的文法进行词法分析，识别出所有的文法符号（终结符和非终结符）并对其编码生成相应ID，同时用单链表型数据结构存储单个产生式，产生式的文法符号在单链表中以其相应ID表示，即所有的产生式以规定形式存储在一个单链表集中。第二步，针对单链表型数据结构，设计相应算法计算出每一个表达式右部的FIRST集、每一非终结符的FOLLOW集和每一产生式的SELECT集，其结果均以单链表集的形式存储。最后，由求出的SELECT集经由相应算法判定出该输入文法是否为LL(1)文法，若是，则在屏幕上输出预测分析表，并对

5、给定的符号串判定是否是文法中的句子，分析过程用计算机打印出来。第二章语言文法规则2.1语言的词法规则为简单起见，本设计规定非终结符集VN为所有大写字母的集合，终结符集VT为所有小写字母、数字和四则运算符号的集合，取所有文法符号均为单个字符。33华北电力大学（北京）2.2语言的语法规则由2型文法的定义，定义如下：设G=（VN，VT，P，S），若P中的每一个产生式α→β满足：α是一非终结符，β∈(VN∪VT)*则此文法称为2型的或上下文无关的[1]。规定产生式的左部必须为非终结符。第三章程序设计3.1词法分析程序的实现3.1.1文法输入规则源文法的输入采用文件输入的方式，每读入一

6、个字符就进行文法符号的判定、记录和编码，同时对产生式以特定格式存储。文件中源产生式的书写格式规定如下：格式为“左部>右部”，左部为一非终结符，右部的文法符号之间不允许有空格，右部结束后直接回车或文件结束，规定文件的第一个字符为文法的开始符号；格式中使用“>”而非“->”的原因在于简化词法分析，可以避免在读入字符“-”时的分情况处理（因为“-”也是一个终结符）。举例如下：/*file:e:demo1.dat参考文献1例5.5*/S>ABS>bCA>&A>bB>&B>aDC>ADC>bD>aSD>c3.1.2数据结构对非终结符和终结符分别采用以下的数据结构存储：typedefs

7、tructVn_stru{unsignedintID;charNch;unsignedintifgetnull;}Vn_type;Vn_typeVn[100];33华北电力大学（北京）intVn_ID_next;以上为非终结符的存储结构，对非终结符采用结构体数组存储。结构体中ID存储非终结符的编码（关于编码，程序中规定非终结符的编码从200开始，第一个被“发现”的非终结符被编码为200，按照被“发现”顺序依次编码为201,202,…,程序最多允许100个非终结符，即编码范围在200~299之间。对于终结