下载文档原格式
第三部分上下文无关语言和下推自动机前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。
上下文无关文法（CFL）是一种简单的描述语法规则的递归方法，语言中的字符串由这些规则产生。
所有的正规语言都能用上下文无关文法描述，它也可以描述非正规语言。
上下文无关文法描述的语法规则更复杂多变，可以在相当大的程度上，描述高级程序设计语言的语法和其他一些形式语言。
类似正则语言对应的抽象机模型是有限自动机，CFL也有对应的抽象机模型。
CFL对应的计算模型是在有限自动机的基础上增加存储空间得到，并被设想成无限空间（对应有限自动机的有限空间），采用了一种简单的管理模式，栈（stack），这种新的计算模型（或抽象机）称为下推自动机（pushdown automata），下推是栈最典型的操作。
有必要在下推自动机中保留非确定性，确定型下推自动机不能接受所有的CFL，但给定一个CFG，容易构造一个相应的非确定型下推自动机，它在识别字符串过程中的移动模拟了文法的推导过程，这个过程称为分析（parse）。
分析不是一定需要下推自动机来完成。
CFL仍然不够通用，不能包括所有有意义的、或有用的形式语言。
采用类似第五章的技术，我们将给出一些不是CFL的简单例子，这些技术也用于解决与CFL相关的判定问题。
6 上下文无关文法6.1 上下文无关文法的定义为了描述我们在第二部分考察的各种语言，包括一些非正则语言，我们引入一种语言的递归定义方法，称为文法。
文法与我们熟悉的语言的语法描述相近，是描述语言和分析语言的有力工具。
问题：文法的形式化定义似乎可以模仿有限自动机，比如5元组或6元组之类。
例子6.1 正如我们在例子2.16中所见，字母表{a, b}上的回文语言pal可以用下面的递归方法描述：1.Λ, a, b∈pal2.对每个S∈pal，aSa和bSb也属于pal3.pal中不包含其他字符串如果将上面的符号S看成一个变量，代表了所有我们希望计算（比如某种递归算法）的pal 的元素，那么上面的规则1和规则2可以非正式地重新表述如下：1.S的值可以是Λ, a, b2.每个S可以写成aSa或bSb的形式如果我们用→表示“可以取值为”，则可以写出下面的式子：S→aSa→abSba→abΛba=abba上面的产生过程可以总结成下面的两组产生式（或称规则）：S→a | b | ΛS→aSa | bSb符号“|”表示“或”的含义。
编译原理第二版课后习答案编译原理是计算机科学领域中的一门重要学科，它主要研究程序的自动翻译技术，将高级语言编写的程序转换为机器能够执行的低级语言。
编译原理的基本概念和技术是计算机专业学生必须学会的知识之一，而编译原理第二版课后习题则是帮助学生更好地理解课程内容和提高编译器开发能力的重要资源。
本篇文章将对编译原理第二版课后习题进行分析和总结，并提供一些参考答案和解决问题的思路。
一、词法分析词法分析是编译器的第一步，它主要将输入的字符流转换为有意义的词法单元，例如关键字、标识符、常量和运算符等。
在词法分析过程中，我们需要编写一个词法分析程序来处理输入的字符流。
以下是几道词法分析相关的习题：1. 如何使用正则表达式来表示浮点数？答案：[+|-]?(\d+\.\d+|\d+\.|\.\d+)([e|E][+|-]?\d+)?这个正则表达式可以匹配所有的浮点数，包括正负小数、整数和指数形式的浮点数。
2. 什么是语素？举例说明。
答案：语素是构成单词的最小承载语义的单位，例如单词“man”，它由两个语素“ma”和“n”组成。
“ma”表示男性，“n”表示名词。
3. 采用有限状态自动机(Finite State Automata)实现词法分析的优点是什么？答案：采用有限状态自动机(Finite State Automata)实现词法分析的优点是运行速度快，消耗内存小，易于编写和调试，具有可读性。
二、语法分析语法分析是编译器的第二步，它主要检查词法分析生成的词法单元是否符合语法规则。
在语法分析过程中，我们需要编写一个语法分析器来处理词法单元序列。
以下是几道语法分析相关的习题：1. 什么是上下文无关文法？答案：上下文无关文法(Context-Free Grammar, CFG)是一种形式语言，它的语法规则不依赖于上下文，只考虑规则左边的非终结符号。
EBNF是一种常见的上下文无关文法。
2. LR分析表有什么作用？答案：LR分析表是一种自动机，它的作用是给定一个输入符号串，判断其是否符合某个文法规则，并生成语法树。
上下文无关文法的基本概念上下文无关文法的基本概念定义：上下文无关文法G是一个四元组G = (N，T，P，S)，其中N是非终结符的有限集合；T是终结符或单词的有限集合，它与N不相交；P是形如 A →α的产生式的有限集合，其中A∈N,α∈V ﹡,V=T∪NS是N中的区分符号，称为开始符号或句子符号。
V中的符号称为文法符号，包括终结符和非终结符。
特殊情况：A →ε空产生式例如，if语句结构的文法产生式表示：stmt →if expr then stmt else stmtBackus - Naur范式（Backus-Naur form）或BNF文法符号的使用约定：符号是终结符：字母表中比较靠前的小写字母，如a，b，c等。
操作符，如+、-等。
标点符号，如括号、逗号等。
数字0，1， (9)黑体串，如id、if等。
符号的使用约定：下列符号是非终结符：字母表中比较靠前的大写字母，如A、B、C等。
字母S，它常常代表开始符号。
小写斜体名字，如expr、stmt等。
字母表中比较靠后的大写字母，如X、Y、Z等，表示文法符号，也就是说，可以是非终结符也可以是终结符。
符号的使用约定：字母表中比较靠后的小写字母，如u，v，…，z等，表示终结符号的串。
小写希腊字母，如α、β、γ等，表示文法符号的串。
因此，一个通用产生式可以写作A →α，箭头左边（产生式左部）是一个非终结符A，箭头右边是文法符号串（产生式右部）。
符号的使用约定：如果A →α1、A →α2、…、A →αk 是所有以A为左部的产生式（称为A产生式），则可以把它们写成A →α1|α2|…|αk，我们将α1、α2、…、αk称为A的候选式。
除非另有说明，否则第一个产生式左部的符号是开始符号。
例1考虑下面的关于简单算术表达式的文法，非终结符为<表达式>和<运算符>，终结符有ID,+,-,*,/,↑,(,)。
产生式有<表达式> → <表达式> <运算符> <表达式><表达式> → (<表达式>)<表达式> → - <表达式><表达式> →ID<运算符> → +<运算符> → -<运算符> → *<运算符> → /<运算符> →↑正规表达式和上下文无关文法的关系：正规表达式所描述的每一种语言结构都可以用上下文无关文法来描述。
HUNAN UNIVERSITY计算理论导引实验报告题目：上下文无关文法（CFG）学生姓名：学生学号：专业班级：计算机科学与技术2班上课老师：实验日期：2014-1-5一、实验目的 (2)二、实验内容.......................................................................................... 错误！未定义书签。
三、实验代码.......................................................................................... 错误！未定义书签。
四、测试数据以及运行结果 (9)五、实验感想 (13)一、实验目的1、掌握上下文无关文法概念。
2、掌握用动态规划算法验证某个字符串w是否属于某上下文无关文法。
二、实验内容对于任意给定的一个上下文无关文法，并对任意字符串w, 用动态规划算法判断是否有w∈L(G)。
编写一个算法/程序，对于给定的输入<G,w>，可以在多项式时间内判定ACFG。
三、实验代码#include <iostream.h>// 第一类规则，即规则右边只含有两个变元class Regular_1{public:int left;int right_1;int right_2;};// 第二类规则，即规则右边只含有一个终结符或者空class Regular_2{public:int left;int right;};// 表格类，用来存放中间数据class Table{public:int size; // 表格的行和列的数量，与输入长度相同int num_v; // 表格中每个单元格最多含有的数量大小，与cfg的变元数量相同int ***value; // 用来存放数据的三元数组Table(int num_v,int num_w); // 构造函数，参数指定输入字符串的长度以及cfg变元的数量~Table(); // 析构函数void SetValue(int i,int j,int num); // 向表格第i行j列追加数据numbool CheckValue(int i,int j,int num); // 检查表格第i行j列是否含有数据num，含有则返回true，否则返回falsevoid Print(); // 打印表格的内容};Table::~Table(){if(value)delete value;}void Table::SetValue(int i,int j,int num){int *p=value[i][j];// 寻找追加数据的位置while((*p)!=-1){p++;}*p=num;}bool Table::CheckV alue(int i,int j,int num) {int *p=value[i][j];while((*p)!=-1){if((*p)==num)return true;p++;}return false;}Table::Table(int num_v,int num_w){size=num_w;this->num_v=num_v;value=new int**[num_w];// 给value动态分配，并将初值设为-1for(int i=0;i<num_w;i++){value[i]=new int*[num_w];for(int j=0;j<num_w;j++){value[i][j]=new int[num_v];for(int k=0;k<num_v;k++){value[i][j][k]=-1;}}}}void Table::Print(){int i,j,k;cout<<"---------------打印表格内容------------------"<<endl;if(size==0){cout<<"表格为空"<<endl;return;}cout<<"表格内容如下:"<<endl;for(i=0;i<size;i++){for(j=0;j<size;j++){cout<<"table["<<i<<"]["<<j<<"]:";for(k=0;k<num_v;k++){if(this->value[i][j][k]==-1)break;elsecout<<this->value[i][j][k]<<" ";}cout<<endl;}}}class CFG{public:int num_v;int num_e;Regular_1* r1;Regular_2* r2;int start_v;bool Go(int *w);CFG();~CFG();};CFG::CFG(){cout<<endl<<"------------CFG构造函数----------"<<endl;int num_r1,num_r2;int i,j,k;cout<<"----------------------"<<endl<<"变元总数：";cin>>num_v;cout<<"终结符总数:";cin>>num_e;cout<<"----------------------"<<endl<<"第一类规则总数（规则右边为变元）：";cin>>num_r1;r1=new Regular_1[num_r1+1];cout<<"----------------------"<<endl;cout<<"在下面的输入中注意：变元编号以及终结符编号从0开始"<<endl;cout<<"----------------------"<<endl;for(i=0;i<num_r1;i++){cout<<"第"<<i<<"条规则的三个变元的编号依次为(以空格隔开)：";cin>>r1[i].left>>r1[i].right_1>>r1[i].right_2;}r1[i].left=-1;cout<<"----------------------"<<endl<<"第二类规则总数（规则右边为终结符或空）：";cin>>num_r2;r2=new Regular_2[num_r2+1];for(i=0;i<num_r2;i++){cout<<"第"<<i<<"条规则的变元的编号和终结符编号（空以-1表示）依次为(以空格隔开)：";cin>>r2[i].left>>r2[i].right;}r2[i].left=-1;cout<<"----------------------"<<endl<<"起始变元的编号为:";cin>>start_v;}CFG::~CFG(){if(r1)delete r1;if(r2)delete r2;}bool CFG::Go(int *w){bool result=false;Regular_1 *p1=r1;Regular_2 *p2=r2;int len_w=0;int *p=w;// 获取输入长度while(*p!=-1){len_w++;p++;}p=w;Table t(num_v,len_w);int i,j,k,l;cout<<"-----------开始运行-----------"<<endl;if(w[0]==-1){cout<<"-------------------------------"<<endl;cout<<"检查发现输入为空..."<<endl;while((*p2).left!=-1){if((*p2).left==start_v&&(*p2).right==-1){cout<<"检查到起始变元到空的规则..."<<endl;cout<<"运行完毕！结果为：接受!"<<endl;cout<<"----------------------"<<endl;result=true;return result;}p2++;}cout<<"未发现从起始变元到空的派生。
"<<endl;cout<<"运行完毕，结果为：拒绝"<<endl;cout<<"----------------------"<<endl;return false;}p2=r2;i=0;cout<<"-------------------------------"<<endl;cout<<"开始从头到尾扫描，将某些变元放入对应的对角线上的表格中："<<endl;while(*p!=-1){while((*p2).left!=-1){if((*p2).right==*p){cout<<"由于变元"<<(*p2).left<<"派生"<<"终结符"<<*p<<",故将其放入表格的"<<i<<"行"<<i<<"列"<<endl;t.SetValue(i,i,(*p2).left);}p2++;}p2=r2;p++;i++;}p=w;cout<<"-------------------------------"<<endl;cout<<"开始依次向表格的某些单元格添加数据..."<<endl;for(l=2;l<=len_w;l++){for(i=0;i<len_w-l+1;i++){j=i+l-1;for(k=i;k<=j-1;k++){while((*p1).left!=-1){if(t.CheckValue(i,k,(*p1).right_1)&&t.CheckValue(k+1,j,(*p1).right_2)){cout<<"table("<<i<<","<<k<<")中含有变元"<<(*p1).right_1<<"而且table("<<k+1<<","<<j<<")中含有"<<(*p1).right_2;cout<<",因此将变元"<<(*p1).left<<"放入table("<<i<<","<<j<<")中"<<endl;t.SetValue(i,j,(*p1).left);}p1++;}p1=r1;}}}t.Print();if(t.CheckValue(1,len_w-1,start_v)){cout<<"起始变元"<<start_v<<"在talbe(0,"<<len_w-1<<")中"<<endl;cout<<"运行完毕！结果为：接受!"<<endl;cout<<"----------------------"<<endl;return true;}else{cout<<"起始变元"<<start_v<<"在不在talbe(0,"<<len_w-1<<")中"<<endl;cout<<"运行完毕！结果为：拒绝!"<<endl;cout<<"----------------------"<<endl;return false;}}main(){cout<<"------------CFG是P成员判定程序----------"<<endl;CFG c;while(true){int *w;int len_w;cout<<"----------------------"<<endl<<"输入w的长度：";cin>>len_w;w=new int[len_w+1];if(len_w==0)cout<<"----------------------"<<endl;elsecout<<"依次输入w的内容的编号（以空格隔开）:";for(int i=0;i<len_w;i++){cin>>w[i];}w[i]=-1;c.Go(w);cout<<"验证其它字符串？（Y/N）";char c;cin>>c;if(c=='N')return;}}四、测试数据以及运行结果CFG描述如下：S->RTR->TR|aT->TR|b在该CFG下面测试输入w1=baba和w2=ababb测试结果如下：五、实验感想拿到这个题首先有些无从下手，感觉任务挺艰巨的。
