学习编译原理，写编译器（第五天）
目录
学习编译器第五天编译器概述
1. 词法分析（Flex）2. 语法分析（Bison）3. 语义分析和中间代码生成（Python）4. 汇编文件进行编译5. 生成make文件
实现步骤
步骤1：设置Flex步骤2：设置Bison步骤3：集成Python
示例1. Flex部分（词法分析）2. Bison部分（语法分析）3. Python部分（中间代码生成）注意事项
小试牛刀
使用Flex、Bison和Python编写一个简单的C语言编译器，涉及多个步骤和概念。首先，我们将概述编译器的工作流程，然后详细讲解每个部分的实现，并最后提供一个示例。
编译器概述
编译器主要由两大部分组成：前端和后端。前端包括词法分析（使用Flex）和语法分析（使用Bison），而后端通常涉及中间代码生成、优化和目标代码生成
1. 词法分析（Flex）
目标：将源代码分解为一系列的标记（tokens）。操作：Flex通过定义一组正则表达式来匹配C语言的关键字、标识符、字面量等。
2. 语法分析（Bison）
目标：根据标记构建抽象语法树（AST），检查语法的正确性。操作：Bison使用上下文无关文法（context-free grammar）定义C语言的语法结构。
3. 语义分析和中间代码生成（Python）
目标：根据AST进行语义检查，并生成中间代码。操作：使用Python遍历AST，进行语义检查，并生成简单的中间代码。
4. 汇编文件进行编译
目标：根据AST进行语义检查，并生成中间代码。操作：使用汇编编译器编译asm文件，进行链接，生成可执行文件。
5. 生成make文件
目标：按顺序执行所有步骤。操作：执行这些步骤以生成可执行文件。
实现步骤
步骤1：设置Flex
定义标记：为C语言中的关键字、运算符、字面量等定义正则表达式。生成扫描器：Flex将这些定义转换成C语言代码，用于词法分析。
步骤2：设置Bison
定义文法：为C语言的语法结构定义上下文无关文法规则。生成解析器：Bison根据这些规则生成C语言代码，用于构建AST。
步骤3：集成Python
遍历AST：使用Python访问由Bison生成的AST。语义分析：检查变量定义、类型匹配等。生成中间代码：生成简单的中间表示（如三地址代码）。
示例
假设我们正在编写一个能够解析如下C语言函数的编译器：
int add(int a, int b) {
return a + b;
}
Flex部分
识别整数、加号和括号等。
Bison部分
定义函数、返回语句和表达式的语法规则。
Python部分
遍历函数定义的AST。检查a和b的类型。生成返回语句的中间代码。
这个示例是非常基础的，只处理了一个简单的加法操作。在实际应用中，编译器需要能够处理更复杂的表达式和操作，并且生成的汇编代码会更加复杂和优化。这个例子仅为了演示目的而简化了这个过程。
要实现一个简单的C语言编译器，我们将按照之前讨论的步骤分别实现Flex、Bison和Python部分的代码。请注意，这里提供的是一个非常基础的例子，只涵盖了C语言的一小部分特性。
1. Flex部分（词法分析）
首先，我们需要定义Flex的规则来识别C语言的标记。以下是一个简化的示例，只包括整数、标识符、加号和其他基本元素。
%{
#include "y.tab.h"
%}
digit [0-9]
letter [a-zA-Z]
identifier {letter}({letter}|{digit})*
number {digit}+
%%
"+" return PLUS;
";" return SEMICOLON;
"(" return LPAREN;
")" return RPAREN;
"return" return RETURN;
{number} { yylval.num = atoi(yytext); return NUMBER; }
{identifier}{ yylval.id = strdup(yytext); return IDENTIFIER; }
\\n return EOL;
[ \\t] ; /* ignore whitespace */
. return yytext[0];
%%
2. Bison部分（语法分析）
接下来，我们需要定义Bison的语法规则。这里定义了一个非常基础的语法，只包括赋值和操作符，然后把它传给 Python
%{
#include
#include
#include
typedef struct Node {
char* type;
int value;
struct Node *left, *right;
} Node;
Node* create_node(char* type, int value, Node* left, Node* right) {
Node* node = malloc(sizeof(Node));
node->type = strdup(type);
node->value = value;
node->left = left;
node->right = right;
return node;
}
void print_ast_json(Node* node) {
if (node == NULL) return;
printf("{ \"type\": \"%s\", \"value\": %d", node->type, node->value);
if (node->left || node->right) {
printf(", \"children\": [");
print_ast_json(node->left);
if (node->left && node->right) printf(", ");
print_ast_json(node->right);
printf("]");
}
printf("}");
}
void yyerror(char *s);
int yylex();
%}
%union {
int num;
Node *node;
}
%token
%type
%%
expression:
NUMBER { $$ = create_node("number", $1, NULL, NULL); }
| expression '+' NUMBER { $$ = create_node("add", 0, $1, create_node("number", $3, NULL, NULL)); }
;
%%
int main(void) {
if (yyparse() == 0) {
print_ast_json(root);
}
return 0;
}
void yyerror(char *s) {
fprintf(stderr, "error: %s\n", s);
}
3. Python部分（中间代码生成）
Python，读取从Bison生成的JSON格式的AST， 并生成NASM代码。这个例子中，我们只是简单地打印AST的结构。
import json
import sys
def generate_nasm(node):
if node['type'] == 'number':
return f"mov eax, {node['value']}\n"
elif node['type'] == 'add':
left_code = generate_nasm(node['children'][0])
right_code = generate_nasm(node['children'][1])
return f"{left_code}push eax\n{right_code}pop ebx\nadd eax, ebx\n"
elif node['type'] == 'variable':
return f"mov eax, [{node['name']}]\n" # 假设变量已在某处定义
# 其他类型的处理可以在此添加
else:
return ""
if __name__ == "__main__":
ast_json = sys.stdin.read()
ast = json.loads(ast_json)
nasm_code = generate_nasm(ast)
print(nasm_code)
这个例子中的编译器是非常基础的，只能处理极其简单的C语言结构。实际编写一个完整的C语言编译器需要更多的规则和复杂的逻辑。对于一个初学者来说，这个例子可以作为一个起点来进一步学习和扩展。
要创建一个Makefile来自动化整个编译过程，包括运行Flex和Bison生成词法分析器和语法分析器、使用Python脚本生成NASM代码，以及编译和链接NASM代码，需要确保所有必要的工具和脚本都已经准备好。
我们已经有了以下文件和脚本：
lexer.l：Flex词法分析器定义文件。parser.y：Bison语法分析器定义文件。generate_asm.py：Python脚本，用于生成NASM代码。run_compiler.sh：一个shell脚本，用于运行编译器并生成NASM代码。
测试文件test.c
int add(int a, int b) {
return a + b;
}
为了不用每一次都要输入以此命令。我们写一个脚本把这几个步骤统一起来，输入文件一次性运行
Makefile示例**Makefile**
# 定义编译器和链接器
CC = gcc
NASM = nasm
LD = ld
# 定义目标文件
LEXER = lex.yy.c
PARSER = parser.tab.c parser.tab.h
ASM_FILE = output.asm
OBJECT_FILE = output.o
EXECUTABLE = output
# 默认目标
all: $(EXECUTABLE)
# 编译和链接生成最终的可执行文件
$(EXECUTABLE): $(OBJECT_FILE)
$(LD) $(OBJECT_FILE) -o $(EXECUTABLE)
# 从ASM文件生成目标文件
$(OBJECT_FILE): $(ASM_FILE)
$(NASM) -f elf64 $(ASM_FILE) -o $(OBJECT_FILE)
# 生成NASM文件
$(ASM_FILE): $(LEXER) $(PARSER)
./parser < input.c | python3 generate_asm.py > $(ASM_FILE)
# 生成词法分析器和语法分析器代码
$(LEXER): lexer.l
flex lexer.l
$(PARSER): parser.y
bison -d parser.y
$(CC) lex.yy.c parser.tab.c -o parser
# 清理生成的文件
clean:
rm -f $(LEXER) $(PARSER) $(ASM_FILE) $(OBJECT_FILE) $(EXECUTABLE) parser
.PHONY: all clean
或者用不习惯就
shell脚本**run_compiler.sh**：
#!/bin/bash
# 假设输入文件名作为参数传递
input_file="$1"
# 运行Flex和Bison
flex lexer.l
bison parser.y
gcc lex.yy.c parser.tab.c -o parser
# 生成AST并将其传递给Python脚本
./parser < "$input_file" | python3 generate_asm.py > output.asm
# 编译NASM代码
nasm -f elf64 output.asm -o output.o
ld output.o -o output
echo "Compilation completed. Executable is output."
这样的话就输入make test.c命令
或者
赋予**run_compiler.sh执行权限：chmod +x run_compiler.sh**。运行脚本并传递C源文件作为参数：./run_compiler.sh input.c。
注意事项
确保所有的路径和文件名都与你的实际文件相匹配。这个Makefile和脚本是基于假设的工作流程编写的。根据你的具体实现，可能需要进行相应的调整。你需要在系统中安装Flex、Bison、NASM和GCC。