编译原理实验二：压缩文法的等价变换

文法等价变换方法啥是文法等价变换呀？简单说呢，就是把一种文法的形式变成另一种，但意思还差不多。

就好比把一件衣服换个款式，但还是那件衣服的感觉。

比如说，主动句和被动句的变换。

“我吃了苹果”，这是主动句，变成被动句就是“苹果被我吃了”。

这两种说法虽然形式不一样，但表达的基本事实是一样的。

那为啥要进行文法等价变换呢？有时候是为了让句子看起来更高级，就像给文字化个妆。

比如写作文的时候，老是用简单的句式就显得很平淡。

要是把普通的陈述句变成倒装句，“我喜欢你”变成“喜欢你，我”，是不是突然就有点文艺范了呢？还有的时候是为了强调不同的部分。

主动句强调的是动作的执行者，被动句强调的是动作的承受者。

如果想强调苹果，那就用被动句“苹果被我吃了”，要是强调我，就用主动句“我吃了苹果”。

那具体咋变换呢？有一些小窍门哦。

像刚刚说的主动变被动，要把原来的宾语变成主语，“我”这个主语呢，就变成“被我”这样的形式放在动词前面。

再比如说，把肯定句变成双重否定句。

“他是个好人”，变成双重否定句就是“他不可能不是个好人”。

不过要注意哦，双重否定可别用错了，不然就会变得很奇怪。

还有一种情况呢，是词语的替换来实现等价变换。

比如“美丽”和“漂亮”，在很多时候可以互相替换。

“这个女孩很美丽”和“这个女孩很漂亮”表达的基本情感和意思是一样的。

但是呢，在一些语境下，可能“美丽”会显得更优雅一些，“漂亮”更口语化一些。

宝子们，文法等价变换就像是文字游戏一样，很好玩的。

咱们在平时说话或者写东西的时候，可以灵活运用，让自己的表达更加丰富多彩。

可别小看这个小魔法哦，它能让你的表达更有魅力呢。

递归下降分析器设计一、实验/实习过程内容：利用JavaCC生成一个MiniC的语法分析器；要求：1. 用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。

