实验六计算first集合和follow集合
实验六:计算first集合和follow集合
编译原理实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
姓名:滕雯娟 学号:E10914008 专业:计算机科学与技术 年级 :09 级2班 实验时间:2012/6/7 成绩:
实验六:计算first集合和follow集合 实验目的:
1( 掌握求first和follow集合的算法
2( 熟悉运用C/C++语言对求first和follow集合进行实现
实验要求:
输入:任意的上下文无关文法。
输出:所输入的上下文无关文法一切非终结符的first集合和follow集合 实验原理:
设α,x1x2…xn，FIRST(α)可按下列方法求得:
令FIRST(α),Φ，i,1;
) 若xi?VT，则xi?FIRST(α); (1
(2) 若xi?VN;
? 若ε FIRST(xi)，则FIRST(xi)?FIRST(α);
? 若ε?FIRST(xi)，则FIRST(xi),{ε}?FIRST(α); (3) i,i+1，重复(1)、(2)，直到xi?VT，(i,2，3，…，n)或xi?VN且若ε FIRST(xi)或i>n为止。
当一个文法中存在ε产生式时，例如，存在A?ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A?ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。
设文法G[S],(VN，VT，P，S)，则
FOLLOW(A),{a | S … Aa …，a?VT}。
若S …A，#?FOLLOW(A)。
由定义可以看出，FOLLOW(A)是指在文法G[S]的所有句型中，紧跟在非终结符A后的终结符号的集合。
FOLLOW集可按下列方法求得:
(1) 对于文法G[S]的开始符号S，有#?FOLLOW(S);
(2) 若文法G[S]中有形如B?xAy的规则，其中x，y?V *，则FIRST(y),{ε}?FOLLOW(A);
(3) 若文法G[S]中有形如B?xA的规则，或形如B?xAy的规则且ε?FIRST(y)，其中x，y?V *，则FOLLOW(B)?FOLLOW(A);
实验内容:
程序代码如下:
#include
#include
using namespace std; #define max 30
typedef struct CSS //定义一个产生式结构体 {
string left; //定义产生式的左部
string right; //定义产生式的右部
}CSS;
string con;//存放文法中的非终结符
string first[max];//存放非终结符的first集
string follow[max];//存放非终结符的follow集
//提取产生式中的非终结符
void search(CSS *p,int n) {
int i,j;
for(i=0;i=0&&con.find(p[i].left[0])=0&&con.find(p[i].right[j])=p[i].right[0])
first[mm]=first[mm]+p[i].right.substr(0,1);
if(p[i].right[0]=='#')
first[mm]=first[mm]+p[i].right.substr(0,1);
if('A'<=p[i].right[0]&&'Z'>=p[i].right[0])
{
for(j=0;j>n;
CSS *p=new CSS[n]; // 初始化产生式数组
for(i=0;i>input; //输入
for(j=0;j>f;
search(p,n);//提取产生式中的非终结符
for(m=0;m
本文档为【实验六计算first集合和follow集合】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483