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

2024-01-01 19:31:51

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

主要学习语法分析器

1. 理解语法分析（Syntax Analysis）

理解语法分析（Syntax Analysis）是编译过程中的关键步骤，有助于理解编译器和解释器如何将源代码转化为可执行代码或解释执行。下面是有关语法分析的基本概念：

1. 什么是语法分析？

语法分析是编译过程中的一个阶段，也称为解析（Parsing）。其主要任务是将输入的源代码文本解析成抽象语法树（Abstract Syntax Tree，AST）或语法分析树（Parse Tree）。这棵树表示了程序的语法结构，可以用于进一步的编译或解释。

2. 为什么需要语法分析？

语法分析的主要目的是验证源代码是否符合编程语言的语法规则。如果源代码有语法错误，编译器或解释器会产生错误信息，指出错误的位置和类型，帮助程序员进行修正。同时，语法分析还将源代码转化成易于处理的数据结构（如语法树），以便进行后续的语义分析和代码生成。

3. 语法规则和文法：

编程语言的语法由一组规则和产生式（也称为文法）定义。这些规则规定了哪些代码结构是合法的，哪些是不合法的。语法分析器的任务就是根据这些规则，将输入的源代码分解成一系列语法单元（tokens）并验证其正确性。

4. 语法树（Syntax Tree）和语法分析树（Parse Tree）：

语法分析阶段会生成语法树或语法分析树，这是一种以层次结构表示源代码语法的树状数据结构。它将程序的结构可视化，有助于后续阶段的分析和转换。

语法树通常比较抽象，只包含关键的语法结构，忽略了细节。
语法分析树包含了更多的细节，甚至包括了每个终结符和非终结符的具体信息。

5. 语法分析器工具：

为了执行语法分析，编译器和解释器通常使用语法分析器生成工具，其中最常见的是 Bison（Yacc 的变种）。这些工具根据指定的文法规则自动生成语法分析器的源代码。

6. 语法分析的阶段：

语法分析通常分为两个阶段：

词法分析（Lexical Analysis）：将源代码分解为词法单元（tokens），如关键字、标识符、运算符等。
语法分析（Syntax Parsing）：将词法单元构建成语法树，并验证其结构是否符合语法规则。

总之，语法分析是编译过程中的关键步骤，它确保源代码的语法正确性，为后续的语义分析和代码生成提供了基础。深入理解语法分析有助于更好地理解编译器和解释器的工作原理。

2. 理解文法

理解上下文无关文法（Context-Free Grammar，CFG）是学习编译器工具如 Bison 的关键，因为CFG用于定义编程语言的语法规则。下面是关于CFG的基本概念：

1. 文法（Grammar）：

文法是一组规则，它们描述了一个语言的结构和构造方式。在编译器领域，文法通常用于描述编程语言的语法。文法包含了一组产生式规则，这些规则定义了语言中各种结构的构造方式。

2. 产生式（Production）：

产生式是文法规则的基本组成部分。它们指定了如何从一个或多个符号（终结符和非终结符）生成一个更复杂的结构。产生式通常采用如下形式：

A -> α

其中，A 是一个非终结符，α 是由终结符和非终结符组成的字符串。这表示在语言中可以用非终结符 A 替换成字符串 α。

3. 终结符（Terminal Symbols）：

终结符是文法中的基本符号，它们是语言中的实际字符或标记。终结符不能被替换或分解，它们是语法规则的终点。

在编程语言中，终结符通常包括关键字、运算符、标识符、常量等。

4. 非终结符（Non-terminal Symbols）：

非终结符是文法中的符号，它们表示语法结构的抽象概念。非终结符可以由一个或多个产生式规则定义，它们可以被替换成其他非终结符或终结符。

在编程语言中，非终结符通常包括语句、表达式、函数定义等高级结构。

5. 上下文无关文法（CFG）：

上下文无关文法是一种特定类型的文法，其中产生式规则的左侧只包含一个非终结符，而右侧可以包含任意组合的终结符和非终结符。CFG 用于描述许多编程语言的语法。

CFG 的形式表示如下：

终结符集合：Σ
非终结符集合：N
产生式规则集合：P
开始符号：S

一个上下文无关文法可以用以下形式表示：

G = (N, Σ, P, S)

6. 推导（Derivation）：