2. 具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示3. 如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树具体实施步骤如下：1.把MiniC转换为文法如下<程序〉→ main()〈语句块〉〈语句块〉→{〈语句串〉}〈语句串〉→〈语句〉〈语句串〉|〈语句〉〈语句〉→〈赋值语句〉|〈条件语句〉|〈循环语句〉〈赋值语句〉→ ID =〈表达式〉；〈条件语句〉→ if〈条件〉〈语句块〉〈循环语句〉→ while〈条件〉〈语句块〉〈条件〉→（〈表达式〉〈关系符〉〈表达式〉）〈表达式〉→〈表达式〉〈运算符〉〈表达式〉|（〈表达式〉）|ID|NUM〈运算符〉→+|-|*|/〈关系符〉→＜|＜＝|＞|＞＝|＝＝|!=2.消除语句中的回溯与左递归3．在eclipse环境下完成JavaCC的插件安装后，写一个JavaCC文法规范文件(扩展名为jj)4.完成的功能包括词法分析，语法分析二、代码：options {JDK_VERSION = "1.5";}PARSER_BEGIN(eg1)public class eg1 {public static void main(String args[]) throws ParseException { eg1 parser = new eg1(System.in);parser.start();}}PARSER_END(eg1)SKIP :{" "| "\r"| "\t"| "\n"}TOKEN : /* OPERATORS */{< PLUS: "+" >| < MINUS: "-" >| < MULTIPLY: "*" >| < DIVIDE: "/" >}TOKEN :{<BIGGER:">"> |<SMALLER:"<"> |<NOTVOLUTION:"!="> |<SMALLEREQDD:"<="> |<BIGGEREE:">=" > |<DOUBLE:"==">TOKEN: //关键字{<MAIN:"main"> |<VOID:"void"> |<IF:"if"> |<INT:"int"> | <WHILE:"while"> |<CHAR:"char"> | <VOLUTION:"="> }TOKEN : //定义整型数{< INTEGER: ["0" - "9"]( <DIGIT> )+ >| < #DIGIT: ["0" - "9"] >}TOKEN : //数字{<NUMBER:(<DIGIT>)+ | (<DIGIT>)+"."| (<DIGIT>)+"."(<DIGIT>)+| "."(<DIGIT>)+>}TOKEN : //标记{<COMMA:","> | <SEMICOLON:";"> | <COLON:":"> | <LEFTPARENTHESES:"("> |<RIGHTPARENTHESES:")"> | <LEFTBRACE:"{"> | <RIGHTBRACE:"}"> }TOKEN : //标识符{<IDENTIFIER:<LETTER> |<LETTER>(<LETTER> | <DIGIT> )* >|<#LETTER:["a"-"z", "A"-"Z"]>}void start():{}{<MAIN> <LEFTPARENTHESES> <RIGHTPARENTHESES> block() }void block():{}{<LEFTBRACE> string() <RIGHTBRACE>}void string():{}{yuju() (string())?}void yuju():{}{fuzhiyuju() | tiaojianyuju() | xunhuanyuju()}void fuzhiyuju():{}{<IDENTIFIER> <VOLUTION> biaodashi() <SEMICOLON>}void tiaojianyuju():{}{<IF> tiaojian() block()}void xunhuanyuju():{}<WHILE> tiaojian() block()}void tiaojian():{}{<LEFTPARENTHESES> biaodashi() guanxifu() biaodashi()<RIGHTPARENTHESES>}void biaodashi():{}{( <LEFTPARENTHESES> biaodashi() <RIGHTPARENTHESES> biaodashi2()) |(<IDENTIFIER> biaodashi2() ) | ( <NUMBER> biaodashi2() )}void biaodashi2():{}{(yunsuanfu() biaodashi() biaodashi2() )?}void yunsuanfu():{}{< PLUS > | < MINUS > |< MULTIPLY> | < DIVIDE >}void guanxifu() :{}{<BIGGER> | <SMALLER> | <NOTVOLUTION><SMALLEREQDD> | <BIGGEREE> | <DOUBLE>}三、实验/实习总结本次实习，我使用javacc完成了包括词法分析，语法分析(输出语法树),能够读文件的功能，总的来说比较满意，通过本次实习掌握了javacc基本的使用。

编译原理实验报告实验名称Chomsky文法类型判断实验时间2013年10月29日院系计算机科学与电子技术系班级11计算机软件学号JV114001 JV114095 JP114065姓名唐茹韩强强徐思维1.试验目的：1.熟练掌握四种文法类型的概念及区别。

2.设计一个Chomsky文法类型判别器，判断0型、1型、2型和3型文法。

2.实验原理：1.设G=(Vn,Vt,P,S)，如果它的每个产生式α->β是这样一种结构：α∈(Vn∪Vt)*且至少含有一个非终结符，而β∈(Vn∪Vt)*，则G 是一个0型文法。

2.设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式α->β均满足|β|>=|α|,仅仅S->ԑ除外，则文法G是1型或上下文有关的。

3.设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式α->β均满足：α是一个非终结符，β∈(Vn∪Vt)*，则此文法称为2型的或上下文无关的。

4. 设G=(Vn,Vt,P,S)为一文法，若P中的每一个产生式的形式都是A->aB或A->a，其中A和B都是非终结符，a∈Vt*,则G是3型文法或正规文法。

5.4个文法类的定义是逐渐增加限制的，因此可采用自顶向下的算法。

3.实验内容：1.程序清单如下：#include "stdafx.h"#include<iostream>#include<string>using namespace std;typedef struct CSS //定义一个产生式结构体{string left; //定义产生式的左部string right; //定义产生式的右部}CSS;bool Zero(CSS *p,int n) //判断0型文法{int i,j;for(i=0;i<n;i++) //循环n次，即遍历所有产生式{for(j=0;j<p[i].left.length();j++) //遍历产生式左部每一个字符{if(p[i].left[j]>='A'&&p[i].left[j]<='Z') //判断字符是否是非终结符 break;}if(j==p[i].left.length()){cout<<"该文法不是0型文法"<<endl;return 0;break;}}if(i==n)return 1;//如果每个产生时都能找到非终结符}bool First(CSS *p,int n) //判断1型文法{int i;if(Zero(p,n)) //先判断是否是0型文法{for(i=0;i<n;i++){if((p[i].left.length()>p[i].right.length())&&p[i].right.length()!=NULL) //判断产生式左部长度是否大于右部break;}if(i==n)return 1;else{cout<<"该文法是0型文法"<<endl;return 0;}}elsereturn 0;}bool Second(CSS *p,int n) //判断2型文法{int i;if(First(p,n)) //同上，先判断低级文法是否成立{for(i=0;i<n;i++) //同上，遍历所有文法产生式{if((p[i].left.length()!=1)|| !(p[i].left[0]>='A'&&p[i].left[0]<='Z')) //判断产生式左部长度是否为一，左部第一个是否是非终结符break;}if(i==n)return 1;else{cout<<"该文法是1型文法"<<endl;return 0;}}elsereturn 0;}void Third(CSS *p,int n) //判断3型文法{int i;if(Second(p,n)) //同上，先判断是否是2型文法{for(i=0;i<n;i++) //同上，遍历文法所有的产生式{if((p[i].right.length()==0)||(p[i].right.length()>=3)||(p[i].right[0]>='A'& &p[i].right[0]<='Z')) //判断产生式右部字符个数是否在12之间，判断右部第一个字符是否是非终结符break;}if(i==n){for(i=0;i<n;i++){if(p[i].right.length()==2){if(!(p[i].right[1]>='A'&&p[i].right[1]<='Z'))break;}}if(i==n){cout<<"该文法属于3型文法"<<endl;}elsecout<<"该文法属于2型文法"<<endl;}else cout<<"该文法属于2型文法"<<endl;}elsecout<<"结束"<<endl;}void main( ){int i,j,n;string input;cout<<"请输入文法产生式个数N：";cin>>n;CSS *p=new CSS[n]; // 初始化产生式数组for(i=0;i<n;i++) //输入产生式数组{input.erase(); //清除cin>>input; //输入for(j=0;j<input.length();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");}2.程序运行结果：测试用例1：7S->aSBES->aBEEB->BaB->abbB->bbbE->beeE->ee运行结果：测试用例2：1型文法：7S->aSBES->aBEEB->BEaB->abbB->bbbE->beeE->ee运行结果：测试用例3：2型文法：9S->aABA->bBS->bBB->bBS->aB->bA->aAB->aA->aS运行结果：测试用例4：3型文法：9S->aAA->bBS->bBB->bBS->aB->bA->aAB->aA->aS运行结果见下页：4.实验心得：通过Chomsky文法类型判断实验的实际操作，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。

实验二：压缩文法的等价变换一：要求输入：任意的上下文无关文法输出：等价的压缩了的文法要求：除了可查看压缩了的文法，还可查看删除了哪些规则二：实验目的了解文法的简化三：实验原理删除文法中的有害规则和多余规则有害规则：若文法中有如U::=U的规则，则这就是有害规则，它会引起二义性，而无任何用处。

多余规则：（1）某条规则U::=u的左部非终结符U（U不是识别符号），不在任何其他规则右部出现，即所有的推导始终不会用到此规则。

【不可到达】（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。

即该规则中含有推不出任何终结符号串的非终结符。

【不可终止】四：数据结构与算法struct Chomsky{string left;string right;};void apart(Chomsky *p,int i) //分开产生式左右部void VNVT(Chomsky *p)//求VN和VTint zero(Chomsky *p)//0型文法int one(Chomsky *p)//1型文法int two(Chomsky *p)//2型文法void shanchu(Chomsky *p)//删除多余规则与有害规则五：出错分析1：变量重复定义导致了一些小错误2：程序太长{}缺少也导致了错误3：后面删除规则的程序出错了，没有调试成功。

六：实验结果与分析不是上下文无关文法的：2型文法的压缩：七：源代码#include<iostream>#include<string>using namespace std;#define max 50int NONE=1;int RELEFT=1;string strings,noend,end;//非终结符与终结符存储int n;//产生式总数int flag;struct Chomsky{string left;string right;};void apart(Chomsky *p,int i) //分开产生式左右部{int j;for(j=0;j<strings.length();j++)if(strings[j]=='-'){p[i].left=strings.substr(0,j);p[i].right=strings.substr(j+1,strings.length()-j);}}void VNVT(Chomsky *p)//求VN和VT{int i,j;for(i=0;i<n;i++){for(j=0;j<(int)p[i].left.length();j++){if((p[i].left[j]>='A'&&p[i].left[j]<='Z'))//非终结符判断{if(noend.find(p[i].left[j])>100)noend+=p[i].left[j];}else{if(end.find(p[i].left[j])>100)end+=p[i].left[j];}}{if(!(p[i].right[j]>='A'&&p[i].right[j]<='Z'))//终结符判断{if(end.find(p[i].right[j])>100)end+=p[i].right[j];}else{if(noend.find(p[i].right[j])>100)noend+=p[i].right[j];}}}}int zero(Chomsky *p)//0型文法{int flag(0),count(0);int i,j;for(i=0;i<n;i++){{if(p[i].left[j]>='A'&&p[i].left[j]<='Z') //有否非终结符flag++;}if(flag>0){flag=0;count++;}elsebreak; //左部没有非终结符，结束}if(count==n)return 1; //属于0型文法else{cout<<endl<<"所输产生式不属于任何文法。

编译原理实验报告实验名称压缩文法学号xxxxxxxx姓名xxx压缩文法1.实验目的输入一组文法规则，将其无用的有害规则和多余规则删除，只保留有用的规则，实现文法最简，从而避免文法的二义性。

2.实验原理1)、有害规则：若文法中有如U::=U的规则，则这就是有害规则，它会引起二义性，而无任何用处。

