编译原理Lab. 1 初代编译器实验说明和要求

Lab. 1 初代编译器实验说明和要求

一、初代编译器功能描述

初代编译器将 C 语言顺序语句序列翻译为等价的汇编程序，所输出的汇编程序符合 x86 汇编语言格式要求，能够被后续的汇编器翻译为可执行程序运行。

二、初代编译器文法要求

初代编译器能够处理的文法如下所示：

关键字：int、 return
标识符：单个英文字母
常量：十进制整型，如 1、223、10 等
操作符：=、+、-、*、/、(、)
分隔符：;
语句：表达式语句、赋值语句，其中表达式语句包含括号及括号嵌套；

三、初代编译器测试样例

测试用例难度分为两个等级：其中第一个等级每个表达式中操作符优先级相同，且无括号；第二个等级同一个表达式中会有不同优先级，且包含有嵌套的括号。测试用例中，第一个等级测试用例占比 90%，第二个等级的测试用例占比 10%。

所有输入测试样例文件中单词之间均由空格或者回车分隔，输入文件中可能存在多个连续的空格或者回车。

评分依据 return 的值是否符合预期。

等级一输入样例：

int a ;
int b ;
int d ;
a = 1 ;
b = 2 ;
d = a + b ;
return d ;
（预期返回值为 3）

等级一输出样例 x86：

mov DWORD PTR [ebp-4], 0 # int a
mov DWORD PTR [ebp-8], 0 # int b
mov DWORD PTR [ebp-12], 0 # int d
mov DWORD PTR [ebp-4], 1 # a = 1
mov DWORD PTR [ebp-8], 2 # b = 2
mov eax, DWORD PTR [ebp-4] # d = a + b
push eax
mov eax, DWORD PTR [ebp-8]
push eax
pop ebx
pop eax
add eax, ebx
push eax
pop eax
mov DWORD PTR [ebp-12], eax
mov eax, DWORD PTR [ebp-12] # return d

等级二输入样例：

int a ;
int b ;
int c ;
int d ;
a = 1 ;
b = 2 ;
c = 3 ;
d = ( a + b * 2 ) / c – 3 ;
return d ;
（预期返回值为-2）

等级二输出样例 x86：

