logo资料库

Chomsky文法类型判断（编译原理实验完整代码）.doc

发布时间：2022-06-12 发布人：admin 分类：说明书 资料大小：0.19M 资料格式：doc 举报 版权申诉
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
资料共10页，剩余部分请下载后查看
    编译原理实验报告
    编译原理实验报告 实验名称 Chomsky 文法类型判断 实验时间 2017.3.30 院系 计算机科学与技术 科技二班 班级 学号 姓名
    1.实验目的 输入：一组任意的规则。 输出：相应的 Chomsky 文法的类型。 2.实验原理 1．0 型文法（短语文法） 如果对于某文法 G，P 中的每个规则具有下列形式： u:: = v 其中 u∈V＋，v∈V*，则称该文法 G 为 0 型文法或短语文法，简写为 PSG。 0 型文法或短语结构文法的相应语言称为 0 型语言或短语结构语言 L0。这种 文法由于没有其他任何限制，因此 0 型文法也称为无限制文法，其相应的语 言称为无限制性语言。任何 0 型语言都是递归可枚举的，故 0 型语言又称递 归可枚举集。这种语言可由图灵机（Turning）来识别。 2．1 型文法（上下文有关文法） 如果对于某文法 G，P 中的每个规则具有下列形式： xUy:: = xuy 其中 U∈VN；u∈V＋；x，y∈V*，则称该文法 G 为 1 型文法或上下文有关文法， 也称上下文敏感文法，简写为 CSG。 1 型文法的规则左部的 U 和右部的 u 具有相同的上文 x 和下文 y，利用该规则 进行推导时，要用 u 替换 U，必须在前面有 x 和后面有 y 的情况下才能进行， 显示了上下文有关的特性。 1 型文法所确定的语言为 1 型语言 L1，1 型语言可由线性有界自动机来识别。 3．2 型文法（上下文无关文法） 如果对于某文法 G，P 中的每个规则具有下列形式： U :: = u 其中 U∈VN；u∈V＋，则称该文法 G 为 2 型文法或上下文无关文法，简写为 CFG。 按照这条规则，对于上下文无关文法，利用该规则进行推导时，无需考虑非 终结符 U 所在的上下文，总能用 u 替换 U，或者将 u 归约为 U，显示了上下文 无关的特点。 2 型文法所确定的语言为 2 型语言 L2，2 型语言可由非确定的下推自动机来识 别。 一般定义程序设计语言的文法是上下文无关的。如 C 语言便是如此。因此， 上下文无关文法及相应语言引起了人们较大的兴趣与重视。 4．3 型文法（正则文法，线性文法） 如果对于某文法 G，P 中的每个规则具有下列形式： U :: = T 或 U :: = WT 其中 T∈VT；U,W∈VN，则称该文法 G 为左线性文法。 如果对于某文法 G，P 中的每个规则具有下列形式： U :: = T 或 U :: = TW 其中 T∈VT；U, W∈VN，则称该文法 G 为右线性文法。 左线性文法和右线性文法通称为 3 型文法或正则文法，有时又称为有穷状态 文法，简写为 RG。
    按照定义，对于正则文法应用规则时，单个非终结符号只能被替换为单个终 结符号，或被替换为单个非终结符号加上单个终结符号，或者被替换为单个 终结符号加上单个非终结符号。 3 型文法所确定的语言为 3 型语言 L3，3 型语言可由确定的有限状态自动机来 识别。 在常见的程序设计语言中，多数与词法有关的文法属于 3 型文法。 可以看出，上述 4 类文法，从 0 型到 3 型，产生式限制越来越强，其后一类 都是前一类的子集，而描述语言的功能越来越弱，四类文法及其表示的语言 之间的关系可表示为： 0 型  1 型  2 型  3 型；即 L0  L1  L2  L3 3..实验内容 本程序的基本数据结构是一个字符型的二维数组。 先将文本文件一行一行的读入二维字符数组中，每一行只有一个 产生式； 然后将二维数组中的每一行进行判断处理，先通过扫描找到每一 行的推导符号“->”； 对“->”前面以及后面的字符分开进行处理，分别对其进行终结 字符与非终结字符数量的统计； 比较产生式左部与右部所有的终结字符与非终结字符的数量，分 别对不同的情况进行判断，将判断的结果保存在一个一位数组中（所 有情况都不符合用-1 标记）； 对一维数组按从小到大的顺序进行冒泡排序，所以一位数组的第 一个元素的大小即为此文法的类型，进行输出（-1 则为不符合所有 文法类型）。 4.实验心得 这次的实验本身难度并不大，但是通过这次实验，我了解了 Chomsky 文法的基本类型，以及各种文法的判断条件，加深了我对每
    一种类型的文法的认识，这次的实验也锻炼了我利用编程实现计算机 识别文法的能力，收获还是很大的。 5.实验代码与结果 实验代码： #include #include using namespace std; class Compile { public: int OpenFile(int n,char buffer[][10]); void Scan(int n,char buffer[][10],double * type); void Sort(int n,double * type); void Show(int n,char buffer[][10]); void Select_And_Output(int type); }; void Compile::Show(int n,char buffer[][10]) { int i,j; cout<<"您输入的文法是："<
    while (!myfile.eof()) { myfile.getline(buffer[n],10); n++; } myfile.close(); return n; } void Compile::Scan(int n,char buffer[][10],double * type) { int i,j; for(i=0;i') { int a,big1=0,small1=0,big2=0,small2=0; for(a=0;a=65&&buffer[i][a]<=90) big1++; else if(buffer[i][a]>=97&&buffer[i][a]<=122||buffer[i][a]>=48&&buffer[i][a] <=57) small1++; else continue; } for(a=j+2;a<10;a++) { if(buffer[i][a]>=65&&buffer[i][a]<=90) big2++; else if(buffer[i][a]>=97&&buffer[i][a]<=122||buffer[i][a]>=48&&buffer[i][a] <=57||buffer[i][a]==35) small2++; else continue; } if(big1==1&&small1==0&&((big2==0||big2==1)&&small2==1)) { if(buffer[i][4]=='\0') type[i]=3; else if(buffer[i][3]>=65&&buffer[i][3]<=90) type[i]=2.5;
    else type[i]=2.8; } else if(big1==1&&small1==0&&!(big2<0&&small2<0)) type[i]=2; else if(big1>=1&&(big1+small1)<=(big2+small2)) type[i]=1; else if(big1>=1&&small1>=0&&!(big2<0&&small2<0)) type[i]=0; else type[i]=-1; } else continue; } } void Compile::Sort(int n ,double * type) { int i,j; int swap=0; for(i=0;itype[j+1]) { swap=type[j]; type[j]=type[j+1]; type[j+1]=swap; } else continue; } if(type[0]>2&&type[0]!=3) for(i=0;i
    { case 0: cout<<"此文法为 0 型文法"<
    实验结果：
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料