例如存在U::=U， U::= a | b,则有两棵语法树：U U| || |U Ｕ|a2)、多余规则：（1）某条规则U::=u的左部非终结符U（U不是识别符号），不在任何其他规则右部出现，即所有的推导始终不会用到此规则。

【不可到达】（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。

即该规则中含有推不出任何终结符号串的非终结符。

【不可终止】例如给定G[S]，若其中关于U的规则只有如下一条：U::=xUy该规则是多余规则。

3)、若某文法中无有害规则或多余规则，则称该文法是压缩过的。

文法化简的步骤:◆查找有无形如P P的产生式，若有则删除；◆若某个产生式在推导过程中永远不会被用到，删除它；◆若某个产生式在推导过程中不能从中导出终结符，删除它。

◆最后，整理所有剩余产生式，就得到简化的文法。

3.实验内容1）、输入文法的终结符（小写字母或数字）和非终结符（大写字母）以及确定识别符（规定第一输入的非终结符为识别符）2）、输入文法的产生式的个数以及各个产生式（左部->右部）（包含有害文法或多余文法）3）、压缩文法类型4.实验代码与结果1）、实验代码#include <stdio.h>main(){chara[100][100]={"0"},c[100][100]={"0"},d[100][100]={"0"},e[100][100]={"0"};int f, i,j,k=0,t=0,k1,k2,k3=0,k4,k5=0;char m[100]={"0"},n[100]={"0"};/*输入文法*/printf("\n输入规则个数:");scanf("%d",&f);printf("\n输入文法:\n");for(i=0;i<f;i++)scanf("%s",a[i]);/*规则1的判定*/for(j=0;j<strlen(a[0]);j++)if(a[0][j]>='A'&&a[0][j]<='Z')m[t++]=a[0][j];for(k2=0;k2<t;k2++)for(i=1;i<f;i++)// for(j=0;j<strlen(a[i]);j++)if(a[i][0]==m[k2])for(k1=0;k1<strlen(a[i]);k1++)if(a[i][k1]>='A'&&a[i][k1]<='Z'){for(k4=0;k4<t;k4++){if(m[k4]==a[i][k1])break;if(k4>=t-1)m[t++]=a[i][k1];}}/*规则1判定后的文法*/for(i=0;i<f;i++)for(k1=0;k1<t;k1++)if(a[i][0]==m[k1]){for(k2=0;k2<strlen(a[i]);k2++)c[k3][k2]=a[i][k2];k3++;}/*规则2的判定*/printf("\n压缩后的文法:\n");for(i=0;i<k3;i++)if(c[i][4]>='a'&&c[i][4]<='z')n[k++]=c[i][0];if(k!=0){for(k1=0;k1<k;k1++)for(i=0;i<k3;i++)for(j=4;j<strlen(c[i]);j++) if(n[k1]==c[i][j]){for(k2=0;k2<strlen(c[i]);k2++)if(c[i][k2]>='A'&&c[i][k2]<='Z') for(k4=0;k4<k;k4++){if(n[k4]==c[i][k2])break;if(k4>=k-1)n[k++]=c[i][k2];}}for(i=0;i<k3;i++)for(k2=0;k2<k;k2++)if(c[i][0]==n[k2])for(k4=0;k4<k;k4++)if(c[i][4]==n[k4]){for(k1=0;k1<strlen(c[i]);k1++)d[k5][k1]=c[i][k1];k5++;}for(i=0;i<k3;i++)if(c[i][4]>='a'&&c[i][4]<='z'){for(k2=0;k2<strlen(c[i]);k2++) d[k5][k2]=c[i][k2];k5++;}}else{for(i=0;i<k3;i++)printf("%s ",c[i]);}/*输出文法*/f or(i=0;i<k5;i++)printf("%s ",d[i]);scanf("%d"); }2）、结果。

