动手写一个最简单的编译器，又名: 学习编译原理，写编译器（第五天）

学习编译原理，写编译器（第五天）

目录

• 学习编译器第五天
• 编译器概述
  • 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

1. 定义标记：为C语言中的关键字、运算符、字面量等定义正则表达式。
2. 生成扫描器：Flex将这些定义转换成C语言代码，用于词法分析。

步骤2：设置Bison

1. 定义文法：为C语言的语法结构定义上下文无关文法规则。
2. 生成解析器：Bison根据这些规则生成C语言代码，用于构建AST。

步骤3：集成Python

1. 遍历AST：使用Python访问由Bison生成的AST。
2. 语义分析：检查变量定义、类型匹配等。
3. 生成中间代码：生成简单的中间表示（如三地址代码）。

示例

假设我们正在编写一个能够解析如下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 <stdio.h>
#include <stdlib.h>
#include <string.h>

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 <num> NUMBER
%type <node> expression

%%

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命令

或者

1. 赋予**run_compiler.sh执行权限：chmod +x run_compiler.sh**。
2. 运行脚本并传递C源文件作为参数：./run_compiler.sh input.c。

注意事项

• 确保所有的路径和文件名都与你的实际文件相匹配。
• 这个Makefile和脚本是基于假设的工作流程编写的。根据你的具体实现，可能需要进行相应的调整。
• 你需要在系统中安装Flex、Bison、NASM和GCC。