编译原理中间运算改复写规则

1. 什么是编译程序

编译程序指将某一种程序设计语言写的程序翻译成等价的另一种语言的程序的程序, 称之为编译程序

编译程序也称为编译器，是指把用高级程序设计语言书写的源程序，翻译成等价的机器语言格式目标程序的翻译程序。编译程序属于采用生成性实现途径实现的翻译程序。

它以高级程序设计语言书写的源程序作为输入，而以汇编语言或机器语言表示的目标程序作为输出。编译出的目标程序通常还要经历运行阶段，以便在运行程序的支持下运行，加工初始数据，算出所需的计算结果。

编译程序的实现算法较为复杂，这是因为它所翻译的语句与目标语言的指令不是一一对应关系,而是一多对应关系，同时也因为它要处理递归调用、动态存储分配、多种数据类型，以及语句间的紧密依赖关系。

由于高级程序设计语言书写的程序具有易读、易移植和表达能力强等特点，编译程序广泛地用于翻译规模较大、复杂性较高、且需要高效运行的高级语言书写的源程序。

(1)编译原理中间运算改复写规则扩展阅读：

编译流程分为了四个步骤:

1.预处理，生成预编译文件（.文件）

2.编译，生成汇编代码（.s文件）

3.汇编，生成目标文件（.o文件）

4.链接，生成可执行文件

2. 编译原理问题：求解