2016.11.30LL(1)文法的判断及转换目录一、实验名称 (2)二、实验目的 (2)三、实验原理 (2)1、First集定义 (2)2、Follow集定义 (2)3、Select集定义 (3)4、含左递归文法 (3)四、实验思路 (3)1、求非终结符是否能导出空 (3)2、求First集算法 (3)3、求Follow集算法 (3)4、求Select集算法 (4)五、实验小结 (4)六、附件 (4)1、源代码 (4)2、运行结果截图 (10)一、实验名称LL(1)文法的判断及转换二、实验目的输入：任意一个文法输出：(1)是否为LL(1)文法(2)若是，给出每条产生式的select集(3)若不是，看看是否含有左公共因子或者含有左递归，并用相应的方法将非LL(1)文法变成LL(1)文法，并输出新文法中每条产生式的select集。

三、实验原理1、First集定义令X为一个文法符号（终止符或非终止符）或ε，则集合First（X）有终止符组成，此外可能还有ε，它的定义如下：1.若X是终止符或ε，则First（X）={X}。

2.若X是非终结符，则对于每个产生式X—>X1X2…Xn，First（X）包含了First （X1）-{ε}。

若对于某个i<n，所有的集合First（X1），...，First（Xi）都包含了ε，则First（X）也包括了First（Xi+1）- {ε}。

若所有集合First（X1），...，First （Xn）都包括了ε，则First（X）也包括了ε。

2、Follow集定义给出一个非终结符A，那么集合Follow（A）则是由终结符组成，此外可能还含有#（#是题目约定的字符串结束符）。

集合Follow（A）的定义如下：1. 若A是开始符号，则#在Follow（A）中。

2. 若存在产生式B—>αAγ，则First（γ）- {ε}在Follow（A）中。

3. 若存在产生式B—>αAγ，且ε在First（γ）中，则Follow（A）包括Follow （B）。

编译原理实习作业用某种高级程序设计语言实现 文法的等价压缩算法（PASCAL语言实现）二○○一年十月一日实习作业：用高级程序设计语言实现对文法多余规则的等价压缩 一．相关定义及定理：给出一个无U：：=U形规则的前提下规则不多余的判别条件：一个规则U：：=u要是有用的，便得在推导中被应用，即其左部非终结符号U必须在句子的推导中出现，且u能推导到终结符号串。

为此，U与u必须分别满足下列条件：条件1：Z=>*xUy，其中x，y∈V，Z为识别符号；条件2：u=>+t，其中t∈VT 。

●判别条件1的加标记算法步骤如下：步骤1：对规则中识别符号Z加标记；步骤2：对左部非终结符加有标记的规则，将其右部中出现的一切非终结符号加标记；步骤3：检查是否一切非终结符号都已加过标记。

是，则无多余规则而结束；否，则执行下一步骤；步骤4：检查最近一次执行步骤2时是否未对任何非终结符号加过标记。

如果是这样，该文法中左部非终结符号未加过标记的规则都不满足条件1，这些规则是多余的，结束。

否则重复步骤2。

●判别条件2的加标记算法步骤如下：步骤1：对u∈V的规则U::=u之左部非终结符号U加标记；步骤2：对右部仅包含终结符号与已加标记的非终结符号的规则之左部加标记；步骤3：检查是否已对一切非终结符号加过标记。

是，则无多余的规则而结束；否，则执行下一步骤；步骤4：检查最近一次执行步骤2时是否未对任何非终结符号加过标记。

如果是这样，该文法中左部非终结符号未加过标记的规则都不满足条件2，这些规则是多余的，结束。

否则重复步骤2。

