下载文档原格式
第一章1．典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。
2. 实现编译程序的主要方法有哪些？答：主要有：转换法、移植法、自展法、自动生成法。
3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？答：编译法、解释法。
4. 编译方式和解释方式的根本区别是什么？答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。
第二章1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关系如何？答：1）0型文法、1型文法、2型文法、3型文法。
2）2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。
答：Z→SME | BS→1|2|3|4|5|6|7|8|9M→ε | D | MDD→0|SB→2|4|6|8E→0|B3. 设文法G为：N→ D|NDD→ 0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。
答：N⇒ND⇒N3⇒ND3⇒N23⇒D23⇒123N⇒ND⇒NDD⇒DDD⇒1DD⇒12D⇒123N⇒ND⇒N1⇒ND1⇒N01⇒D01⇒301N⇒ND⇒NDD⇒DDD⇒3DD⇒30D⇒301N⇒ND⇒N1⇒ND1⇒N31⇒ND31⇒N431⇒ND431⇒N5431⇒D5431⇒75431N⇒ND⇒NDD⇒NDDD⇒NDDDD⇒DDDDD⇒7DDDD⇒75DDD⇒754DD⇒7543D⇒75431 4. 证明文法S→iSeS|iS| i是二义性文法。
答：对于句型iiSeS存在两个不同的最左推导：S⇒iSeS⇒iiSesS⇒iS⇒iiSeS所以该文法是二义性文法。
![编译原理[张素琴]第2版答案清华大学出版社](https://img.taocdn.com/s1/m/7c0785a8cd22bcd126fff705cc17552706225e45.png)
《编译原理》课后习题第1章引论第1题解释下列术语：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。
（2）源程序：源语言编写的程序称为源程序。
（3）目标程序：目标语言书写的程序称为目标程序。
（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。
通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。
（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。
（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。
第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。
答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。
其各部分的主要功能简述如下。
词法分析程序：输入源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。
语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。
语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。
中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。
中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。
目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
表格管理程序：负责建立、填写和查找等一系列表格工作。
表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。
编译原理实验报告一、实验目的编译原理是计算机科学中的重要学科，它涉及到将高级编程语言转换为计算机能够理解和执行的机器语言。
本次实验的目的是通过实际操作和编程实践，深入理解编译原理中的词法分析、语法分析、语义分析以及中间代码生成等关键环节，提高我们对编译过程的认识和编程能力。
二、实验环境本次实验使用的编程语言为C+＋，开发环境为Visual Studio 2019。
此外，还使用了一些相关的编译工具和调试工具，如 GDB 等。
三、实验内容（一）词法分析器的实现词法分析是编译过程的第一步，其任务是将输入的源程序分解为一个个单词符号。
在本次实验中，我们使用有限自动机的理论来设计和实现词法分析器。
首先，定义了各种单词符号的类别，如标识符、关键字、常量、运算符等。
然后，根据这些类别设计了相应的状态转换图，并将其转换为代码实现。
在实现过程中，使用了正则表达式来匹配输入字符串中的单词符号。
对于标识符和常量等需要进一步处理的单词符号，使用了相应的规则进行解析和转换。
（二）语法分析器的实现语法分析是编译过程的核心环节之一，其任务是根据给定的语法规则，分析输入的单词符号序列是否符合语法结构。
在本次实验中，我们使用了递归下降的语法分析方法。
首先，根据实验要求定义了语法规则，并将其转换为相应的递归函数。
在递归函数中，通过对输入单词符号的判断和处理，逐步分析语法结构。
为了处理语法错误，在分析过程中添加了错误检测和处理机制。
当遇到不符合语法规则的输入时，能够输出相应的错误信息，并尝试进行恢复。
（三）语义分析及中间代码生成语义分析的目的是对语法分析得到的语法树进行语义检查和语义处理，生成中间代码。
在本次实验中，我们使用了三地址码作为中间代码的表示形式。
在语义分析过程中，对变量的定义和使用、表达式的计算、控制流语句等进行了语义检查和处理。
对于符合语义规则的语法结构，生成相应的三地址码指令。
四、实验步骤（一）词法分析器的实现步骤1、定义单词符号的类别和对应的正则表达式。
编译原理中间代码生成在编译原理中，中间代码生成是编译器的重要阶段之一、在这个阶段，编译器将源代码转换成一种中间表示形式，这种中间表示形式通常比源代码抽象得多，同时又比目标代码具体得多。
中间代码既能够方便地进行优化，又能够方便地转换成目标代码。
为什么需要中间代码呢？其一，中间代码可以方便地进行编译器优化。
编译器优化是编译器的一个核心功能，它能够对中间代码进行优化，以产生更高效的目标代码。
在中间代码生成阶段，编译器可以根据源代码特性进行一些优化，例如常量折叠、公共子表达式消除、循环不变式移动等。
其二，中间代码可以方便地进行目标代码生成。
中间代码通常比较高级，比目标代码更具有表达力。
通过中间代码，编译器可以将源代码转换成与目标机器无关的形式，然后再根据目标机器的特性进行进一步的优化和转换，最终生成目标代码。
中间代码生成的过程通常可以分为以下几步：1.词法分析和语法分析：首先需要将源代码转换成抽象语法树。
这个过程涉及到词法分析和语法分析两个步骤。
词法分析将源代码划分成一个个的词法单元，例如标识符、关键字、运算符等等。
语法分析将词法单元组成树状结构，形成抽象语法树。
2.语义分析：在语义分析阶段，编译器会对抽象语法树进行静态语义检查，以确保源代码符合语言的语义规定。
同时，还会进行类型检查和类型推导等操作。
3.中间代码生成：在中间代码生成阶段，编译器会将抽象语法树转换成一种中间表示形式，例如三地址码、四元式、特定的中间代码形式等。
这种中间表示形式通常比较高级，能够方便进行编译器的优化和转换。
4.中间代码优化：中间代码生成的结果通常不是最优的，因为生成中间代码时考虑的主要是功能的正确性，并没有考虑性能的问题。
在中间代码生成之后，编译器会对中间代码进行各种优化，以产生更高效的代码。
例如常量折叠、循环优化、死代码删除等等。
5.中间代码转换：在完成了中间代码的优化之后，编译器还可以对中间代码进行进一步的转换。
这个转换的目的是将中间代码转换成更具体、更低级的形式，例如目标机器的汇编代码。
编译原理中的中间代码生成编译原理是计算机科学的一门重要课程。
在编译器的构造过程中，中间代码生成是其核心部分之一。
它是将源代码翻译为目标代码的重要中间阶段。
中间代码生成的过程涉及到链表、树，生成三元式、四元式等多种中间形式。
本文将介绍中间代码生成的过程和其在编译中的作用。
一、中间代码的概念中间代码是指在源程序和目标程序之间所生成的一系列指令的集合。
目标代码是指机器可执行的二进制代码，而中间代码则是一种可传递、可处理和可修改的编译代码形式。
中间代码属于一种中间状态，它不是源代码也不是目标代码，但可以被转换成目标代码。
中间代码可以基于语法树、语法分析栈、语法分析表进行生成，生成的中间代码需要满足语言语法结构和语义规则。
二、中间代码生成的流程在编译过程中，中间代码生成是指将源代码转换成中间代码的过程。
它是在词法分析、语法分析和语义分析阶段之后完成的。
下面介绍一下中间代码生成的流程。
1.源代码转换为语法树编译器通过词法分析和语法分析将源代码转换成语法树。
语法树是一种树形结构，它记录了源代码中各个语句的组成情况。
2.语法树进行语义分析在语法分析之后，编译器进行语义分析，检查语法树的合法性，然后根据语言的语义规则对语法树进行标注。
标注的内容包括符号表信息、数据类型等。
3.中间代码的生成在语义分析后，编译器进入中间代码的生成阶段，生成语句的中间代码。
中间代码通常采用三元式或四元式等形式。
三元式包含操作符、操作数以及结果的地址，四元式中还包括了类型信息。
4.中间代码优化在中间代码生成的过程中，编译器会尽可能地优化中间代码。
可以对中间代码进行多种优化，如常量合并、变量替换、公共子表达式消除等。
5.中间代码转换为目标代码在中间代码生成后，编译器将中间代码转换为目标代码。
目标代码可以是汇编代码或机器代码等不同形式的二进制代码。
三、中间代码生成优化的意义编译器中间代码优化的目标是提高程序的执行效率和降低其资源消耗。
执行效率的提高可以通过以下方式实现：1.减少内存使用编译器可以通过删除冗余代码、去除死代码和不必要的变量等方式来减少中间代码的内存使用。
《编译原理》常见题型一、填空题1.编译程序的工作过程一般可以划分为词法分析，语法分析，中间代码生成，代码优化(可省) ，目标代码生成等几个基本阶段。
2.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序.3.编译方式与解释方式的根本区别在于是否生成目标代码 .5.对编译程序而言，输入数据是源程序，输出结果是目标程序 .7.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。
8.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。
其中，词法分析器用于识别单词。
10.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。
12.产生式是用于定义语法成分的一种书写规则。
13.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S=>*x,x∈VT*} 。
14.设G是一个给定的文法，S是文法的开始符号，如果S*⇒x（其中x∈V*），则称x是文法的一个句型。
15.设G是一个给定的文法，S是文法的开始符号，如果S*⇒x(其中x∈V T*)，则称x是文法的一个句子。
16.扫描器的任务是从源程序中识别出一个个单词符号。
17.语法分析最常用的两类方法是自上而下和自下而上分析法。
18.语法分析的任务是识别给定的终结符串是否为给定文法的句子。
19.递归下降法不允许任一非终结符是直接左递归的。
20.自顶向下的语法分析方法的关键是如何选择候选式的问题。
21.递归下降分析法是自顶向下分析方法。
22.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。
23.自底向上的语法分析方法的基本思想是：从给定的终结符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。
理解编译原理和优化技术对代码执行的影响编译原理和优化技术是程序执行过程中非常重要的环节，它们可以对代码执行产生深远的影响。
编译原理主要负责将源代码转化为机器可以执行的指令，而优化技术则负责提高代码执行效率和性能。
本文将探讨编译原理和优化技术对代码执行的影响，并分析它们的作用和原理。
一、编译原理对代码执行的影响编译原理是计算机科学中的一个重要概念，它主要研究源代码如何转化为可执行代码的过程。
编译原理包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等阶段，每个阶段都对代码执行有着直接的影响。
1.词法分析词法分析是源代码的第一步解析过程，它负责将源代码分解为词法单元，比如标识符、关键字、操作符等。
词法分析的结果直接决定了后续语法分析和语义分析的顺利进行，因此词法分析的质量直接影响了代码执行的效率和正确性。
2.语法分析语法分析是编译原理中非常重要的一个环节，它负责将词法单元组成的字符串解析为语法结构，并生成语法树或者语法图。
语法分析的质量决定了程序的结构是否合理，进而影响了后续的优化和生成代码的过程。
3.语义分析语义分析是编译原理中的关键环节，它负责检测源代码中的语法错误和语义错误，比如类型错误、作用域错误等。
语义分析的质量直接决定了程序的执行正确性和可靠性，因此它对代码执行有着直接的影响。
4.中间代码生成中间代码是指在源代码和目标代码之间的一种抽象表示，它可以是三地址码、四元式、抽象语法树等形式。
中间代码生成的质量直接影响了后续的代码优化和生成代码的效果，因此它对代码执行有着深远的影响。
5.代码优化代码优化是编译原理中非常重要的一个环节，它负责提高程序执行的效率和性能。
代码优化可以分为多个层次，比如局部优化、全局优化、线程级优化、并行优化等。
代码优化的质量决定了程序的执行效率和性能，对代码执行有着直接的影响。
6.目标代码生成目标代码生成是编译原理中的最后一个环节，它负责将中间代码转化为目标机器可以执行的指令。
第十章代码优化某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。
所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。
优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化。
一般，优化工作阶段可在中间代码生成之后和（或）目标代码生成之后进行。
中间代码的优化是对中间代码进行等价变换。
目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。
另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。
局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。
循环优化对循环中的代码进行的优化。
全局优化是在整个程序范围内进行的优化。
本章重点：局部优化基本块的DAG表示第一节优化技术简介为了说明问题，我们来看下面这个例子，源程序是：P :=0For I :=1 to 20 doP :=P+A[I]*B[I];经过编译得到的中间代码如图10-1-1所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定机器按字节编址。
那么，对于这个中间代码段，可进行如下这些优化。
1、删除多余运算（删除公共子表达式）优化的目的在于使目标代码执行速度较快。
图10-1-1中间代码（3）和（6）中都有4＊I的运算，而从（3）到（6）没有对I赋值，显然，两次计算机的值是相等的。
所以，（6）的运算是多余的。
我们可以把（6）变换成：T4 :=T1。
这种优化称为删除多余运算或称为删除公共子表达式。
2、代码外提减少循环中代码总数的一个重要办法是代码外提。
这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面。
使之只在循环外计算一次，上例中，我们可以把（4）和（7）提到循环外。
经过删除多余运算和代码外提后，代码变成图10-1-2。
实验三中间的代码优化某些编译程序在中间代码或目标代码生产之后要对其进行优化，所谓优化就是对代码进行等价的变换。
而变换后的代码运行结果与变换前的代码运行结果相同。
而运行速度加快或占用内存空间减少。
中间的代码优化就是对中间代码进行等价的变换。
基本块的有向图DAG（Directed Acyclic Graph)有向图中任何一条通路都不是环路，则称该有向图为无环路有向图，简称为DAG。
一、实验题目：中间代码的局部优化二、实验目的：掌握局部优化方法、提高机器的运行速度三、实验内容：1 、构造基本块内的优化DAG假设：（1）ni 为已知结点号，n为新结点号；（2）访问各结点信息时，按结点号逆序排序2、完成对下例三类表达式的优化（1）常值表达式的优化（2）公共表达式的优化（3）无用赋值的优化3、输出根据优化的DAG重组四元式四、设计概要：首先要实现表达式中间代码生成，采用递归下降子程序法实现。
E→T{ω0 “push(SYN,w)”T“QUAT” }T→F{ω1”push(SYN,w)”F“QUAT”}F→i“push(SEM,entry(w))”|(E)其中：·push(SYN,w)---当前单词w入符号栈SYN；·push(SEM,entry(w))--- 当前i在符号表中的入口值压入语义栈SEM；·QUAT---生成四元式函数①T:=newtemp;②QT[j]=(SYN[k],SEM[s-1],SEM[s],T);j++;③ pop(SYN,_);pop(SEM,_);pop(SEM,_); push(SEM,T);在对中间代码进行局部优化五、程序代码及运行结果：1.表达式中间代码生成#include<iostream>#include<cstdlib>using namespace std;char str[50];char sem[50];char syn[50];char ch;int i=0;int j=0;int n=0;int p=1;void push_sem(char w){sem[j++]=w;}void push_syn(char w){syn[n++]=w;}void Gen(){char s[2][2];char w;w=sem[--j];if(w>='1'&&w<='9'){s[0][1]=w;s[0][0]=sem[--j];}else{s[0][0]=w;s[0][1]=' ';}w=sem[--j];if(w>='1'&&w<='9'){s[1][1]=w;s[1][0]=sem[--j];}else{s[1][0]=w;s[1][1]=' ';}cout<<"("<<syn[--n]<<","<<s[1][0]<<s[1][1]<<","<<s[0][0]<<s[0][1] <<","<<'t'<<p++<<")"<<endl;push_sem('t');push_sem(p+47);}int F(){int m;int E();if(ch=='('){ch=str[i++];m=E();if(ch==')') ch=str[i++];else{//cout<<"表达式error!"<<endl;return 0;}}else{if((ch>='a'&&ch<='z')||(ch>='1'&&ch<='9')){push_sem(ch);ch=str[i++];}else{//cout<<"表达式error!"<<endl;return 0;}}return 1;}int T(){int k,m,l;k=F();if(k==0){return 0;}while(1){//push_syn(ch);if(ch=='*'){push_syn(ch);ch=str[i++];m=F();if(m==0){return 0;}Gen();}else if(ch=='/'){push_syn(ch);ch=str[i++];l=F();if(l==0){return 0;}Gen();}else break;}return 1;}int E(){int k,m,l;k=T();if(k==0){return 0;}while(1){//push_syn(ch);if(ch=='+'){push_syn(ch);ch=str[i++];m=T();if(m==0){return 0;}Gen();}else if(ch=='-'){push_syn(ch);ch=str[i++];l=T();if(l==0){return 0;}Gen();}else break;}return 1;}int main(){int k,q=0;char w1,w2,w;char s[1][2];cout<<"输入表达式(以'#'结束):";cin>>str;w1=str[i++];w2=str[i++];if(w2!='=') {i=i-2;q=1;}ch=str[i++];k=E();if(q==0){w=sem[--j];if(w>='1'&&w<='9'){s[0][1]=w;s[0][0]=sem[--j];}else{s[0][0]=w;s[0][1]=' ';}cout<<"("<<w2<<","<<s[0][0]<<s[0][1]<<","<<" "<<","<<w1<<")"<<endl;}if(k==0) cout<<"error!"<<endl;else{if(ch=='#') cout<<"OK!"<<endl;else cout<<"error!"<<endl;}return 0;}运行结果：2.代码优化：（采用递归下降子程序法判断表达式是否合法，方法如上）#include <iostream>#include <cstdlib>#include <string.h>using namespace std;int i=1;int j=0,n=0;int p;int m=1;int Ti=0;char prog[100];char ch;char syn[20],sem[50][3];void SEM(void){int i,j;for(i=0;i<50;i++)for(j=0;j<3;j++)sem[i][j]='\0';}struct quat//四元式结构{char result[8];char ag1[8];char op;char ag2[8];}quad[25],newquad[15];struct Ni//节点结构{int pre[2];char op;char bz[25][8];}N[25];void newN(void){int l,j;i++;for(j=0;j<25;j++){for(l=0;l<8;l++){N[i-1].bz[j][l]='\0';}}for(j=0;j<2;j++)N[i-1].pre[j]=0;N[i-1].op='\0';}void dagt(void);void newquat(void);void fuzhi(void);//递归语法分析生成中间代码void E(void);void T(void);void F(void);void pop0(char sz[]);void push0(char sz[],char x);void pop1(char sz[50][3]);void push1(char sz[50][3],char x[3]); void quat1(void);void quat0(char w);void print1(void);void print2(void);char *newT(void){char *p;char m[8];p=(char *)malloc(8);Ti++;itoa(Ti,m,10);strcpy(p+1,m);p[0]='t';return(p);}void main(){p=0;syn[0]='#';SEM();sem[0][0]='#';cout<<"请输入表达式："<<endl;do{cin.get(ch);if(ch != '\n') prog[p++]=ch;}while(ch!='#');p=0;ch=prog[p++];while(ch!='#'){fuzhi();}print1();dagt();newquat();print2();}void fuzhi(void){char temp[3];temp[0]='\0';temp[1]='\0';temp[2]='\0';if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')) {temp[0]=ch;push1(sem,temp);ch=prog[p++];if(ch=='='){push0(syn,ch);ch=prog[p++];E();if(m==0){cout<<"错误1!"<<endl;system("pause"); /////return;}if(ch==';'){ch=prog[p++];quat1();}else{cout<<"错误2!"<<endl;system("pause");return;}}else{cout<<"错误3!"<<endl;system("pause");return;}}else{cout<<"错误4!"<<endl;printf("%d",ch);system("pause");return;}}//E、T、F是递归下降子程序的语法分析void E(void){char w;T();while(ch=='+'||ch=='-'){push0(syn,ch);w=syn[strlen(syn)-1];ch=prog[p++];T();quat0(w);}}void T(void){char w;F();while(ch=='*'||ch=='/'){push0(syn,ch);w=syn[strlen(syn)-1];ch=prog[p++];F();quat0(w);}}void F(void){char temp[3];temp[0]='\0';temp[1]='\0';temp[2]='\0';if(ch=='('){ch=prog[p++];E();if(ch==')'){ch=prog[p++];}else m=0;}else if((ch<='z'&&ch>='a')||(ch<='Z'&&ch>='A')||(ch<='9'&&ch>='0')) {temp[0]=ch;push1(sem,temp);ch=prog[p++];}else m=0;}void push0(char sz[],char x){int top;top=strlen(sz);sz[top]=x;top++;sz[top+1]='\0';}void pop0(char sz[]){int top;top=strlen(sz)-1;sz[top]='\0';}void push1(char sz[50][3],char x[3]) {int top=1;while(sz[top][0])top++;strcpy(sz[top],x);top++;sz[top+1][0]='\0';}void pop1(char sz[50][3]){int top=1;while(sz[top][0])top++;top--;sz[top][0]='\0';sz[top][1]='\0';sz[top][2]='\0';}void quat0(char w){int top=1,i;char *p;while(sem[top][0])top++;strcpy(quad[j].ag1,sem[top-2]);strcpy(quad[j].ag2,sem[top-1]);quad[j].op=w;p=newT();for(i=0;i<8;i++)quad[j].result[i]=p[i];pop1(sem);top--;pop1(sem);top--;for(i=0;i<3;i++)sem[top][i]=quad[j].result[i];sem[top][2]='\0';j++;}void quat1(void){char ag2[8];int top,i;top=1;while(sem[top][0])top++;ag2[0]='_';for(i=1;i<8;i++)ag2[i]='\0';strcpy(quad[j].ag1,sem[top-1]);strcpy(quad[j].ag2,ag2);quad[j].op='=';strcpy(quad[j].result,sem[top-2]);pop0(syn);pop1(sem);pop1(sem);j++;}void print1(void){int i;cout<<"原来的四元组："<<endl;for(i=0;i<j;i++)cout<<(i+1)<<"、("<<quad[i].op<<","<<quad[i].ag1<<","<<quad[i].ag2<<","<<quad[i].result<<")"<<endl;}void dagt(void){int m,n,top,l,tag=0,tag1=0,tag2=0;char temp;for(m=0;m<j;m++){tag=0;for(n=i;n>0;n--)for(l=0;l<25;l++){if(strcmp(quad[m].ag1,N[n-1].bz[l])==0){tag=n;break;}}if(tag!=0){tag1=tag-1;if('0'<quad[m].ag1[0]&&quad[m].ag1[0]<'9')goto N3;else goto N3;}else{if('0'<quad[m].ag1[0]&&quad[m].ag1[0]<'9'){if(quad[m].ag2[0]!='_'){if('0'<quad[m].ag2[0]&&quad[m].ag2[0]<'9'){quad[m].ag1[0]=quad[m].ag1[0]-'0';quad[m].ag2[0]=quad[m].ag2[0]-'0';switch(quad[m].op){case '+':temp=quad[m].ag1[0]+quad[m].ag2[0];break;case '-':temp=quad[m].ag1[0]-quad[m].ag2[0];break;case '*':temp=quad[m].ag1[0]*quad[m].ag2[0];break;case '/':temp=quad[m].ag1[0]/quad[m].ag2[0];break;default:break;}tag=0;for(n=i;n>0;n--)for(l=0;l<25;l++){if(strcmp(quad[m].result,N[n-1].bz[l])==0){tag=n;break;}}if(tag!=0)continue;else{newN();N[i-1].bz[0][0]=temp+'0' ;strcpy(N[i-1].bz[1],quad[m].result);continue;}}else{newN();tag1=i-1;strcpy(N[i-1].bz[0],quad[m].ag1);goto N2;}}else goto N1;}elseN1:{newN();strcpy(N[i-1].bz[0],quad[m].ag1);tag1=i-1;N3:if(quad[m].ag2[0]=='_'){tag=0;for(n=i;n>0;n--)for(l=0;l<25;l++){if(strcmp(quad[m].result,N[n-1].bz[l])==0){tag=n;top=l;break;}}if(tag!=0){for(l=top+1;l<25;l++){strcpy(N[tag-1].bz[l-1],N[tag-1].bz[l]);}goto N5;}else{N5:if(N[i-1].bz[0][1]){if(quad[m].result[1]){top=0;while(N[tag1].bz[top][0])top++;strcpy(N[tag1].bz[top],quad[m].result);continue;}else{temp=N[i-1].bz[0][1];strcpy(N[i-1].bz[0],quad[m].result);top=0;while(N[tag1].bz[top][0])top++;N[i-1].bz[top][0]='t';N[i-1].bz[top][1]=temp;continue;}}else{top=0;while(N[tag1].bz[top][0])top++;strcpy(N[tag1].bz[top],quad[m].result);continue;}}}elseN2:{tag=0;for(n=i;n>0;n--)for(l=0;l<25;l++){if(strcmp(quad[m].ag2,N[n-1].bz[l])==0){tag=n;break;}}if(tag!=0){tag2=tag-1;tag=0;for(n=i;n>0;n--)if((N[n-1].pre[0]==tag1)&&(N[n-1].pre[1]==tag2)){tag=n;break;}if(tag!=0){if(N[tag-1].op==quad[m].op){if(!N[tag-1].bz[0][1]){top=1;while(N[tag-1].bz[top][0])top++;strcpy(N[tag-1].bz[top],quad[m].result);}else if(!quad[m].result[1]){temp=N[tag-1].bz[0][1];strcpy(N[tag-1].bz[0],quad[m].result);top=1;while(N[tag-1].bz[top][0])top++;N[tag].bz[top][0]='t';N[tag].bz[top][1]=temp;}else{top=1;while(N[tag-1].bz[top][0])top++;strcpy(N[tag-1].bz[top],quad[m].result);}continue;}else{newN();N[i-1].op=quad[m].op;strcpy(N[i-1].bz[0],quad[m].result);N[i-1].pre[0]=tag1;N[i-1].pre[1]=tag2;}continue;}else{newN();N[i-1].op=quad[m].op;strcpy(N[i-1].bz[0],quad[m].result);N[i-1].pre[0]=tag1;N[i-1].pre[1]=tag2;continue;}}else{newN();strcpy(N[i-1].bz[0],quad[m].ag2);tag2=i-1;tag=0;for(n=i;n>0;n--)for(l=0;l<25;l++)if(strcmp(quad[m].result,N[n-1].bz[l])==0){tag=n;top=l;break;}if(tag==0){newN();strcpy(N[i-1].bz[0],quad[m].result);N[i-1].op=quad[m].op;N[i-1].pre[0]=tag1;N[i-1].pre[1]=tag2;continue;}else{for(l=top+1;l<25;l++){strcpy(N[tag-1].bz[l-1],N[tag-1].bz[l]);}newN();strcpy(N[i-1].bz[0],quad[m].result);N[i-1].op=quad[m].op;N[i-1].pre[0]=tag1;N[i-1].pre[1]=tag2;}}}}}}}void newquat(void){int l,top;for(l=1;l<i;l++){if(N[l].pre[1]==0&&N[l].pre[0]==0){if(!N[l].bz[0][1]){if(('0'<N[l].bz[0][0])&&(N[l].bz[0][0]<'9'))continue;else{for(top=1;N[l].bz[top][1];top++){if(!N[l].bz[top][0]){strcpy(newquad[n].ag1,N[l].bz[0]);newquad[n].ag2[0]='_';newquad[n].op='=';strcpy(newquad[n].result,N[l].bz[top]);n++;}}}}else continue;}else if(N[l].pre[1]!=0||N[l].pre[0]!=0){strcpy(newquad[n].ag1,N[N[l].pre[0]].bz[0]);strcpy(newquad[n].ag2,N[N[l].pre[1]].bz[0]);newquad[n].op=N[l].op;strcpy(newquad[n].result,N[l].bz[0]);n++;if(!N[l].bz[0][1]){for(top=1;N[l].bz[top][0];top++){if(!N[l].bz[top][1]){strcpy(newquad[n].ag1,N[l].bz[0]);newquad[n].ag2[0]='_';newquad[n].op='=';strcpy(newquad[n].result,N[l].bz[top]);n++;}}}}}}void print2(void){int i;cout<<"优化后的代码:"<<endl;for(i=0;i<n;i++)cout<<(i+1)<<"、("<<newquad[i].op<<","<<newquad[i].ag1<<","<<newquad[i].ag2<<","<<newquad[i].result<<")"<<endl;}运行结果：。