用例 2 的期待输出: (你的输出中不必输出#行的内容)
# int a ;
mov DWORD PTR [ebp-4], 0
# int b ;
mov DWORD PTR [ebp-8], 0
# int c ;
mov DWORD PTR [ebp-12], 0 
# int d ;
mov DWORD PTR [ebp-16], 0
# a = 1 ;
mov DWORD PTR [ebp-4], 1
# b = 2 ;
mov DWORD PTR [ebp-8], 2
# c = 3 ;
mov DWORD PTR [ebp-12], 3
# d = ( a + b * 2 ) / c - 3
mov eax, DWORD PTR [ebp-4]
push eax
mov eax, DWORD PTR [ebp-8]
push eax
mov eax, 2
push eax
pop ebx
pop eax
imul eax, ebx
push eax
pop ebx
pop eax
add eax, ebx
push eax
mov eax, DWORD PTR [ebp-12]
push eax
pop ebx
pop eax
cdq
idiv ebx
push eax
mov eax, 3
push eax
pop ebx
pop eax
sub eax, ebx
push eax
pop eax
mov DWORD PTR [ebp-16], eax
# return d
mov eax, DWORD PTR [ebp-16]

四、初代编译器提交要求

实现语言：C++（语言标准 c++14）

编译环境：g++ -11

测试环境：gcc -11

提交内容：单个 cpp 源文件，文件名称为 compilerlab1.cpp

输入输出：实现的编译器有一个命令行参数，用于指明输入文件路径，编译器从该路径读取源码，并向 stdout 输出编译结果。

注：g++用于编译你提交的编译器实验源码，gcc 用于将你的编译器实验输出的 x86 汇编码编译成可执行文件，用于测试。

五、初代编译器实验测试框架说明

为了方便测试，实验提供了一个测试框架，用于测试你的编译器实验。

x86 汇编的测试框架：

.intel_syntax noprefix # 使用 Intel 语法
.global main # 声明 main 函数为全局符号，这使得链接器能够识别程序
的入口点。
.extern printf # 声明外部函数 printf，表示该函数在其他地方定义，通
常是 C 标准库中。
.data # 开始数据段，用于定义程序中的初始化数据。
format_str:.asciz "%d\n" # 定义一个用于 printf 的格式字符串，输出整数并换行。
.text # 开始代码段，包含程序的实际指令。
main:push ebp # 将基指针寄存器 ebp 的当前值压入堆栈，保存上一个函
数栈帧的基指针mov ebp, esp # 将栈指针 esp 的值复制到基指针 ebp ，设置新的栈帧
基指针sub esp, 0x100 # 从栈指针 esp 减去 256 字节，为局部变量分配栈空间
##################################################
##
## 你的编译器实验输出的 x86 汇编码将被插入到这里
##
################################################### 打印 d (当前 eax 的值)push eax # 将结果 (eax 的值) 作为 printf 的参数push offset format_str # 将格式字符串的地址作为 printf 的参数call printf # 调用 printf 函数add esp, 8 # 清理栈# 恢复 eax 的值并退出 mainpop eaxleaveret

你的编译器实验输出的 x86 汇编码将会被插入到上述框架中。

为了便于评测，本实验框架将会自动调用 C 库的 printf 函数，输出你的编译器实验输出的 x86 汇编码中的返回值（即 eax 的内容）。

代码与思路

考虑到代码会查重，以及隔壁3月16号大哥的惨案，我不会给出具体的代码。（至少要过半年我才会补上代码）

请同学们自己完成代码。

我会给出一些实验注意事项，该部分主要阐述本人在做该实验时踩过的坑，为大家提供一部分参考。

1. 注意按照平台要求的命令行输入输出，否则提交无效
2. 关于测试用例8：需要处理可能出现的回车，可能出现一条语句中间被回车截断，如

int a ;
a 
= 
1
;			// 一条语句 a = 1 ; 被拆成了多行输入
return a
;
// 还可能会出现同一行多条语句，例如：
int b ; int c ; b = 1 ; c = 2 ;

请注意以上情况。

3. 关于测试用例3和7：注意处理直接赋变量的值的语句，如

int a ;
int b ;
a = 1 ;			// 对于这一句，直接把1存入a即可，即 mov DWORD PTR [ebp-4], 1 
b = a ;			// 对于这一句，容易写成把a的值直接mov到b中；然而这样做是错的，要先从a取出放到eax，再从eax取出放到b
return b ;

这里再贴两组用例供大家测试。

输入用例 3: (试试直接赋值,顺便试试大写字母)

int a ;
int A ;
int B ;
a = 1 ;
A = a ;
B = A / a ;
return B ;

用例 3 的期待输出: (你的输出不必像我这里特意搞空行)

mov DWORD PTR [ebp-4], 0mov DWORD PTR [ebp-8], 0mov DWORD PTR [ebp-12], 0mov DWORD PTR [ebp-4], 1mov eax, DWORD PTR [ebp-4]
mov DWORD PTR [ebp-8], eaxmov eax, DWORD PTR [ebp-8]
push eax
mov eax, DWORD PTR [ebp-4]
push eax
pop ebx
pop eax
cdq
idiv ebx
push eax
pop eax
mov DWORD PTR [ebp-12], eaxmov eax, DWORD PTR [ebp-12]

输入用例 4: (莫名其妙的换行)

int
p
; int q ; p =
1 
; 
q
= p 
+
p ; return 
q 
;

用例 4 的期待输出: (你的输出不必像我这里特意搞空行)

mov DWORD PTR [ebp-4], 0mov DWORD PTR [ebp-8], 0mov DWORD PTR [ebp-4], 1mov eax, DWORD PTR [ebp-4]
push eax
mov eax, DWORD PTR [ebp-4]
push eax
pop ebx
pop eax
add eax, ebx
push eax
pop eax
mov DWORD PTR [ebp-8], eaxmov eax, DWORD PTR [ebp-8]

以上。

someday，我会把我的代码补充进来，顺便在git上再发一份

但不是现在:)

---

发布后的一小时后补充

我忘记写思路了2333

你可以直接 if ：

• 如果遇到了 int，就输出 mov DWORD PTR [ebp-%d], 0
• 如果遇到了 =，就说明是等式，可能是赋值，或可能是算式
• 如果遇到了 return，就输出 mov eax, DWORD PTR [ebp-%d]，并结束程序

对于遇到了 =：

• 右边只有一个数字
• 右边只有一个字母
• 如果不是前两者，说明是算式

如果是算式：

• 用我们以前学过的和栈有关的知识去做
• 下面是我的处理手段
  • 定义两个栈：op 用来存储符号，v 用来存储值
  • 如果是数字
  • 如果是字母
  • 如果既不是数字也不是字母，那就说明是符号：
    • 如果是 (
    • 如果是 )
    • 如果是 * 或 /
    • 如果是 + 或 -
    • 当然，你也可以先转换成前缀表或者后缀表达式，再用相应的方法处理，自己去百度吧

你也可以使用正则表达式

如果这些方法都不合你的胃口，那你问问身边的人，方法真的很多。

我就点到为止吧，剩下的靠你们自己了（笔芯）。

祝大家早日AC

如果有什么思路上的问题或者编译上的问题总之跟这个实验有关的都可以问，我要是有空会回答的。