概括起来，对一个给定的文法进行压缩文法等价变换的规范步骤如下：●展开文法规则，并删除U::=u形规则●判别条件1和2，执行加标记算法●删除不满足条件的无用规则，得到等价的压缩了的文法。

二.PASCAL程序设计语言实现文法压缩算法的功能说明：●文法的存储：对每一个可能包含无用规则的文法G[Z]以数组（grammar类型）形式存储。

《编译原理》教学大纲大纲说明课程代码： 3225003总学时： 64 学时（讲课 48 学时，实验16 学时）总学分： 4课程类别：学科基础课适用专业 : 计算机科学与技术（专业）预修要求： C 语言程序设计、 C++ 程序设计、数据结构课程的性质、任务及地位：《编译原理》是计算机科学与技术专业的一门重要基础课。

通过对该课程的学习，使学生掌握编译过程中的相关原理和编译技术，让学生能初步进行编译程序的开发和维护，同时促进提高学生开发软件的能力。

教学目的与基本要求：本课程的目的，通过向学生讲述编译系统的结构、工作流程及编译程序各部分的设计原理和实现技术，使学生既掌握编译技术理论的基础与基本知识，也具有设计、实现、分析和维护编译程序等方面的初步能力。

本课程理论性较强。

因授课对象为工科学生，所以在强调编译系统的构造原理和实现方法的同时，为培养学生的实际工作能力，通过上机实践进一步加深学生对课堂教学内容的理解。

目的是要使学生牢固掌握相关的基本理论和基本方法，并能初步利用上述理论和方法解决简单实际问题。

教学方法和教学手段的建议：在教学方法上，贯彻理论联系实际、“精讲、多练”的原则，进行案例式、启发式的教学，对于一些实际性较强的问题要多采用课堂讨论等方式，以提高学生的思辨能力和学习的主动性；引导学生读书、理解、体悟、运用相结合；提高学生的学习兴趣与热情，培养与发挥学生的提出、分析及解决问题的能力。

教学手段：运用多媒体教学手段 +黑板 +上机实验的手段。

采取课堂讲授、课堂讨论、课后练习与自学等形式。

大纲的使用说明：大纲对课程性质、目的等作简单说明，同时列出各章节要学习的知识点、重点、难点，便于教学时教授重点的安排和学生自学安排。

大纲正文第一章引论学时： 4 学时（讲课 4 学时，实验 0 学时）了解编译的概念；理解编译程序的各组成部分及功能。

本章讲授要点：介绍程序设计语言与编译程序间的关系，主要内容包括：各级程序设计语言的定义、源程序的执行、编译程序的构造、编译程序的分类、形式语言理论与编译实现技术的联系。

深圳大学实验报告课程名称：编译原理实验项目名称：语法分析--递归下降法学院：计算机与软件专业：软件工程指导教师：张小建报告人：文成学号：2011150259 班级： 2 实验时间：2013-12-25实验报告提交时间：2013-12-26教务部制一、实验目的：掌握自顶向下的语法分析法——递归下降法。

二、实验内容：用递归下降法对如下所定义的逻辑表达式进行语法分析。

1 L→ L || A2 L→ A3 A→ A && R4 A→ R5 R→ [ L ]6 R→ ! L7 R→ E >= E8 R→ E > E9 R→ E <= E10 R→ E < E11 R→ E == E12 R→ E != E13 R→ E14 E→ E + T15 E→ T16 T→ T * F17 T→ F18 F→ ( E )19 F→ n // 数20 F→ i // 标识符三、实验设计：1、消除该文法的左递归（产生式1、3、14、16）；产生式(1)L→ L || A (2)L→ A消除左递归得到：L→ A L' L'→ || A L' | з产生式(3)A→ A && R (4)A→ R消除左递归得到：A→ RA' A'→ && RA' | з产生式(14)E→ E + T (15)E→ T消除左递归得到：E→ TE' E'→ + TE' | з产生式(16)T→ T * F (17)T→ F消除左递归得到：T→ FT' T'→ *FT' | з2、通过抽取公共左因子（产生式7 ~ 12），对该文法进行LL(1)改造；产生式7~127 R→ E >= E8 R→ E > E9 R→ E <= E10 R→ E < E11 R→ E == E12 R→ E != E抽取公共左因子：R→ ER'R'→ >=E | >E | <=E | <E | ==E | !=E3、证明最终得到的文法为LL(1)文法。

文法的等价性的名词解释文法的等价性是指在语言学中，如果两种文法可以生成相同的语言，那么它们就是等价的。

在深入探讨文法的等价性之前，我们首先需要了解一些基本概念：文法、语言和生成。

然后，我们将介绍文法的等价性的概念以及与之相关的一些重要问题。

一、文法、语言和生成文法是描述一种语言结构的规则集合。

它由终结符号、非终结符号和产生规则组成。

终结符号是语言中的最基本单位，代表了具体的词汇。

非终结符号则表示了某种语言规则或语法结构。

产生规则描述了如何将非终结符号替换为终结符号和非终结符号的规则。

语言是由文法生成的符串的集合。

在一种语言中，每个符串都符合该语言的文法规则。

从一个非终结符号出发，通过不断地应用产生规则，可以生成不同的符串。

这个过程被称为生成。

二、文法的等价性文法的等价性是一个非常重要的概念。

在形式语言理论中，我们关注的是语言本身的性质，而不是语言的具体表示形式。

