没有合适的资源?快使用搜索试试~ 我知道了~
1、设计内容 (1)LL(1)文法的判定(假设文法符合的First和Follow集未知)根据LL(1) 分析法编写一个语法分析程序 2、设计要求: 输入文法,输出判定该文法是否是LL(1)的。
资源推荐
资源详情
资源评论
课程设计报告
课程:
编译原理课程设计
学号:
姓名:
班级:
教师:
时间:
计算机科学与技术系
1
设计名称:
()文法的判定(假设文法符合的 和 集未知)
设计内容、目的与要求:
、设计内容
()文法的判定(假设文法符合的 和 集未知)根据
分析法编写一个语法分析程序
、设计要求:
输入文法,输出判定该文法是否是 ()的。
计划与进度安排:
月 日— 月 日:
查阅资料,进一步掌握 ()文法的定义,掌握 ()分析法及其原理;
月 日— 月 日:
分析题目,画出系统的流程图;根据流程图,将系统功能划分成各个不同的模
块;
月 日— 月 日:对各个函数进行编译和检查;
编写程序执行的入口函数 ()函数,通过调用各个函数,实现整个程序
的基本功能;
月 日— 月 日:编写程序执行的入口函数 ()函数,通过调用各
个函数,实现整个程序的基本功能;
月 日 — 月 日:编译整个程序,并根据调试信息进行相应的修改
设计过程、步骤(可加页):
、数据结构设计
本系统的数据结构包含全局变量的定义和一位数组以及二维数组的定义。
分解的产生式的个数
所有终结符和非终结符的总数
!开始符号
! "#终结符号
!$ "#非终结符号
!%"#所有符号
! &"#左部
!'!"#"#右部
!("#"#)&"#"#各产生式右部的 *+,- 和左部的
../ 集合
!("#"#所有单个符号的 *+,- 集合
! "#"#各单个产生式的 ,001- 集合
!&"#)"#记录各符号的 *+,- 和 ../ 是否已求过
2
! 23"#记录可直接推出4的符号
!-056"#求 ../ 时存放某一符号串的 *+,- 集合
%73表示输入文法是否有效
表示输入文法是否为 文法
5"#"#分析表
!! 用户输入时使用
! 2"#求$ 2时使用
!&"#求 ../ 集合时使用
7'标志输入文法是否是由有递归的文法合成的 ()
、函数设计及其说明
()!)!2
功能:判断一个字符是否在指定字符串中
说明:若该字符在指定字符串中,函数返回 ;否则返回 。
()%755
功能:构造预测分析表 5。
说明:在该函数中,把预测分析表设计成二维数组,构造预测分析表时,文
法用其序号代替。
()%7
功能:设置用户界面。
说明:该函数将设计一个人机交互界面,从而选择实现各种功能。
(8)%71!
功能:得到一个不是非终结符的符号。
说明:该函数通过调用 !)!2函数,返回一个不是非终结符的
符号。
()%7 ' !7)!)32
功能:将单个符号或符号串并入另一符号串
说明:7 指向目标符号串, 指向源串,32 =,源串中的‘9:一并并入目
串;32 =,源串中的‘9:不并入目串。
()%7 !2
功能:分解含有左递归的产生式。
说明:完整的产生式在 2"#中。
()%7$ !2
功能:分解不含有左递归的产生式,即将形如 6;<= 的产生式分解为
6;< 和 6;。
说明:完整的产生式在 2"#中。
()>7'
功能:判断读入的文法是否正确
说明:若读入的文法不正确则返回 ,否则返回 。
()%73?
功能:检查输入串是否满足,通过分析表判断。
说明:通过分析表判断,检查输入的字符串是否满足。
()!' !)!)! &)!'!"#"#
3
功能:读入一个文法。
说明:! 指向终结符号的集合;
! 指向非终结符号的集合;
! & 指向文法产生式的左部;
!'!"#"#传递的参数是文法产生式的右部。
()%7../
功能:求各产生式左部的 ../ 集。
说明: 为分解后的产生式的序号。
()%7(
功能:求单个符号的 *+,- 集。
说明: 为符号在所有输入符号中的序号。
()%7*+,-)!2
功能:求各产生式右部的 *+,- 集。
说明: 为分解后的产生式的序号;!2 指向产生式的右部。
(8)
功能:判断读入文法是否为一个 文法。
说明:若输入的文法是 文法,返回 ,否则报错,返回 。
()%7 2!
功能:求所有能直接推出 9 的符号)这里利用4代替 9。
说明:!是需要判断的符号。
()$ 2!
功能:求某一符号能否推出‘9:
说明:!是需要判断的符号,若能推出,则返回 ,否则返回 。
、总控算法及流程
() 推导出非终结符
首先进行第一次扫描,把能够直接推出@的非终结符号记录到空串表,把
不能直接推出@的符号依次记录下来,然后单个扫描每一个不能直接推出@的符
号。扫描这个符号能够直接推出的第一个非终结符记录到一个队列,接下来依
次检查队列中每一个元素,把二次能够推出@的符号记录到空串表,把二次也
推不出空串的继续送入到队列,然后再从队列取元素扫描,直到队列为空没能
找到能够星推导出@的终结符,那么可以确定这个非终结符推导不出@,接下去
扫描下一个非终结符。
()确定 *+,- 集
*+,- 集使用以下四个步骤判定:
、若 ABC--)则 *+,-ADAE
、若 ABCF)且有产生式 A;G,BC- 则把 加入到 *+,-A中,即
B*+,-A
、 若 ABCF) 且 有 产 生 式 A;@ , 则 把 @ 也 加 到 *+,-A 中 , 即
@B*+,-A
8、若 ABCF)H,H,…,H都∈CF,且有产生式 A;HHGH。
当 H, IIHJK@LL,则 *+,-HJD@E,…,*+,-HJJ
D@E,*+,-H都包含在 *+,-A中,即:
4
*+,-HJJD@EB*+,-A
所有 H)GHK@)则把@加到 *+,-A中)即M
*+,-HB*+,-A
其中第 J 个方法都很好处理,关键是第四个方法判断时首先判断第一个
字符为非终结符,设定一个布尔型扫描标志 NO,赋初值 -+P0,接下去依
次扫描产生式右部每一个字符 H,假如第 个字符可以推出空,那么就把这个
字符的 *+,- 集去除@加入到产生式左部字符的 *+,- 集中,即 *+,-HJ
D@EQ*+,-A)假如 H 是终结符或 者 不可以推 出 @, 那么就把 这 个字符 的
*+,- 集 直 接 加 入 到 *+,-A中 , 即 *+,-HQ*+,-A同时 置 NO 为
N,0 不再向下扫描,假如 H 恰好是最后一个字符,那么不管它能不能星推导
出空都直接把它的 *+,- 集加入到 *+,-A中。同时要设置一个队列和一组
布尔型变量记录 *+,- 集是否完成,队列用来记录 *+,-A用到了哪些其它
非终结符的 *+,- 集。
第一遍扫描完成后就扫描队列,把 *+,- 集完成的非终结符的 *+,- 集加
入到那些没有完成的非终结符的 *+,- 集中去,没有完成的非终结符再送回到
队列,这时候可能出现死循环,比如 *+,-,用到了 *+,-N)而 *+,-N
用到了 *+,-R,*+,-R又用到了 *+,-,)这时候 ,)N)R 的 *+,- 标志
均为 N,0,无限循环下去。这时候可以记录一下,比如循环了 次,强行
设置 *+,-,的标志为 -+P0,那么 *+,-N)*+,-R也就依次可以求出
了。我们在实际计算时也是这样处理的,只是没有把标志写出来而是记录在心
里的。
()确定 ../ 集
../ 集使用以下三个步骤判定:
、如果 A是开始符 那么把 S加入到 ../A
、若AKTRU 是一个产生式)则把 *+,-U-D@E加至 ../R
中
、若AKTR 是一个产生式,或AKTRU 是一个产生式而 UK@即
@B*+,-U),则把 ../N加至 ../R中。
../ 集的求法与 *+,- 集类似,但有不同的地方。../ 集需要
扫描每一个产生式。而 *+,- 集扫描的是产生式左部不同的产生式,然后扫描
左部相同的产生式的每一个右部。../ 集第一次扫描可以确定哪些 *+,-
集或 ../ 集属于所求的 ../ 集,由于 *+,- 集已经求出,所以第一
次扫描就可以把相应的 *+,- 集加入到 ../ 集中,设置 ../ 集完成
标记位,设置队列,把未完成的非终结符送入队列,依次取出队列元素,把求
出 ../ 集的非终结符的 ../ 集加入到相应的 ../ 集中,把未
求出的送回队列。如果碰到死循环使用 *+,- 集一样的方法处理就可以。
(8)确定 ,001- 集
*+,- 集&../ 集都已经求出来后 ,001- 集就很好求了,扫描每
一个产生式,使用以下三个步骤确定:
N;TNBCF,TBC,
、若 T 是终结符,那么 ,001-N;TDTE;
、若 T 是@,则 ,001-N;T../N;
、若 T 是非终结符,那么
剩余21页未读,继续阅读
资源评论
S2726664048
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功