动手写一个最简单的编译器,又名: 学习编译原理,写编译器(第五天)

2024-01-01 09:23:36

学习编译原理,写编译器(第五天)

目录

  • 学习编译器第五天
  • 编译器概述
    • 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。
  • 检查ab的类型。
  • 生成返回语句的中间代码。

这个示例是非常基础的,只处理了一个简单的加法操作。在实际应用中,编译器需要能够处理更复杂的表达式和操作,并且生成的汇编代码会更加复杂和优化。这个例子仅为了演示目的而简化了这个过程。

要实现一个简单的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。

文章来源:https://blog.csdn.net/lixiemang8887/article/details/135280118
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。