因此，如果两个文法可以生成相同的语言，它们就是等价的。

等价的文法可能具有不同的产生规则，但它们最终生成的符串是相同的。

这意味着，无论是使用哪个等价的文法，我们都可以得到相同的语言。

三、文法的等价性的问题文法的等价性涉及一些重要的问题，其中一些值得我们深入思考。

1. 文法的等价性是否是可判定的？在现实中，我们经常遇到需要判断两个文法是否等价的问题。

但是，判断文法的等价性是否总是可行的呢？这是一个复杂的问题，和图灵机问题类似。

虽然对于一些特定的文法类别，我们可以找到一些算法来判断等价性，但对于一般的文法类别来说，这个问题是无法判定的。

2. 如何证明两个文法是等价的？在实际应用中，我们有时需要证明给定的两个文法是等价的。

这个过程通常包括两个方面的工作：找到一个生成相同语言的等价文法，并证明这两个文法的等价性。

寻找等价文法的过程涉及使用一系列转换规则来修改文法的产生规则，以使得两个文法具有相同的生成能力。

证明等价性的过程则需要严格的逻辑推理，通常采用归纳法或形式化证明。

一、实验背景编译原理是计算机科学的一个重要分支，主要研究如何将高级语言源代码转换为计算机可以执行的机器代码。

本实验旨在通过实践操作，加深对编译原理基本概念和算法的理解，提高编程能力和解决问题的能力。

二、实验目的1. 理解编译原理的基本概念和流程；2. 掌握词法分析和语法分析的基本方法；3. 熟悉编译过程中的中间代码生成和代码优化；4. 培养编程能力和团队协作精神。

三、实验内容1. 词法分析词法分析是编译过程的第一步，其主要任务是将源代码中的字符序列转换成一个个有意义的符号（单词）。

本实验中，我们实现了词法分析器，能够识别出标识符、关键字、运算符、常量等单词。

2. 语法分析语法分析是编译过程的核心，其主要任务是将词法分析器生成的单词序列按照一定的语法规则进行组织，形成语法树。

本实验中，我们实现了递归下降解析法，对表达式、赋值语句、函数定义等语法结构进行了分析。

3. 中间代码生成中间代码生成是编译过程中的一个重要环节，其主要任务是将语法树转换为一种抽象的、与具体机器无关的中间代码。

本实验中，我们实现了三地址代码生成，将语法树转换为三地址代码。

4. 代码优化代码优化是编译过程中的一个关键步骤，其主要任务是在保证程序正确性的前提下，提高程序的性能。

本实验中，我们实现了简单的代码优化，如常数传播、变量替换等。

四、实验结果与分析1. 实验结果通过实验，我们成功实现了词法分析、语法分析、中间代码生成和代码优化等功能。

以一个简单的C语言程序为例，我们能够将其转换为三地址代码，并进行简单的优化。

2. 实验分析（1）词法分析：本实验中，我们通过定义状态转换表和动作表，实现了对C语言源代码的词法分析。

实验结果表明，词法分析器能够准确地识别出标识符、关键字、运算符、常量等单词。

（2）语法分析：递归下降解析法是一种较为直观的语法分析方法。

本实验中，我们实现了递归下降解析法，对表达式、赋值语句、函数定义等语法结构进行了分析。

编译原理1 实验题目：达式语法分析设计。

2 实验目的：熟悉并设计一个表达式的语法分析器3 相关知识：1、形式语言基础及其文法运算2、语法分析原理及4种常用的语法分析方法其中：四种算法为（1）设计算术表达式的递归下降子程序分析算法（2）设计算术表达式的LL(1) 分析算法（3）设计算术表达式的简单优先分析算法（4）设计算术表达式的SLR(1) 分析算法4 实验内容：1．设计表达式的语法语法分析器算法（1）算术表达式文法G(E): E→Eω0T|TE为算术表达式，T为项，T→Tω1F|FF为因式项，ω0为 +或 -；ω1为 * 或 /F→i|(E)i 为变量或常量（2）文法交换G'(E): E→T{ω0T}T→F{ω1F}F→i|(E)2．编写代码并上机调试运行通过要求：输入-----------表达式输出-----------表达式语法是否正确5 实验要求：1、给出算术表达式文法2、进行适当的文法变换3、选择一种语法分析的方法，并说明其原理4、根据原理给出相应的算法设计，说明主要的数据结构并画出算法流程图5、编写代码并上机调试运行通过6、写出程序运行结果7、写出相应的文档以及代码注释5 源程序(包含注释)#include<iostream>using namespace std;int value=1;char ch;int iloact=0;char str[80];void ProT(void);void ProF(void);void error() //出错处理函数{cout<<"语法分析未通过，表达式语法不正确"<<endl; }void ProE(void) //语法E的递归程序{ProT();if(ch=='+'){iloact++;ch=str[iloact]; //向前移一个位置ProE();}}void ProT(void) //语法T的递归程序{ProF();if(ch=='*'){iloact++;ch=str[iloact];ProT();}}void ProF(void) //语法F的递归程序{if(ch=='('){iloact++;ch=str[iloact];ProE();if(ch==')'){iloact++;ch=str[iloact];}else{error();value=0;}}else if(ch>='0'||ch<='9'){iloact++;ch=str[iloact];}else{error();value=0;}}int main(){cout<<"输入表达式："<<endl;cin>>str;ch=str[0];while(ch!='#') //进行递归下降分析{ProE();if(!value)break;}if((ch=='#') && ( value != 0))cout<<"语法分析通过，表达式语法正确"<<endl;return 0;}6 测试数据及运行结果7思考题：语法分析的任务是什么？答：语法分析是编译的第二阶段；其任务是识别和处理比单词更大的语法单位，如：程序设计语言中的表达式、各种说明和语句乃至全部源程序，指出其中的语法错误；必要时，可生成内部形式，便于下一阶段处理。

