Gang 收录于编译原理

2022-04-24 约 1200 字预计阅读 6 分钟

编译程序的设计

编译器是编译系统的核心，主要负责解析源程序语义

一般情况下编译流程包含一下四个步骤：

词法分析
语法分析
语义分析
代码生成

词法分析

词法分析器通过对源文件的扫描获得高级语言定义的词法记号

为了能从一长串代码文本中分析出每一个词法记号，需要引入有限自动机的概念

有线自动机从开始状态启动，读入一个字符作为输入，并根据该字符进入下一个状态，继续读入新的字符，直到遇到结束状态。

var2 = var1 + 100

该语句包含了6个词法记号，分别是：

var
=
var2
+
100

语法分析

语法分析器的输入是词法分析器识别的词法记号序列

var2 = var1 + 100

对应的抽象语法树

终结符：由图中可以看出来，所有的词法记号都出现在叶子节点，这样的叶子节点称为终结符

在了解语法分析器工作之前，需要有限获得高级语言的形式化表示，即文法。文法定义了远程需的书写规则，同时也是语法分析器构造抽象语法树的规则。

赋值语句的一般文法：

<赋值语句>=>标识符等号<表达式>分号

被<>括起来的内容标识非终结符，直接书写即可
上式可以读作：赋值语句推导出标识符、等号、表达式、分号
其中表达式也有自己的文法

有了高级语言的文法表示，就可以构造语法分线器来生成抽象语法树。

文法分析算法：

自顶向下的LL(1) 分析
自底向上的算符优先分析
LR分析

书本中使用：LL(1)完成语法分析，使用递归下降子程序作为LL(1)算法的一宗便捷实现方式。

递归下降子程序的基本原则是：

将产生式左侧的非终结符转化为函数定义，
将产生式右侧的非终结符转化为函数调用，
将终结符转化为词法记号匹配。

赋值语句：

1
2
3
4
5
6
7


void 赋值语句()
{
    match(标识符);
    match(等号);
    表达式();
    match(分号);
}

符号表

是记录符号信息的数据结构

符号存在两种形式：

变量

数据的符号化形式
函数

代码的符号化形式

变量形式

如：

1

extern int var;

定义了一个外部全局变量

符号表结构中包含了：

变量的名称：var
变量的类型：int

函数形式

如：

1
2
3
4
5
6


int sum(int a,int b)
{
     int c;
     c=a+b;
     return c;
}

符号表结构中包含了：

函数的返回类型：int
函数名：sum
参数列表：int
函数局部变量：c
参数变量：a，b

由于局部变量的存在，符号表必须考虑代码作用域的变化。

符号表需要根据作用域的变化动态的维护变量的可见性

语义分析

语言的文法分为四种：

0型
1型
2型：又称为上下文无关文法，是目前计算机程序语言所采用的的文法。
3型：正规文法，词法分析器中有限自动机能处理的语言文法正式3型文法

这几类文法对语言的描述能力一次减弱

语义分析是编译器处理流程中对源代码正确性的最后一次检查。

代码生成

代码生成是编译器的最后一个处理阶段。

根据识别的语法模块翻译出目标机器的指令

编译优化

提高生成代码的质量
会使代码生成过程变得复杂

编译器设计被分为前端、优化器和后端三大部分。

前端包含词法分析、语法分析和语义分析。
后端包括指令选择、指令调度和寄存器分配。实际完成代码生成的工作
优化器则是对中间代码进行优化的操作

优化器

常量传播
冗余消除
复写传播
死代码消除

死代码消除优化会把无效的表达式从中间代码中删除

x86指令格式

intel手册

架构开发人员手册

编译系统的汇编器需要把编译器生成的汇编语言程序转化为x86格式的二进制机器指令序列，然后将这些二进制信息存储为ELF格式的目标文件

x86指令结构中，指令被分为前缀、操作码、ModR/M、SIB、偏移量和立即数六个部分。

如下指令：

1

add eax, ebx

在汇编语法的分析阶段，需要记录生成的二进制指令需要的信息：

指令名称决定操作码
指令的寻址方式决定ModR/M和SIB字段
指令中的常量决定偏移量和立即数部分

ELF文件格式

ELF文件格式描述了Linux下可执行文件、可重定位目标文件、共享目标文件。核心转促文件的存储格式

Linux下可以使用readelf命令来查看ELF文件的信息

在ELF文件中，最开始的52个字节记录了ELF文件头部信息

通过它可以确定ELF文件中程序头表和段表的位置和大小

如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85


