Abell Studio

这世界没有一件事情是虚空而生的。站在光里,背后就会有阴影,这深夜一片寂静,是因为你还没有听见声音。

编译器

分类

LR分析中shift/reduce reduce/reduce冲突解决方案SLR(1)与LR(1)

此篇文章要求读者对编译原理前端部分有一定了解 此篇文章中,我们以大写英文作为非终结符,小写英文作为终结符

1. LR(0)分析法简述

LR分析法从左至右移进输入的终结符(词法分析器的输出实际是token,但在语法分析阶段会代表是一个终结符),并将终结符压入到堆栈,称为shift。如果当前栈上的符号恰好符合某个非终结符的生成式,则此时进行归约操作:将这些符号弹出栈,然后将规约后的非终结符压入堆栈,这一步就称为reduce。然后继续上面的步骤,直到没有输入。
如果最终栈上只有一个非终结符,且该非终结符就是目标符号,那证明识别成功,否则识别失败。
名称LR得名于:从左(Left)到右扫描(L),反向(Reverse)最右推导(R)。

2. LR(0)分析法的不足

上面描述的算法存在一个问题,我们以下面的语法为例说明:

// 例1
B : A c
A : b d
  | b

对于上面的语法,当语法分析器遇到终结符b时,面临着两个选择,一个是继续移进下一个终结符,一个是使用生成式A : b进行归约。这种情况称为shift/reduce冲突
继续看下面一个例子:

// 例2
A : b
C : b
D : A a
E : C d

对于上面的语法,当语法分析器遇到终结符b时,面临着两个选择,一个是根据A : b,归约为A,另一个选择是使用生成式C : b进行归约。这种情况称为reduce/reduce冲突

因为这两种冲突的存在导致了LR(0)分析法在实际语法分析中基本不可用,必须找到解决这两种冲突的方案才行,那么如何这两种冲突呢?

3. SLR(1)

对于这两种冲突,我们首先先看一种简单的解决方案:SLR(1) (Simple LR)分析法。
SLR(1)分析法首先求出所有非终结符的Follow Set,即 跟在非终结符之后的所有终结符的集合,然后前瞻一个符号(即从词法分析器中预先读入下一个终结符),如果该前瞻符号在一个非终结符的Follow Set中,就根据此非终结符的生成式进行归约。

我们以上面的例2为例,SLR(1)分析器先求出A的Follow Set为{a},C的Follow Set为{b},假设当前输入为b a,输入b之后,语法分析器面临选择:归约到A or 归约到C,此时分析器前瞻一个符号即c,由于c属于A的Follow Set,所以分析器选择归约到A。

上面的例1也可以通过此算法解决shift/reduce冲突。

遗憾的是SLR(1)依然存在问题,这里举个例子就清楚了:

// 例3
T : S
S : aAd
S : bAc
S : aec
S : bed
A : e

首先求出各个非终结符的Follow Set:

Follow(T) = {}
Follow(S) = {}
Follow(A) = {d, c}

我们假设当前的输入为a e c, 当输入e时,SLR(1)分析器面临两个选择:继续移进下一个符号 or 根据A : e归约到A,此时SLR(1)分析器前瞻符号c,c存在于Follow(A)中,但此时又可以选择移进c,所以SLR(1)此时又面临着冲突了。

SLR(1)不足之处在于Follow Set太宽泛,处于Follow Set中的前瞻符号不一定能合法的跟在非终结符之后。实际上SLR(1)忽略了分析的上下文,针对SLR(1)的不足由提出了LR(1)分析法。

4. LR(1)

LR(1)的基本原理就是只要前瞻符号能合法跟在归约的非终结符之后就可以进行归约,LR(1)会为每个生成式绑定一个** LookAhead Set**,只有前瞻符号处于这个集合之中才进行归约,它是Follow Set的子集。那么LookAhead Set如何生成呢?

4.1 LookAhead Set生成

我们将生成式一般化为下面的样子:

s -> α .x β, C 
x -> . r

其中 s,x都是非终结符,α β r可以是终结符也可以是非终结符,C 为生成式的LookAhead Set。

x的LookAhead Set = First(β C),即β的FirstSet与C串起来之后的First集

First Set可以理解为非终结符所有生成式中第一个终结符的集合

5. Merak

我将LR(1)分析算法封装成了一个Golang Parser库:Merak,并且用它实现了一个面向对象语言的Parser: Mizar。对此有兴趣的同学可以试用下,它将为你省略手写语法分析器的过程,节省宝贵的时间投入到更加有趣的编译器后端工作中。

阅读全文 »

GNU 汇编器的语法

学习汇编语法的目的