推导是根据文法的产生式规则，从开始符号开始逐步替换，生成一个字符串的过程。推导的结果是一个句子或字符串，它遵循文法规则。

深入理解上下文无关文法是学习编译器工具如 Bison 的重要基础，因为这些工具使用 CFG 来定义编程语言的语法规则。了解文法符号、产生式、终结符、非终结符等基本概念有助于理解和定义语法规则，以及构建编译器的语法分析器。

3. 安装Bison

安装和配置 Bison 工具可以帮助你定义和生成语法分析器，这对于编译器和解释器的开发非常重要。下面是一些常见操作系统上安装和配置 Bison 的步骤：

在 Ubuntu/Debian 上安装 Bison：

在 Ubuntu 或 Debian 系统上，你可以使用包管理器 apt 来安装 Bison：

sudo apt-get update
sudo apt-get install bison

在 CentOS/RHEL 上安装 Bison：

在 CentOS 或 RHEL 系统上，你可以使用包管理器 yum 安装 Bison：

sudo yum install bison

在 macOS 上安装 Bison：

在 macOS 上，你可以使用包管理器 Homebrew 安装 Bison。如果你尚未安装 Homebrew，可以按照官方网站的指南进行安装。

安装 Bison：

brew install bison

在 Windows 上安装 Bison：

在 Windows 上，你可以使用 MinGW-w64 来安装 Bison。首先，确保你安装了 MinGW-w64，然后按照以下步骤安装 Bison：

下载 Bison for Windows：你可以在 Bison 的官方网站（https://www.gnu.org/software/bison/）上找到 Windows 版本的 Bison。下载并解压缩文件。
将 Bison 添加到系统路径：将 Bison 的安装目录（包含 bison.exe 的目录）添加到系统的 PATH 环境变量中，以便在命令行中使用 Bison。

验证 Bison 安装：

安装完成后，你可以在命令行中运行以下命令来验证 Bison 是否成功安装：

bison --version

如果 Bison 成功安装，将会显示 Bison 的版本信息。

安装和配置 Bison 后，你就可以使用它来定义和生成语法分析器。通常，你需要编写一个 Bison 文件（通常以 .y 扩展名结尾），其中包含语法规则，并使用 Bison 工具生成 C 或 C++ 代码来创建语法分析器。随后，你可以将这个生成的代码与词法分析器（通常使用 Flex 创建）一起使用，以完成编译器或解释器的开发。

4. 学习 Bison 的基本语法

学习 Bison 的基本语法是理解如何定义和生成语法分析器的关键。Bison 使用自己的语法来描述文法规则和语法动作。以下是 Bison 的基本语法元素：

1. 定义语法规则：

Bison 使用文法规则来描述编程语言的语法。语法规则通常采用如下形式：

非终结符: 产生式右侧

其中，非终结符表示一个抽象的语法结构，产生式右侧描述了如何构造或匹配这个结构。例如：

stmt: if_expr
    | while_expr
    | assignment
    ;

上述规则表示 stmt 是一个语法结构，它可以是 if_expr、while_expr 或 assignment 中的任何一个。

2. 定义产生式右侧：

产生式右侧由终结符、非终结符和特殊符号组成，用于构建语法结构。你可以使用 | 分隔多个可能的右侧，使用递归定义复杂的结构。

3. 定义终结符和非终结符：

Bison 中的终结符表示源代码中的实际符号，如标识符、关键字、运算符等。非终结符表示抽象语法结构，可以由产生式定义。

4. 定义语法动作：

语法动作是在匹配规则时执行的操作，通常用于构建语法树或执行语义分析。语法动作使用 C 或 C++ 代码块来定义，放置在花括号 {} 中。

例如，下面的示例演示了如何定义一个简单的语法规则和语法动作：

stmt: if_expr { /* 在这里执行语法动作 */ }
    ;

5. Bison 文件的结构：

通常，Bison 文件的结构包括文法规则、终结符和非终结符的定义，以及语法动作的定义。文件以 % 开头的部分用于指定 Bison 的选项和声明。

以下是一个简单的示例，演示了一个包含两个非终结符和一条规则的 Bison 文件：

%{
#include <stdio.h>
%}

%token IF THEN ELSE
%token ID

%%