E是文法开头。ε代表终结符号(推理中代表终点或结果，程序语言中代表常量等)。E T 这些大写字母一般代表非终结符号（这些代表中间过程，非结果。程序中代表函数等等）。开始是E。因为有个G(E)。E就是文法开始符号。推导就有E开始，它也是一个非终结符(代表函数、或者一个推导过程，类似于程序中的main(c++)、winmain(vc++)、dllmain(dll)等主函数）。

1算术表达式文法：这个文法是一个递归文法。计算机进行逻辑推导时会走很多弯路（类似于遍历一颗树的过程）。为了不让计算机走弯路（提高效率的目的），可以变换为第二种文法。这种文法消除了递归（消除了歧义，类似于后缀表达式），使计算机可以一条直线走到底儿推导出结果。

我也很久没看编译原理了。 呵呵

3. 编译原理有有符号un-1.u=un吗

编译程序把源程序翻译为目标程序。根据源程序的语言种类，翻译程序可以分为汇编程序与编译程序。与之相对，解释程序是对源程序进行解释执行的程序。相应的可以将高级语言分为

编译型 C/C++, Swift, etc.
解释型 Python, javascript, etc.
混合型 Java, etc.
本文重点放在编译程序的设计上。典型的编译程序具有 7 77 个逻辑部分

对源程序扫描一次被称为一遍 (pass)。典型的一遍扫描编译程序有如下形式

通常将中间代码生成前的分析部分称为编译器的前端，其后的综合部分则被称为后端。这样就把一个编译程序分为了与源语言相关和与目标机有关的两个独立的部分，降低了程序的耦合。假设 llvm 编译器 支持 M MM 种源语言到 N NN 种目标语言的编译
传统的编译器如 gcc 可能需要开发 M × N M \times NM×N 个不同的子模块。而 llvm 使用统一的中间语言 llvm Intermediate Representation 只需要 M MM 个前端与 N NN 个后端，大大降低了开发成本。

文法
设非空有穷集合 Σ \SigmaΣ 为一字母表，则其上的符号串为 ∀ s ∈ Σ ∗ \forall s \in \Sigma^*∀s∈Σ
∗
，其中 ∗ *∗ 表示集合的闭包。特别的记 Σ 0 = ε \Sigma^0 = {\varepsilon}Σ
0
=ε 为空串组成的集合。规则通常写作

U : : = x  or  U → x , ∣ U ∣ = 1 , ∣ x ∣ ≥ 0 U ::= x\text{ or }U\rightarrow x,\quad |U| = 1, |x| \ge 0U::=x or U→x,∣U∣=1,∣x∣≥0

其中左部 U UU 是符号，右部 x xx 是有穷符号串。规则的集合 P PP 即可确定一个文法 G GG

<程序> ::= <常量说明><变量说明><函数说明>
<常量说明> ::= {const<常量定义>;}
<常量定义> ::= int<标识符>=<整数>{,<标识符>=<整数>}|char<标识符>=<字符>{,<标识符>=<字符>}
<变量说明> ::= {<类型标识符><变量定义>;}
<变量定义> ::= <标识符>[<下标>]{,<标识符>[<下标>]}
<下标> ::= '['<无符号整数>']' // <无符号整数>表示数组元素的个数，其值需大于0
<函数说明> ::= {(<类型标识符>|void)<函数定义>}void<主函数>
<函数定义> ::= <标识符>'('<参数表>')'<复合语句>
<参数表> ::= [<类型标识符><标识符>{,<类型标识符><标识符>}]
<主函数> ::= main'('')'<复合语句>

<复合语句> ::= '{'<常量说明><变量说明>{<语句>}'}'
<语句> ::= <条件语句>|'{'{<语句>}'}'|<函数调用语句>;|<赋值语句>;|<读语句>;|<写语句>;|<返回语句>;|;
<条件语句> ::= <if语句>|<while语句>|<do语句>|<for语句>
<if语句> ::= if'('<条件>')'<语句>[else<语句>]
<while语句> ::= while'('<条件>')'<语句>
<do语句> ::= do<语句>while'('<条件>')'
<for语句> ::= for'('<标识符>=<表达式>;<条件>;<标识符>=<标识符><加法运算符><无符号整数>')'<语句>
<条件> ::= <表达式>[<关系运算符><表达式>] // 表达式为0条件为假，否则为真
<函数调用语句> ::= <标识符>'('[<表达式>{,<表达式>}]')'
<赋值语句> ::= <标识符>['['<表达式>']']=<表达式>
<读语句> ::= scanf'('<标识符>{,<标识符>}')'
<写语句> ::= printf'('<字符串>[,<表达式>]')'|printf'('<表达式>')'
<返回语句> ::= return['('<表达式>')']

<表达式> ::= [<加法运算符>]<项>{<加法运算符><项>} // [+|-]只作用于第一个<项>
<项> ::= <因子>{<乘法运算符><因子>}
<因子> ::= <标识符>['['<表达式>']']|'('<表达式>')'|<整数>|<字符>|<函数调用语句>
<整数> ::= [<加法运算符>]<无符号整数>

<标识符> ::= <字母>{<字母>|<数字>}
<无符号整数> ::= <非零数字>{<数字>}|0
<数字> ::= 0|<非零数字>
<非零数字> ::= 1|...|9
<字符> ::= '<加法运算符>'|'<乘法运算符>'|'<字母>'|'<数字>'
<字符串> ::= "{十进制编码为32,33,35-126的ASCII字符}"
<类型标识符> ::= int|char
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
<关系运算符> ::= <|<=|>|>=|!=|==
<字母> ::= _|a|...|z|A|...|Z
复制

上述文法使用扩充的 BNF 表示法进行描述

符号 定义 说明
∣ \vert∣ 或 作用域由括号限定
{ t } n m \{t\}^m_n{t}
n
m
​
将 t tt 重复连接 n ∼ m n \sim mn∼m 次 缺省时 m = ∞ ,   n = 0 m = \infin,\ n = 0m=∞, n=0
[ t ] [t][t] 符号串 t tt 可有可无 等价于 { t } 1 \{t\}^1{t}
1

( t ) (t)(t) 局部作用域 主要用于限定 ∣ \vert∣ 范围
相关概念有

概念 符号 定义 示例
识别符号 Z ZZ 文法中第一条规则的左部符号 <程序>
字汇表 V VV 文法中出现的全部符号 { <程序>, <常量说明>, …, 0, 1, … }
非终结符号集 V n V_nV
n
​
全部规则的左部组成的集合 { <程序>, <常量说明>, <变量说明>, … }
终结符号集 V t V_tV
t
​
V − V n V - V_nV−V
n
​
{ 0, 1, …, _, a, b, … }
设 U : : = u ∈ P U ::= u \in PU::=u∈P 则对于 ∀ x , y ∈ V ∗ \forall x, y \in V^*∀x,y∈V
∗
有直接推导 x U y ⇒ x u y xUy \Rightarrow xuyxUy⇒xuy 。如果 y ∈ V t ∗ y \in V_t^*y∈V
t
∗
​
则 x U y   ⤃   x u y xUy\ ⤃\ xuyxUy ⤃ xuy 称为规范推导。直接推导序列 u 0 ⇒ u 1 ⇒ ⋯ ⇒ u n u_0 \Rightarrow u_1 \Rightarrow \cdots \Rightarrow u_nu
0
​
⇒u
1
​
⇒⋯⇒u
n
​
可简记为

{ u 0 ⇒ + u n n > 0 u 0 ⇒ ∗ u n n ≥ 0 \begin{cases} u_0 \mathop\Rightarrow\limits^+ u_n & n > 0\\ u_0 \mathop\Rightarrow\limits^* u_n & n \ge 0\\ \end{cases}{
u
0
​
⇒
+
u
n
​
u
0
​
⇒
∗
u
n
​
​

n
>
0
n
≥
0
​

进一步定义

句型 V ∗ ∋ x ⇐ ∗ Z V^* \ni x \mathop\Leftarrow\limits^* ZV
∗
∋x
⇐
∗
Z
句子 V t ∗ ∋ x ⇐ + Z V_t^* \ni x \mathop\Leftarrow\limits^+ ZV
t
∗
​
∋x
⇐
+
Z
语言 L ( G ) = { x ∣ x  is sentence } L(G) = \{ x| x\text{ is sentence} \}L(G)={x∣x is sentence}
如果文法 G GG 和 G ′ G'G
′
有 L ( G ) = L ( G ′ ) L(G) = L(G')L(G)=L(G
′
) ，则称这两个文法等价。设 w = x u y w=xuyw=xuy 为一句型，称 u uu 为一个相对于 U ∈ V n U \in V_nU∈V
n
​
的

w ww 的短语 如果 Z ⇒ ∗ x U y ∧ U ⇒ + u Z \mathop\Rightarrow\limits^* xUy \land U \mathop\Rightarrow\limits^+ uZ
⇒
∗
xUy∧U
⇒
+
u
w ww 的简单短语 如果 u uu 是短语且 U ⇒ u U \mathop\Rightarrow\limits uU⇒u
句型的最左简单短语称为句柄。

二义性
文法 G GG 是二义性的，如果 ∃ x ∈ L ( G ) \exist x \in L(G)∃x∈L(G) 使下列条件之一成立

x xx 可以对应两颗不同的语法树
x xx 有两个不同的规范推导

4. 编译原理常用的查填表技术有哪些它们各自的特点是什么

解答如下：
技术： 删除公共子表示式;复写传播;删除无用代码;代码外提;强度削弱;删除归纳变量;合并常量。
编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质，高度抽象。

5. 帮我看看下面 编译原理 的题目: 谢谢!

23. D

24. D

25. A

26. D

27. C

28. B

29. D

30. A

31. A

32. B

33. A

34. 不太确定，蒙D

35. A

36. 不太确定，蒙A

37. D

38. C

39. D

40. 不知道

二、

1. A,B

2. A,D

3. C,D

4. A,C

5. A,B,D

6. A,B,C,D
   

6. 为什么要采用中间代码中间代码有哪几种形式（编译原理）

采用中间代码是把源程序映射成中间代码表示，再映射成目标代码的工作分在几个阶段进行，使编译算法更加清晰。中间代码有四种形式：

1、逆波兰表示

逆波兰表示又称后缀表示法，它是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式。

2、四元式

四元式也是一种比较普遍采用的中间代码形式，

其形式为：（OP，ARG1，ARG2，RESULT）

3、三元式

三元式表示是与四元式类似的一种表示法，所不同的仅是三元式中没有表示运算结果的部分，凡要涉及到运算结果的均用三元式的位置或序号来代替。

4、树表示

树形表示是三元式的翻版。在树的表示中，树叶均为运算对象，即常量或变量，其他结点表示运算符。表达式的树形表示很容易实现：简单变量或常量的树就是该变量或常量自身。

(6)编译原理中间运算改复写规则扩展阅读

中间语言的优点：

1、中间语言与具体机器特性无关，一种中间语言可以为生成多种不同型号的目标机的目标代码服务。

2、可对中间语言进行与机器无关的优化，有利于提高目标代码的质量。

对于中间语言，要求其不但与机器无关，而且有利于代码生成。