五、语法制导翻译与抽象语法树，《编译原理》（本科教学版），第2版

🕗 发布于 2024-11-10 19:48 编译原理

零、LR(1)分析工具

1.1 历史

Antlr-v4 是基于 LL(*)算法，这里介绍下基于LR(1)的 yacc

YACC 是 Yet Another Compiler-Compiler 缩写
- Compiler-Compiler：写一个模块，可以把这个C编译器生成出来
在1975年首先由Steve Johnson在 Unix 上实现
后来，很多工具在此基础上做了改进：
- 例如GNU Bison，下面会用
- 并且移植到了很多其他语言上
YACC现在是一个标准的工具(见IEEE Posix 标准 P1003.2)

1.2 Yacc

Yacc 语言很简单，分为三大块：

用户代码和Yacc声明：可以在接下来的部分使用
%%
语法规则：上下文无关文法的规则及相应语义动作(后续变成一个表驱动的语法分析算法)
%%
用户代码：用户提供的代码

下面写一个简单的检测表达式输入的文法

创建一个文件 test.y
书写语法规则
并在用户代码部分书写主函数，调用 yyparse()


%%

exp: n
   | exp '+' exp
;

n: '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0';

%%

int main(int argc, char **argv){
    yyparse();
    return 0;
}

我们通过 bison + 文件名来进行编译
发现报错：出现二义性

root@LAPTOP-292TJJC6:~/UstcCompile# bison test.y
test.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]

我们强制左结合优先：


%left '+'

%%

exp: n
   | exp '+' exp
;

n: '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0';

%%

int main(int argc, char **argv){
    yyparse();
    return 0;
}

发现可以编译，并且生成了 test.tab.c
test.tab.c 是一个长达上千行，自动生成的一个LR(1)语法分析器

root@LAPTOP-292TJJC6:~/UstcCompile# bison test.y
root@LAPTOP-292TJJC6:~/UstcCompile# ls
test.tab.c  test.y
root@LAPTOP-292TJJC6:~/UstcCompile#

我们利用gcc 去编译 test.tab.c：再次报错

root@LAPTOP-292TJJC6:~/UstcCompile# gcc test.tab.c
test.tab.c: In function ‘yyparse’:
test.tab.c:1197:16: warning: implicit declaration of function ‘yylex’ [-Wimplicit-function-declaration]
 1197 |       yychar = yylex ();
      |                ^~~~~
test.tab.c:1324:7: warning: implicit declaration of function ‘yyerror’; did you mean ‘yyerrok’? [-Wimplicit-function-declaration]
 1324 |       yyerror (YY_("syntax error"));
      |       ^~~~~~~
      |       yyerrok
/usr/bin/ld: /tmp/ccdewM9y.o: in function `yyparse':
test.tab.c:(.text+0x328): undefined reference to `yylex'
/usr/bin/ld: test.tab.c:(.text+0x628): undefined reference to `yyerror'
/usr/bin/ld: test.tab.c:(.text+0x7be): undefined reference to `yyerror'
collect2: error: ld returned 1 exit status
root@LAPTOP-292TJJC6:~/UstcCompile#

因为我们没有实现 yylex 和 yyerror

yylex：类似于getToken
yyerror：语法报错

%{
    int yylex();
    void yyerror();
%}


%left '+'

%%

exp: n
   | exp '+' exp
;

n: '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0';

%%

int yylex(){
    return getchar();
}

void yyerror(char *s){
    fprintf(stderr, "%s\n", s);
}

int main(int argc, char **argv){
    yyparse();
    return 0;
}

再次重新编译，又报错：
因为没引头文件

root@LAPTOP-292TJJC6:~/UstcCompile# bison test.y
root@LAPTOP-292TJJC6:~/UstcCompile# ls
test.tab.c  test.y
root@LAPTOP-292TJJC6:~/UstcCompile# gcc test.tab.c
test.y: In function ‘yylex’:
test.y:22:12: warning: implicit declaration of function ‘getchar’ [-Wimplicit-function-declaration]
   22 |     return getchar();
      |            ^~~~~~~