stmt: IF expr THEN stmt ELSE stmt
    {
        printf("if-else语句\\\\\\\\n");
    }
    | ID
    {
        printf("标识符\\\\\\\\n");
    }
    ;

%%

int main() {
    yyparse();
    return 0;
}

在上面的示例中，我们定义了两个非终结符 stmt 和 expr，以及一条规则来描述 if-else 语句。在规则的语法动作中，我们输出了相应的消息。

要深入学习 Bison 的语法，建议查阅 Bison 的官方文档和示例，以及参考相关教程。逐步练习并理解不同类型的语法规则和语法动作可以帮助你更好地利用 Bison 来定义编程语言的语法规则。

编写一个简单的语法分析器是理解语法规则和语法分析的关键一步。在下面的示例中，我们将创建一个基本的语法分析器，用于处理简单的数学表达式，包括加法和乘法操作。我们将使用 Bison 来定义语法规则，并在规则中执行一些简单的语法动作。

首先，创建一个名为 calculator.y 的 Bison 文件，并添加以下内容：

%{
#include <stdio.h>
%}

%token NUM   /* 表示数字 */
%token ADD   /* 表示加法操作符 */
%token MUL   /* 表示乘法操作符 */

%%

expr: expr ADD term    /* 表达式可以是表达式 + 项 */
    {
        printf("加法操作: %d\\\\\\\\n", $1 + $3);
        $$ = $1 + $3; /* 将计算结果传递给父节点 */
    }
    | term            /* 或者只是一个项 */
    ;

term: term MUL factor /* 项可以是项 * 因子 */
    {
        printf("乘法操作: %d\\\\\\\\n", $1 * $3);
        $$ = $1 * $3; /* 将计算结果传递给父节点 */
    }
    | factor          /* 或者只是一个因子 */
    ;

factor: NUM         /* 因子可以是一个数字 */
    {
        $$ = $1; /* 数字的值作为结果传递给父节点 */
    }
    | '(' expr ')'   /* 或者一个括号包裹的表达式 */
    ;

%%

int main() {
    yyparse(); /* 启动语法分析器 */
    return 0;
}

上述示例定义了一个简单的文法，用于处理加法和乘法表达式。我们定义了终结符 NUM（表示数字）、ADD（表示加法操作符）和 MUL（表示乘法操作符）。

接下来，你需要使用 Bison 工具来生成 C 代码：

bison -d calculator.y

这将生成 calculator.tab.c 和 calculator.tab.h 文件。

接着，编译生成的 C 代码并运行：

gcc -o calculator calculator.tab.c -ly -lfl
./calculator

如果是Mac电脑的M1芯片，链接的flex的动态库就该是 -ll：

gcc -o calculator calculator.tab.c -ly -ll
./calculator

现在，你可以输入一些数学表达式，如 2 + 3 * (4 + 5)，然后你的语法分析器将识别和计算表达式的值，并输出结果。

这只是一个简单的语法分析器示例，用于处理基本的数学表达式。你可以根据需要扩展这个示例，添加更多的语法规则和操作符，以满足更复杂的需求。深入学习 Bison 的语法和语法动作将有助于你定义和生成更复杂的语法分析器。

不做展开： 深入学习Bison的功能： Bison提供了许多高级功能，如语法错误处理、语法树构建等。深入学习这些功能，以满足更复杂的语法分析需求。

编写一个完整的编程语言的语法分析器是一个相对复杂的任务，需要考虑语言的整体结构、语法规则和语义分析。在这个简单示例中，我们将创建一个极其简化的编程语言，只包含基本的赋值语句和表达式。我们将使用 Bison 来定义语法规则和语法动作。

首先，让我们创建一个名为 simple_lang.y 的 Bison 文件，并添加以下内容：

%{
#include <stdio.h>

/* 定义符号表 */
struct SymbolTable {
    char name[32];
    int value;
};

/* 用于存储变量的符号表 */
struct SymbolTable variables[100];
int varCount = 0;

/* 函数声明 */
int lookupVariable(const char* name);
%}

%union {
    int numValue;        /* 用于存储整数值 */
    const char* varName; /* 用于存储变量名 */
}

%token <numValue> NUM
%token <varName> IDENTIFIER
%token ASSIGN
%token SEMICOLON

%type <numValue> expr
%type <varName> var

%%

