题目:First集和Follow集生成算法模拟
【问题描述】
设计一个由正规文法生成First集和Follow集并进行简化的算法动态模拟。(算法参见教材)
【基本要求】
动态模拟算法的基本功能是:
(1) 输入一个文法G;
(2) 输出由文法G构造FIRST集的算法;
(3) 输出First集;
(4) 输出由文法G构造FOLLOW集的算法;
(5) 输出FOLLOW集。
【测试数据】
输入文法:
E->TE’
E’->+TE’|ε
T->FT’
T’->*FT’|εF->(E)|i
【实现提示】
用数据库存储多行文法,用LIST控件显示算法,用GRID类依据算法进行作图。并实现算法与生成过程的关联。
三、设计思路
该分析器主要包括三大部分:求FIRST集,求FOLLOW集,求SELECT集。下面主要介绍计算FIRST集和FOLLOW集算法思想。
求FIRST集的算法思想:主要有三个函数 First(), First_getvn(), First_getvt。函数 First()调用First_getvn(),First_getvn()调用First_getvt
这里主要把产生式分成的两种:
一:产生式只能推出空,形如:S->$;此时S的FIRST集为{$}
二:产生式右部包含非终结符和终结符,形如:S->aA, S->AB.
这里定义了两个比较重要字符串,分别是first 即FIRST集;另一个是first_vn,把它定义非终结符的FIRST集。当产生式右边的第一个字符为非终结符时,把该VN加入 srt first_vn中,后再调用函数first_getvt求出FIRST集。若产生式右边的第一个字符为终结符时,则直接把该VT加入str first,得到FISRT集。
流程图:
略
2021-12-19 11:03:32
313KB
编译原理
1