test.y:19:1: note: ‘getchar’ is defined in header ‘<stdio.h>’; did you forget to ‘#include <stdio.h>’?
   18 |
  +++ |+#include <stdio.h>
   19 | %%
test.y: In function ‘yyerror’:
test.y:26:5: warning: implicit declaration of function ‘fprintf’ [-Wimplicit-function-declaration]
   26 |     fprintf(stderr, "%s\n", s);
      |     ^~~~~~~
test.y:26:5: warning: incompatible implicit declaration of built-in function ‘fprintf’
test.y:26:5: note: include ‘<stdio.h>’ or provide a declaration of ‘fprintf’
test.y:26:13: error: ‘stderr’ undeclared (first use in this function)
   26 |     fprintf(stderr, "%s\n", s);
      |             ^~~~~~
test.y:26:13: note: ‘stderr’ is defined in header ‘<stdio.h>’; did you forget to ‘#include <stdio.h>’?
test.y:26:13: note: each undeclared identifier is reported only once for each function it appears in
root@LAPTOP-292TJJC6:~/UstcCompile#

我们把头文件加上

%{
#include <stdio.h>
#include <stdlib.h>
    int yylex();
    void yyerror();
%}

root@LAPTOP-292TJJC6:~/UstcCompile# bison test.y
root@LAPTOP-292TJJC6:~/UstcCompile# gcc test.tab.c
root@LAPTOP-292TJJC6:~/UstcCompile# ls
a.out  test.tab.c  test.y

产生了可执行文件
运行（注意，非终结符为 Ctrl + D）

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

我们通过增加 lines 产生式来实现多行输入检测：

%%

lines: line
     | line lines
;

line: exp
    | exp '\n'
;

exp: n
   | exp '+' exp
;

n: '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '0';

%%

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

一、语法制导的翻译

编译器在做语法分析的过程中，除了回答程序语法是否合法外，还必须完成后续工作
- 可能的工作包括(但不限于)
  - 类型检查
  - 目标代码生成
  - 中间代码生成
这些后续的工作一般可通过语法制导的翻译完成

1.1 LR分析中的语法制导翻译

我们有如下文法，对于每个产生规则我们添加了一个语义动作 ai，这些语义动作要在右部被识别完，进行规约的时候来执行。

X -> β1a1
| β2    a2
| β3    a3
...
| βn    an

用伪代码表示就是下面这样，我们在弹栈规约前调用了 ai