为什么要学习汇编语法呢?原因是我最近在做一个面向对象语言的编译器(地址:https://github.com/Orlion/Mizar),目前已经完成了parser部分,即已经生成了AST,下一步要做的就是语义分析了,而语义分析之后要做的就是生成AT&T汇编代码了,所以有必要提前了解下汇编语法看在语义分析的实现阶段能否有所指导。

先看一段代码

首先我们有这样一段c语言代码:

#include <stdio.h>

char msg[14] = "Hello,world!\n";
 
int main(void)
{
    puts(msg);
    return 0;
}

运行 gcc -S -Os hello.c

    .file   "hello.c"
    .section    .text.startup,"ax",@progbits
    .globl  main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    pushq   %rax
    .cfi_def_cfa_offset 16
    movl    $msg, %edi
    call    puts
    xorl    %eax, %eax
    popq    %rdx
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
    .globl  msg
    .data
    .align 8
    .type   msg, @object
    .size   msg, 14
msg:
    .string "Hello,world!\n"
    .ident  "GCC: (GNU) 4.8.5 20150623 (Red Hat 4.8.5-39)"
    .section    .note.GNU-stack,"",@progbits

接下来解释下AT&T汇编的语法

指令

指令是直接由CPU负责处理的命令,不以.开头的行首缩进的行都是指令行。

    movl    $msg, %edi
    call    puts
    xorl    %eax, %eax

指令由操作符和作为参数的操作数组成,以 movl $msg, %edi 为例,movl 为操作符, $msg%edi 为操作数,操作数以逗号来间隔。

汇编伪操作

. 开头末尾没有:的行都是汇编伪操作。例如,.file "hello.c", .globl main。汇编伪操作是由汇编器而非CPU处理的指令。一般用于在目标文件中记录元数据(meta data)或者设定指定的属性等。例如 .string 是用来定义字符串常量的汇编伪操作。

标签(labal)

以冒号: 结尾的行都是标签行,例如:.LFB0:,main:。 标签具有为汇编伪操作生成的数据或者指令命名(标上符号)的功能,这样就可以在其他地方调用通过标签定义的符号。 标签可以以.开头

注释

支持两种注释:

# xxx

/* xxx
xxx */

助记符后缀

刚才提到的movlsubl为助记符,更准确的说movsub为助记符,末尾的l是后缀,llong的缩写,表示操作对象的数据大小。类似这样的后缀还有b,w,l

|后缀|操作对象的大小|缩写| |-|-|-| |b|8位|byte| |w|16位|word| |l|32位|long|

操作数

操作数有四种: 1. 立即数 2. 寄存器 3. 直接内存引用 4. 间接内存引用

1. 立即数

立即数就是C语言中的字面量,机器语言中立即数以整数的形式出现,能高速访问。像$27这样,立即数用$来标识,如果漏掉了$就成了直接内存引用了。立即数有8位,16位,32位。

2. 寄存器

GUN汇编器规定寄存器以%开头,例如eax寄存器写作%eax

3. 直接内存引用

直接访问固定内存地址的方式。GNC汇编器会将任何整数解释为内存地址并访问。比起使用数字,更常用符号(symbol)直接访问内存。例如.LFE0就是访问符号.LFE0所指向的地址。符号在汇编和链接的过程中会被置换为实际内存地址。

4. 间接内存引用

是将寄存器的值作为内存地址访问的方式。间接内存引用中最通用的就是下方的形式:

disp(base, index, scale)

其中任何一者都可以省略。

上述指令访问disp + (base + index * scale)的地址。 下面详细讲解,首先最简单的间接引用的形式如下:

(%eax)

即只指定基地址(base)的形式。上述表达式将eax寄存器中的值作为内存地址访问。 接着带有disp的形式如下。disp是displacement(偏移)的简称。

4(%eax)

上述就是访问 4 + (eax寄存器中值) 这个内存地址。在C语言中用来访问如下结构体中成员y的情况:

struct point {
    int x; // x占4个字节,即4个内存地址
    int y;
}

最后使用index和scale的情况如下所示:

(%ebx, %eax, 4)

上面访问的就是(ebx寄存器中的值 + eax寄存器中的值 * 4)内存地址。在C语言中用来访问数组,例如访问元素大小为4字节(例如int)的数组中元素的第%ebx个元素时就可以用这种方式。当并非所有的数组访问都可以只靠间接内存引用来表示,因为scale只能是1、2、4、8之一。

2020-09-22更

突然意识到如果要将一个复杂工程的AST编译为汇编代码必须具备能够用汇编实现这个复杂工程的能力才行,这太难了… 所以暂时放弃吧,先编译到了LLVM IR再说,嗯。

2020-10-07更

不如趁此机会学习下汇编以及后续的链接装载,有助于建立宏观的了解。所以还是继续学习吧。 😸

未完待续…

阅读全文 »