广州大学实验课程建设项目《编译原理实验》实验指导书广州大学信息与机电工程学院计算机系2006年10月目录实验1 Pascal 语言的编译器的使用 3 实验2 词法分析（一） 13 (调试一个词法分析程序)实验3 词法分析（二） 16 (设计、编制并调试一个词法分析程序)实验4 语法分析（一） 19 （调试一个语法分析程序，了解编译程序中LR分析表的作用）实验5 语法分析（二） 22（设计、编制并调试一个语法分析程序）实验6 语义分析 24实验7 编译原理综合实验 26 实验报告示例：词法分析程序 47考试考核方式 53实验一：Pascal 语言的编译器的使用实验目的:调试一个Pascal 语言的编译器，加深对语言编译器的理解实验内容：此程序为Pascal 语言的编译器，支持Proc ，Repeat，If，While，For，Fun函数结构代码的编译，能生成变量表、常量表和汇编程序。

界面如下：图1 Pascal 语言的编译器的使用界面下面给出软件所能编译的代码和编译出的结果。

―――――――――――――――――――――――――――――――――――Proc函数结构代码：vara, b, i: integer;procedure p1(arg1: integer; arg2: integer);begina := arg1 * arg2;end;beginb := 123;p1(3, b);――――――――――――――――――――――――――――――――――－编译状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = unsigned[静], OffPos = 0[2]b = unsigned[静], OffPos = 0[3]i = unsigned[静], OffPos = 0[4]arg1 = unsigned[参], OffPos = 0[5]arg2 = unsigned[参], OffPos = 1常量[0]Number = 123[静], OffPos = 0[1]Number = 3[静], OffPos = 0方法ID = 1, Name = p1, MethodType = 过程, ParamList = (4, 5), DynaV arList = (), Addr = 2 ＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋运行状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = 369[静], OffPos = 0[2]b = 123[静], OffPos = 0[3]i = unsigned[静], OffPos = 0[4]arg1 = unsigned[参], OffPos = 0[5]arg2 = unsigned[参], OffPos = 1汇编语句：0:Goto 0, 71:Return 0, 02:Mov 0, 43:Mov 0, 54:Mul 0, 05:Sto 1, 16:Return 0, 07:LoadConst 0, 08:Sto 0, 29:LoadConst 0, 110:Mov 0, 211:Call 0, 1 ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――For结构代码：vara, b, i: integer;a := 0;for i := 0 to 100 dobegina := a + i;end;end;――――――――――――――――――――――――――――――――――－编译状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = unsigned[静], OffPos = 0[2]b = unsigned[静], OffPos = 0[3]i = unsigned[静], OffPos = 0常量[0]Number = 0[静], OffPos = 0[1]Number = 0[静], OffPos = 0[2]Number = 100[静], OffPos = 0方法ID = 0, Name = ShowMessage, MethodType = 过程, ParamList = (0), DynaV arList = (), Addr = 1＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋运行状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = 5050[静], OffPos = 0[2]b = unsigned[静], OffPos = 0[3]i = 101[静], OffPos = 0汇编语句：0:Goto 0, 21:Return 0, 02:LoadConst 0, 03:Sto 0, 14:LoadConst 0, 15:Sto 0, 36:LoadConst 0, 27:Mov 0, 38:>=? 0, 09:IfFalseGoto 0, 1810:Mov 0, 111:Mov 0, 312:Add 0, 013:Sto 0, 114:Mov 0, 315:IncV ar 0, 116:Sto 0, 317:Goto 0, 6 ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――While函数结构代码：vara, i: integer;begini := 0;a := 0;while i <= 100 dobegina := a +i;i := i +1;end;end;――――――――――――――――――――――――――――――――――－编译状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = unsigned[静], OffPos = 0[2]i = unsigned[静], OffPos = 0常量[0]Number = 0[静], OffPos = 0[1]Number = 0[静], OffPos = 0[2]Number = 100[静], OffPos = 0[3]Number = 1[静], OffPos = 0方法ID = 0, Name = ShowMessage, MethodType = 过程, ParamList = (0), DynaV arList = (), Addr = 1＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋运行状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = 5050[静], OffPos = 0[2]i = 101[静], OffPos = 0汇编语句：0:Goto 0, 21:Return 0, 02:LoadConst 0, 03:Sto 0, 24:LoadConst 0, 15:Sto 0, 16:Mov 0, 27:LoadConst 0, 28:<=? 0, 09:IfFalseGoto 0, 1910:Mov 0, 111:Mov 0, 212:Add 0, 013:Sto 0, 114:Mov 0, 215:LoadConst 0, 316:Add 0, 017:Sto 0, 218:Goto 0, 6 ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――Repeat函数结构代码：vara, i: integer;begina := 0;i := 0;repeata := a + i;i := i + 1;until i > 100;end; ――――――――――――――――――――――――――――――――――－编译状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = unsigned[静], OffPos = 0[2]i = unsigned[静], OffPos = 0常量[0]Number = 0[静], OffPos = 0[1]Number = 0[静], OffPos = 0[2]Number = 1[静], OffPos = 0[3]Number = 100[静], OffPos = 0方法ID = 0, Name = ShowMessage, MethodType = 过程, ParamList = (0), DynaV arList = (), Addr = 1＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋运行状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = 5050[静], OffPos = 0[2]i = 101[静], OffPos = 0汇编语句：0:Goto 0, 21:Return 0, 02:LoadConst 0, 03:Sto 0, 14:LoadConst 0, 15:Sto 0, 26:Mov 0, 17:Mov 0, 28:Add 0, 09:Sto 0, 110:Mov 0, 211:LoadConst 0, 212:Add 0, 013:Sto 0, 214:Mov 0, 215:LoadConst 0, 316:>? 0, 017:IfFalseGoto 0, 6 ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――Fun函数结构代码：vara, i: integer;function fun1(arg1, arg2: integer): integer;beginResult := arg1 + arg2;end;begina := 0;for i := 1 to 100 dobegina := fun1(a, i);end;end;――――――――――――――――――――――――――――――――――－编译状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = unsigned[静], OffPos = 0[2]i = unsigned[静], OffPos = 0[3]arg1 = unsigned[参], OffPos = 0[4]arg2 = unsigned[参], OffPos = 1[5]Result = unsigned[动], OffPos = 2常量[0]Number = 0[静], OffPos = 0[1]Number = 1[静], OffPos = 0[2]Number = 100[静], OffPos = 0方法ID = 1, Name = fun1, MethodType = 函数, ParamList = (3, 4), DynaV arList = (5), Addr = 2 ＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋运行状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = 5050[静], OffPos = 0[2]i = 101[静], OffPos = 0[3]arg1 = unsigned[参], OffPos = 0[4]arg2 = unsigned[参], OffPos = 1[5]Result = unsigned[动], OffPos = 2汇编语句：0:Goto 0, 71:Return 0, 02:Mov 0, 33:Mov 0, 44:Add 0, 05:Sto 0, 56:Return 0, 07:LoadConst 0, 08:Sto 0, 19:LoadConst 0, 110:Sto 0, 211:LoadConst 0, 212:Mov 0, 213:>=? 0, 014:IfFalseGoto 0, 2315:Mov 0, 116:Mov 0, 217:Call 0, 118:Sto 0, 119:Mov 0, 220:IncV ar 0, 121:Sto 0, 222:Goto 0, 11 ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――If 结构代码：vara, i: integer;begina := 2;if a = 1 thenbegini := 10;endelse begini := 100;end;end;――――――――――――――――――――――――――――――――――－编译状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = unsigned[静], OffPos = 0[2]i = unsigned[静], OffPos = 0常量[0]Number = 2[静], OffPos = 0[1]Number = 1[静], OffPos = 0[2]Number = 10[静], OffPos = 0[3]Number = 100[静], OffPos = 0方法ID = 0, Name = ShowMessage, MethodType = 过程, ParamList = (0), DynaV arList = (), Addr = 1 ＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋运行状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = 2[静], OffPos = 0[2]i = 100[静], OffPos = 0汇编语句：0:Goto 0, 21:Return 0, 02:LoadConst 0, 03:Sto 0, 14:Mov 0, 15:LoadConst 0, 16:=? 0, 07:IfFalseGoto 0, 118:LoadConst 0, 29:Sto 0, 210:Goto 0, 1311:LoadConst 0, 312:Sto 0, 2 ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――递归结构代码：vara, b: integer;function f1(arg: integer): integer;beginif arg <= 1 thenbeginResult := 1;endelse beginResult := arg * f1(arg - 1);end;end;begina := 10;b := f1(a);ShowMessage(b);end; ――――――――――――――――――――――――――――――――――－编译状态下：变量[0]str = unsigned[参], OffPos = 0[1]a = unsigned[静], OffPos = 0[2]b = unsigned[静], OffPos = 0[3]arg = unsigned[参], OffPos = 0[4]Result = unsigned[动], OffPos = 1常量[0]Number = 1[静], OffPos = 0[1]Number = 1[静], OffPos = 0[2]Number = 1[静], OffPos = 0[3]Number = 10[静], OffPos = 0方法ID = 1, Name = f1, MethodType = 函数, ParamList = (3), DynaV arList = (4), Addr = 2 ＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋＋运行状态下：变量：无汇编语句：Goto 0, 171:Return 0, 02:Mov 0, 33:LoadConst 0, 04:<=? 0, 05:IfFalseGoto 0, 96:LoadConst 0, 17:Sto 0, 48:Goto 0, 169:Mov 0, 310:Mov 0, 311:LoadConst 0, 212:Sub 0, 013:Call 0, 114:Mul 0, 015:Sto 0, 416:Return 0, 017:LoadConst 0, 318:Sto 0, 119:Mov 0, 120:Call 0, 121:Sto 0, 222:Mov 0, 223:Call 0, 0 ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――实验二：词法分析（一）实验目的:调试一个词法分析程序，加深对词法分析原理的理解实验内容：（1）设一小型编译程序关于高级语言有如下的规定：高级语言程序具有四种基本结构：顺序结构﹑选择结构﹑循环结构和过程。