if (action[s, t] == "ri")
ai
pop(βi)
state s' = stack[top]
push(x)
push(goto[s', x])

示例：计算表达式的的值：

按照产生式1进行规约时，我们将 n 赋值给 E

同样的，按照产生式0进行规约时，我们一定已经得到了E1和E2的值了，那么我们将 E1+E2 赋值给 E

0: E -> E+E{E = E1 + E2}
1:  | n{E = n}

1.1.1 实例

回看前面的 Yacc 程序，我们在其中加入语义动作：

Yacc 中语义动作在产生式后用花括号包裹
产生式右部的token 从左至右分别为 $1, $2 … %n
左部用 $$ 表示

line: exp   {printf("value=%d\n", $1);}
    | exp '\n'  {printf("value=%d\n", $1);}
;

exp: n              {$$=$1;}
   | exp '+' exp    {$$=$1+$3;}
;

n: '1'  {$$=1;}
    | '2' {$$=2;}
    | '3' {$$=3;}
    | '4' {$$=4;}
    | '5' {$$=5;}
    | '6' {$$=6;}
    | '7' {$$=7;}
    | '8' {$$=8;}
    | '9' {$$=9;}
    | '0' {$$=0;}
;

root@LAPTOP-292TJJC6:~/UstcCompile# ./a.out
1+3
value=4
2+5
value=7
6+7
value=13
root@LAPTOP-292TJJC6:~/UstcCompile#

1.2 语法制导翻译的实现原理

X -> β1a1
| β2    a2
| β3    a3
...
| βn    an

给每条产生式规则附加一个语义动作
- 一个代码片段
语义动作在产生式**“归约”**时执行
- 即由右部的值计算左部的值
- 以自底向上的技术为例进行讨论
  - 自顶向下的技术与此类似

1.2.1 LR分析中的语法制导翻译

if (action[s, t] == "ri")
ai
pop(βi)
state s' = stack[top]
push(x)
push(goto[s', x])

在分析栈上维护三元组：<symbo1, value，state>
其中symbo1是终结符或非终结符，value是symbo1所拥有的值，state是当前的分析状态

1.2.2 例子

这里对前面Yacc 中的例子来进行解释

E -> E + E{$$=$1+$3;}
| n    {$$=n;}

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

我们对下面这个输入进行语法制导翻译

7+8+9

栈中存储三元组<symbol, value, state>

<S, _, 0> 入栈
读入7，<7, 7, 1> 入栈
执行语义动作 <$$ = n;>，弹栈规约，<E, 7, 2> 入栈
读入+，<+, +, 3> 入栈
读入8，<8, 8, 1> 入栈
弹栈规约，<E, 8, 4>
此时的栈的状态：
这个时候执行语义动作<$$ = $1 + $3>，弹栈规约，<E, 15, 2>入栈
后面读入 + 和 9 重复前面的情况，不再赘述

1.3 抽象语法树

这一part非常简单，其实就是数据结构中讲的表达式树：表达式树与前中后缀表达式的转化_二叉树前缀后缀中缀-CSDN博客

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

现代语法分析器的输出往往是一个抽象语法树

1.3.1 分析树

分析树编码了句子的推导过程
但是包含很多不必要的信息
- 注意：这些节点要占用额外的存储空间
本质上，这里的哪些信息是重要的?
对于表达式而言，编译只需要知道运算符和运算数
- 优先级、结合性等已经在语法分析部分处理掉了
对于语句、函数等语言，其他构造语言也一样
- 例如，编译器不关心赋值符号是**=还是:=**或其他

1.3.2 抽象语法树

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

可见右边的抽象语法树是对于左侧分析树的浓缩。

当然，如果还记得数据结构课程中的表达式树的话，对于抽象语法树应该不会陌生。

1.3.3 具体语法和抽象语法

具体语法是语法分析器使用的语法
- 必须适合于语法分析，如各种分隔符、消除左递归、提取左公因子，等等
抽象语法是用来表达语法结构的内部表示
- 现代编译器一般都采用抽象语法作为前端(词法语法分析)和后端(代码生成)的接口

比如我们可以有这样一个具体文法：

E -> E + T
   | T
T -> T * F
   | F
F -> n
   | (E)

如果我们将其简化：

E -> n
   | E + E
   | E * E

但是这个文法是有二义性的，但是这样的抽象文法却有助于我们对于数据结构的建立。

1.3.4 抽象语法树数据结构

在编译器中，为了定义抽象语法树，需要使用实现语言（编译器的实现语言）来定义一组数据结构。
- 和实现语言密切相关
早期的编译器有的不采用抽象语法树数据结构
- 直接在语法制导翻译中生成代码（早期内存受限）
- 但现代的编译器一般采用抽象语法树作为语法分析器的输出
  - 更好的系统的支持
  - 简化编译器的设计

1.3.5 抽象语法树的定义(C语言)

文法：

E -> n
   | E + E
   | E * E

1.3.5.1 数据结构

下面的定义个人理解是一种类似于侵入式链表结构
将数据和指针进行了解耦合，USTC的PPT上的代码有些语法错误，做了更正
事实上如果按照他这种侵入式的设计方式，实际运用应该加一些成员访问的逻辑，Exp指针如何访问不同类型的Exp_ 的成员
所以下面就当成是伪代码，看个乐就行

/*数据结构*/
enum kind {E_INT, E_ADD, E_TIMES};
struct Exp {
    enum kind kind;
};

// int
struct Exp_Int {
    enum kind kind;
    int n;
};

// +
struct Exp_Add {
    enum kind kind;
    struct Exp *left;
    struct Exp *right;
};

// *
struct Exp_Times {
    enum kind kind;
    struct Exp *left;
    struct Exp *right;
};

1.3.5.2 “构造函数”

struct Exp_Int *Exp_Int_new(int n) {
    struct Exp_Int *p = (struct Exp_Int*)malloc(sizeof (*p));
    p->kind = E_INT;
    p->n = n;
    return p;
}

struct Exp_Add *Exp_Add_new(struct Exp *left, struct Exp *right) {
    struct Exp_Add *p = (struct Exp_Add*)malloc(sizeof (*p));
    p->kind = E_ADD;
    p->left = left;
    p->right = right;
    return p;
}

1.3.5.3 示例

用数据结构来编码程序 “2+3+4”

e1 = Exp_Int_new(2);
e2 = Exp_Int_new(3);
e3 = Exp_Int_new(4);
e4 = Exp_Times_new(e2, e3);
e5 = Exp_Add_new(e1, e4);

得到如下抽象语法树

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

1.3.6 AST上的操作成为树的遍历

/*优美打印*/
void pretty_print(e) {
    switch(e->kind) {
        case E_INT: printf("%d", e->n); return;
        case E_ADD: 
            printf("(");
            pretty_print(e->left);
            printf(")");
            printf("+");
            printf("(");
            pretty_print(e->right);
            printf(")");
        other cases: /* 类似 */
    }
}

示例：树的规模

通过 dfs 来计算节点个数

/*节点的个数*/
int numNodes(E e) {
switch (e->kind) {
        case E_INT:
        case E_ADD:
        case E_TIMES:
            return 1 + numNodes (e->left) + numNodes (e->right);
        default:
            error("complier bug");
    }
}

示例：从表达式到栈式计算机Stack的编译器

/*编译器：请参考课程第一部分的作业内容：Sum -> Stack*/
List all;// 存放生成的所有指令
void compile (E e) {
    switch (e->kind) {
        case E_INT: emit(push e->n); return;
        case E_ADDS:
        case E_TIMES:
        // 留作练习
        default:
            error("compiler bug");
    }
}

1.3.7 抽象语法树的自动生成

1.3.7.1 LR分析中生成抽象语法树

在语法动作中，加入生成语法树的代码片段
- 片段一般是语法树的’构造函数’
在产生式归约的时候，会自底向上构造整棵树
- 从叶子到根

生成方法非常的巧妙，通过规约前的语义动作完成构造，而且不会影响结合性！

1.3.8 源代码信息的保留和传播

抽象语法树是编译器前端和后端的接口
- 程序一旦被转换成抽象语法树，则源代码即被丢弃
- 后续的阶段只处理抽象语法树
所以抽象语法树必须编码足够多的源代码信息
- 例如，它必须编码每个语法结构在源代码中的位置(文件、行号、列号等)
  - 这样，后续的检查阶段才能精确的报错
  - 或者获取程序的执行创面
抽象语法树必须仔细设计

示例：位置信息

我们还可以在节点中加入位置信息

struct position_t {
    char *file;
    int line;
int column;
};

struct Exp_Add {
    enum kind kind;
    Exp *left;
    Exp *right;
    struct position_t from;
    struct position_t to;
};

设计好的抽象语法树是一门艺术，绝对不是教条化，绝对化的规则。要根据设计编译器的需求和目的，来设计抽象语法树的合理表示，来保证我们需要的信息，来满足设计需求。

而且不会影响结合性！

1.3.8 源代码信息的保留和传播

抽象语法树是编译器前端和后端的接口
- 程序一旦被转换成抽象语法树，则源代码即被丢弃
- 后续的阶段只处理抽象语法树
所以抽象语法树必须编码足够多的源代码信息
- 例如，它必须编码每个语法结构在源代码中的位置(文件、行号、列号等)
  - 这样，后续的检查阶段才能精确的报错
  - 或者获取程序的执行创面
抽象语法树必须仔细设计

示例：位置信息

我们还可以在节点中加入位置信息

struct position_t {
    char *file;
    int line;
int column;
};

struct Exp_Add {
    enum kind kind;
    Exp *left;
    Exp *right;
    struct position_t from;
    struct position_t to;
};

原文地址：https://blog.csdn.net/EQUINOX1/article/details/143662626

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：探索 Linux 系统：开源世界的璀璨明珠
下一篇：用Java实现samza转换成flink

(时序论文阅读)TimeMixer: Decomposable Multiscale Mixing for Time Series Forecasting
来源论文iclr2024论文地址：https://arxiv.org/abs/2405.14616源码地址： https://github.com/kwuking/TimeMixer。
阅读更多2024-11-13
HTML文件中引入jQuery的库文件
HTML文件中引入jQuery的库文件
阅读更多2024-11-13
10款PDF合并工具的使用体验与推荐！！！
在如今的信息洪流中，我们几乎每个人都被淹没在大量的数字文档之中。无论是学生、教师还是职场人士，我们都需要高效地管理和处理这些文档。而PDF文件，凭借其跨平台的稳定性和通用性，成了最常用的文档格式之一。
阅读更多2024-11-13
红日靶机(七)笔记
在 VulnStack7 是由 5 台目标机器组成的三层网络环境，分别为 DMZ 区、第二层网络、第三层网络。涉及到的知识点也是有很多，redis未授权的利用、laravel的历史漏洞、docker逃
阅读更多2024-11-13
【分布式】CAP理论
是分布式系统中的三个基本要求，但根据CAP定理，在分布式系统中，不能同时满足这三者。当网络发生分区时（网络分区通常是不可避免的），系统只能在。每个分布式系统根据具体的业务需求、使用场景和网络环境，都会
阅读更多2024-11-13
【linux】TCP网络编程及Web服务器搭建
默认的情况下，如果一个网络应用程序的一个套接字绑定了一个端口( 占用了 8000 )，这时候，别的套接字就无法使用这个端口( 8000 )端口复用：允许在一个应用程序可以把 n 个套接字绑在一个端
阅读更多2024-11-13
全媒体数字化转型浪潮下半场，有效流量&创新业务是转型成功与否的最好证明
不少传媒企业已经开始积极探索转型之路。通过打造个性IP工作室、重视C端用户服务、深化G端合作等方式，传媒行业正在逐步构建起一个以用户为中心、以数据为驱动、以创新为核心的新型媒体生态。
阅读更多2024-11-13
C++- 基于多设计模式下的同步&异步日志系统
13万字项目带源代码
阅读更多2024-11-13
多路转接之select
表示timeout->tv_sec时间内没有文件描述符的资源准备就绪，就一直阻塞等待，直到等待时间超过timeout->tv_sec才返回。在timeout->tv_sec时间内有文
阅读更多2024-11-13
Android Studio | 修改镜像地址为阿里云镜像地址，启动App
在项目文件的目录下的 settings.gradle.kts 中修改配置，配置中包含插件和依赖项。
阅读更多2024-11-13

五、语法制导翻译与抽象语法树，《编译原理》（本科教学版），第2版

文章目录

零、LR(1)分析工具

1.1 历史

1.2 Yacc

一、语法制导的翻译

1.1 LR分析中的语法制导翻译

1.1.1 实例

1.2 语法制导翻译的实现原理

1.2.1 LR分析中的语法制导翻译

1.2.2 例子

1.3 抽象语法树

1.3.1 分析树

1.3.2 抽象语法树

1.3.3 具体语法和抽象语法

1.3.4 抽象语法树数据结构

1.3.5 抽象语法树的定义(C语言)

1.3.5.1 数据结构

1.3.5.2 “构造函数”

1.3.5.3 示例

1.3.6 AST上的操作成为树的遍历

1.3.7 抽象语法树的自动生成

1.3.7.1 LR分析中生成抽象语法树

1.3.8 源代码信息的保留和传播

1.3.8 源代码信息的保留和传播

相关文章