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

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