跳转至

School/Compiler

编译原理 0. 概述

忽略掉预处理以及链接的部分，C/C++ 语言的完整编译过程可以用下图表示：

flowchart LR
    subgraph 源代码
        A[main.c]
    end

    subgraph 汇编代码
        C[main.s]
    end

    A --编译 -S--> C

    subgraph 机器码
        D[main.o]
    end

    C --汇编 -c--> D

    机器码 ---> 可执行程序
    可执行程序 --> z([运行])

编译原理中的“编译”二字与此处的“编译”二字并不是一个意思，此处的编译是具体的过程，从源代码到最终的可执行程序，而编译原理中的“编译”更加广泛，一切与解析某一种语言并转化为其他“语言”有关的过程都离不开此原理。

比如 python 的解释器（解释 python 代码并转化为具体指令运行），Markdown的解析渲染（解析 Markdown 并转化为 HTML 进行渲染），以及 SQL 的解析执行（解析 SQL 语句为具体的操作并执行）等等。

而这些过程都可以大致抽象为两大部分：

  • 前端部分（Frontend）

负责将源代码经过一步步分析转化为一个抽象的树形结构 —— 抽象语法树（AST）

  • 后端部分（Backend）

可能是个代码生成器，依照抽象的树形结构生成具体实际的转化目标的指令或语言等

或许还会包含优化器等部分

编译原理 1. 词法分析 - flex

一、概述

flex 手册：Lexical Analysis With Flex, for Flex 2.6.2: Top (westes.github.io)

flex 是一个用于生成基于 C/C++ 的词法分析器的程序。

它的输入是一个 .flex 文件，其中包含着一对对由 正则表达式 和 C 语言代码 组成的 规则。

它的输出是一个 C 语言源文件，其中会包含一个 yylex() 函数，该函数会对输入的字符序列进行扫描，根据 规则 中的一个个 正则表达式 进行匹配并执行其对应的 C 语言代码。

-SQL解析

注释

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
%option noyywrap nodefault yylineno case-insensitive

%{
void yyerror(char *s, ...);
%}

%s COMMENT

%%
    /* comments */
"--"[ \t].*      ;
"/*"             { old_state = YY_START; BEGIN COMMENT; }
<COMMENT>"*/"    { BEGIN old_state; }
<COMMENT>.|\n    ;
<COMMENT><<EOF>> { yyerror("lexer: unclosed comment"); }

    /* everything else */
[ \t\n]          ;
.                { yyerror("lexer: mystery character: '%c'", *yytext); }
%%

实训II —— SQL解析 Draft

使用 flex 生成 C++ 词法分析器

主要两种方法：

  • 简单地直接用 C++ 编译器代替 C 编译器
  • 也可以使用 -+ 选项（或者添加 %option c++），这样就会生成 lex.yy.cc 而非 lex.yy.c

使用第二种方法：

在 .l 文件中的 defination 部分添加

Text Only
1
%option c++

即可。

生成的 lex.yy.cc 文件中会引入一个 FlexLexer.h 头文件，其中定义了一个 FlexLexer 类，这是一个抽象的基类，定义了一般的扫描器类接口，在该类中提供了以下成员函数：

编译原理 2. 语法分析 - bison

flex 匹配正则表达式，bison 识别整个文法（grammar），将从 flex 中得到的记号组织成树形结构。

一、概述

比如对于一个计算器来说，可能会有如下的文法：

Text Only
1
2
3
statement: NAME '=' expression
expression: NUMBER '+' NUMBER
          | NUMBER '-' NUMBER

| 表示有两种可能性，对于 : 左侧相同的规则可以用这种方式简写。

比如对于这个表达式：

Text Only
1
fred = 12 + 13

它被 flex 解析完毕后大概可以得到如下 记号：

Text Only
1
<NAME, fred> '=' <NUMBER, 12> '+' <NUMBER, 13>

它进而会被 bison 转化为如下的解析树：

-Week 1 02-01-cool-overview-final

这里引入了一个 COOL 语言（Classroom Object Oriented Language）是教授自己写的，它被设计为可以在短时间内实现的语言。实际上它的编译器的数量要超过了用它写的程序的数量。

课程的内容将做一个 COOL 到 MIPS 汇编语言的编译器，将包含五个作业： - 写一个 COOL 程序 - 词法分析器 - 解析器 - 语义分析器 - 代码生成

MIPS 是一个用于 20世纪80年代设计的机器的指令集，而现在有一个用于 MIPS 的可以运行在各种设备的模拟器 SPIN。

-PA1

一、环境准备

在虚拟机中的合适位置创建一个目录，用于存放此次作业相关内容。

在目录中执行下面的命令：

  • 如果使用 C++：make -f /usr/class/cs143/assignments/PA2/Makefile
  • 如果使用 Java：make -f /usr/class/cs143/assignments/PA2J/Makefile

然后会多出来一些文件和符号链接。

需要我们完成的只有 cool.flex（使用 C++）或 cool.lex（使用 Java）。

如果要构建词法分析器，则需要运行 make lexer。

-04-02-finite-automata

有限自动机

一个有限自动机所对应的语言就是接受字符串的集合

正则表达式是声明，而有限自动机则是实现。

一个有限自动机由以下部分组成：

  • 一个输入字母表 \(\Sigma\)
  • 一组状态的有限的集合 \(S\)
  • 一个起始状态 \(n\)
  • 一组可接受的状态 \(F \subseteq S\)
  • 一组状态的转移 \(state \to^{input} state\)

Transition $$ S_1 \to^{a} S_2 $$ 读作：在状态 \(S_1\) 时输入 \(a\) 到状态 \(S_2\)

如果在输入结束的时候状态位于 \(F\) 内则为接受，否则为拒绝（在状态 \(S \notin F\) 终止 或 卡住）

状态图

每一个节点是一个状态，由一个五源的箭头指向的一个节点为起始节点，双边框节点为一个接收状态，箭头为一个转移

stateDiagram-v2
    [*] --> Still
    Still --> [*]

    Still --> Moving
    Moving --> Still
    Moving --> Crash
    Crash --> [*]

image-20230323110644981

不消耗输入的状态移动，可做选择移动与否

image-20230323110756233

image-20230323111011406

image-20230323111213522