logo资料库

Chomsky文法类型判断.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.19M 资料格式：doc 举报 版权申诉
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
资料共7页，全文预览结束
    编译原理实验报告
    1．0型文法（短语文法）
    2．1型文法（上下文有关文法）
    3．2型文法（上下文无关文法）
    4．3型文法（正则文法，线性文法）
    编译原理实验报告 实验名称: Chomsky 文法类型判断 实验时间: 2014 年 4 月 9 日 专业: 网路工程 学号: E01114172 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.实验内容 理解文法的判定规则，通过编程实现对文法类型的判断，并输出判定结果。 4.实验心得 通过这次实验我又一次理解了各类型文法规则的不同定义形式,并能清楚的 判断各类型文法,进而通过编程实现对于文法类型的判断,将理论付诸实践,实验 中获益很多。 5.实验代码与结果 #include #include using namespace std; typedef struct CSS { //定义一个产生式结构体 string left; //定义产生式的左部 string right; //定义产生式的右部 }CSS; bool Zero(CSS *p,int n) { int i,j; //判断 0 型文法 for(i=0;i='A'&&p[i].left[j]<='Z') //判断字符是否是非终结 符 break; } if(j==p[i].left.length()) { cout<<"该文法不是 0 型文法"<
    } bool First(CSS *p,int n) { int i; if(Zero(p,n)) { //判断 1 型文法 //先判断是否是 0 型文法 for(i=0;ip[i].right.length())&&p[i].right.length()!=NUL L) //判断产生式左部长度是否大于右部 break; } if(i==n)return 1; else{ cout<<"该文法是 0 型文法"<='A'&&p[i].left[0]<='Z')) break; } if(i==n)return 1; else{ cout<<"该文法是 1 型文法"<
    int i; if(Second(p,n)) { //同上，先判断是否是 2 型文法 for(i=0;i=3)||(p[i].right[0] >='A'&&p[i].right[0]<='Z')) //判断产生式右部字符个数是否在 12 之间，判 断右部第一个字符是否是非终结符 break; } if(i==n) { for(i=0;i='A'&&p[i].right[1]<='Z'))break; } } if(i==n) { cout<<"该文法属于 3 型文法"<>n; CSS *p=new CSS[n]; for(i=0;i>input; for(j=0;j
    { } if(input[j]=='-') { p[i].left=input.substr(0,j); p[i].right=input.substr(j+2,input.length()); } //调用文法类型判断，自顶向下 } Third(p,n); system("pause"); } 实验截图： 零型文法 一型文法
    二型文法 三型文法
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

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

    热门标签

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

    最新资料