[root@localhost c]# readelf -a hello.o
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          672 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           64 (bytes)
  Number of section headers:         13
  Section header string table index: 12

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000000000  00000040
       000000000000001a  0000000000000000  AX       0     0     1
  [ 2] .rela.text        RELA             0000000000000000  000001f0
       0000000000000030  0000000000000018   I      10     1     8
  [ 3] .data             PROGBITS         0000000000000000  0000005a
       0000000000000000  0000000000000000  WA       0     0     1
  [ 4] .bss              NOBITS           0000000000000000  0000005a
       0000000000000000  0000000000000000  WA       0     0     1
  [ 5] .rodata           PROGBITS         0000000000000000  0000005a
       000000000000000d  0000000000000000   A       0     0     1
  [ 6] .comment          PROGBITS         0000000000000000  00000067
       000000000000002e  0000000000000001  MS       0     0     1
  [ 7] .note.GNU-stack   PROGBITS         0000000000000000  00000095
       0000000000000000  0000000000000000           0     0     1
  [ 8] .eh_frame         PROGBITS         0000000000000000  00000098
       0000000000000038  0000000000000000   A       0     0     8
  [ 9] .rela.eh_frame    RELA             0000000000000000  00000220
       0000000000000018  0000000000000018   I      10     8     8
  [10] .symtab           SYMTAB           0000000000000000  000000d0
       0000000000000108  0000000000000018          11     9     8
  [11] .strtab           STRTAB           0000000000000000  000001d8
       0000000000000015  0000000000000000           0     0     1
  [12] .shstrtab         STRTAB           0000000000000000  00000238
       0000000000000061  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

There are no section groups in this file.

There are no program headers in this file.

Relocation section '.rela.text' at offset 0x1f0 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000005  00050000000a R_X86_64_32       0000000000000000 .rodata + 0
00000000000f  000a00000002 R_X86_64_PC32     0000000000000000 printf - 4

Relocation section '.rela.eh_frame' at offset 0x220 contains 1 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000020  000200000002 R_X86_64_PC32     0000000000000000 .text + 0

The decoding of unwind sections for machine type Advanced Micro Devices X86-64 is not currently supported.

Symbol table '.symtab' contains 11 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS hello.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1 
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    3 
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    4 
     5: 0000000000000000     0 SECTION LOCAL  DEFAULT    5 
     6: 0000000000000000     0 SECTION LOCAL  DEFAULT    7 
     7: 0000000000000000     0 SECTION LOCAL  DEFAULT    8 
     8: 0000000000000000     0 SECTION LOCAL  DEFAULT    6 
     9: 0000000000000000    26 FUNC    GLOBAL DEFAULT    1 main
    10: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND printf

书中紧接着文件头的便是程序头表？？？

ELF文件中最关键的结构是段表:Section Headers

段表记录了ELLF文件内所有端的位置和大小等信息

保存代码二进制信息的代码段
存储数据的数据段
保存段宁的名称段表字符串表段
存储程序字符串常量的字符串表段

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000000000  00000040
       000000000000001a  0000000000000000  AX       0     0     1
  [ 2] .rela.text        RELA             0000000000000000  000001f0
       0000000000000030  0000000000000018   I      10     1     8
  [ 3] .data             PROGBITS         0000000000000000  0000005a
       0000000000000000  0000000000000000  WA       0     0     1
  [ 4] .bss              NOBITS           0000000000000000  0000005a
       0000000000000000  0000000000000000  WA       0     0     1
  [ 5] .rodata           PROGBITS         0000000000000000  0000005a
       000000000000000d  0000000000000000   A       0     0     1
  [ 6] .comment          PROGBITS         0000000000000000  00000067
       000000000000002e  0000000000000001  MS       0     0     1
  [ 7] .note.GNU-stack   PROGBITS         0000000000000000  00000095
       0000000000000000  0000000000000000           0     0     1
  [ 8] .eh_frame         PROGBITS         0000000000000000  00000098
       0000000000000038  0000000000000000   A       0     0     8
  [ 9] .rela.eh_frame    RELA             0000000000000000  00000220
       0000000000000018  0000000000000018   I      10     8     8
  [10] .symtab           SYMTAB           0000000000000000  000000d0
       0000000000000108  0000000000000018          11     9     8
  [11] .strtab           STRTAB           0000000000000000  000001d8
       0000000000000015  0000000000000000           0     0     1
  [12] .shstrtab         STRTAB           0000000000000000  00000238
       0000000000000061  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
  L (link order), O (extra OS processing required), G (group), T (TLS),
  C (compressed), x (unknown), o (OS specific), E (exclude),
  l (large), p (processor specific)

且程序头表提示没有信息

1
2
3


There are no section groups in this file.

There are no program headers in this file.

符号表段

表格形式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


Symbol table '.symtab' contains 11 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 FILE    LOCAL  DEFAULT  ABS hello.c
     2: 0000000000000000     0 SECTION LOCAL  DEFAULT    1 
     3: 0000000000000000     0 SECTION LOCAL  DEFAULT    3 
     4: 0000000000000000     0 SECTION LOCAL  DEFAULT    4 
     5: 0000000000000000     0 SECTION LOCAL  DEFAULT    5 
     6: 0000000000000000     0 SECTION LOCAL  DEFAULT    7 
     7: 0000000000000000     0 SECTION LOCAL  DEFAULT    8 
     8: 0000000000000000     0 SECTION LOCAL  DEFAULT    6 
     9: 0000000000000000    26 FUNC    GLOBAL DEFAULT    1 main
    10: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND printf

符号表段记录了汇编代码中定义的符号信息，重定位表段记录可重定位目标文件中需要重定位的符号信息。

可以看到main、print

重定位表段