program:
    /* 空程序 */
    | program stmt SEMICOLON
    ;

stmt:
    /* 赋值语句 */
    IDENTIFIER ASSIGN expr
    {
        int index = lookupVariable($1);
        if (index != -1) {
            variables[index].value = $3;
        } else {
            strcpy(variables[varCount].name, $1);
            variables[varCount].value = $3;
            varCount++;
        }
        printf("赋值语句: %s = %d\\\\\\\\n", $1, $3);
    }
    ;

expr:
    /* 表达式 */
    expr '+' term
    {
        $$ = $1 + $3;
    }
    | term
    ;

term:
    /* 项 */
    term '*' factor
    {
        $$ = $1 * $3;
    }
    | factor
    ;

factor:
    /* 因子 */
    NUM
    {
        $$ = $1;
    }
    | IDENTIFIER
    {
        int index = lookupVariable($1);
        if (index != -1) {
            $$ = variables[index].value;
        } else {
            printf("错误: 变量 %s 未定义\\\\\\\\n", $1);
            yyerror("语法错误");
            exit(1);
        }
    }
    | '(' expr ')'
    ;

var:
    /* 变量 */
    IDENTIFIER
    {
        int index = lookupVariable($1);
        if (index != -1) {
            yyerror("变量已经定义");
            exit(1);
        } else {
            strcpy(variables[varCount].name, $1);
            varCount++;
        }
    }
    ;

%%

int lookupVariable(const char* name) {
    for (int i = 0; i < varCount; i++) {
        if (strcmp(name, variables[i].name) == 0) {
            return i;
        }
    }
    return -1; /* 未找到变量 */
}

int main() {
    yyparse();
    return 0;
}

上述代码创建了一个非常简化的编程语言，只包含基本的赋值语句和算术表达式。语法分析器使用了一个简单的符号表来管理变量。你可以按照以下步骤来编译和运行这个示例：

使用 Bison 生成 C 代码：
```
bison -d simple_lang.y
```
这将生成 simple_lang.tab.c 和 simple_lang.tab.h 文件。

编译生成的 C 代码：

gcc -o simple_lang simple_lang.tab.c -ly -lfl

运行语法分析器：
```
./simple_lang
```

现在，你可以输入简单的赋值语句和表达式，例如：

x = 10;
y = x + 5;
z = y * 2;

语法分析器将识别并输出相应的赋值语句，并在符号表中记录变量的值。

请注意，这只是一个非常简化的示例，真实的编程语言要复杂得多。学习编写更复杂的语法分析器需要深入了解语法规则、语法动作和语义分析等概念。这个示例可以作为入门的起点，帮助你更好地理解 Bison 和语法分析的基本原理。

5. 扩展

寻找 Bison 的官方文档和在线教程是学习和掌握 Bison 的关键。以下是一些资源，你可以使用它们来获取关于 Bison 的详细信息和示例：

1. Bison 官方网站：

Bison 的官方网站提供了官方文档、下载链接和其他有用的资源。你可以在这里找到最新的版本和文档：

Bison 官方网站

2. Bison 用户手册：

Bison 用户手册是官方文档的一部分，提供了关于 Bison 的详细信息，包括语法规则、语法动作、选项和示例。你可以在以下链接找到手册：

Bison 用户手册

3. Bison 教程和示例：

除了官方文档，还有一些在线教程和示例可以帮助你学习如何使用 Bison。以下是一些资源：

Bison 教程: 由罗切斯特大学提供的简明教程，涵盖了 Bison 的基本用法。
Bison and Flex简介: 一本介绍 Bison 和 Flex 的书，包含示例和练习。
Bison 教程: 一个简短的教程，介绍了如何使用 Bison 和 Flex 来创建语法分析器。——评论区，一键三连告诉我要需要，我加一个全文注释，导读版本的，存在github仓库

4. 在线社区和论坛：

有时，与其他使用 Bison 的开发者交流经验和提问问题也是学习的好方式。你可以加入 Bison 相关的在线社区和论坛，如 Stack Overflow 等，以获取帮助和建议。

通过官方文档和这些在线资源，你可以深入学习 Bison 的用法和最佳实践，以更好地掌握这个强大的工具。

文章来源:https://blog.csdn.net/lixiemang8887/article/details/135233294
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！

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