2.编译原理-编译系统设计
编译程序的设计
编译器是编译系统的核心，主要负责解析源程序语义
一般情况下编译流程包含一下四个步骤 ：
- 词法分析
- 语法分析
- 语义分析
- 代码生成
词法分析
词法分析器通过对源文件的扫描获得高级语言定义的词法记号
为了能从一长串代码文本中分析出每一个词法记号，需要引入有限自动机的概念
有线自动机从开始状态启动，读入一个字符作为输入，并根据该字符进入下一个状态，继续读入新的字符，直到遇到结束状态。
var2 = var1 + 100
该语句包含了6个词法记号，分别是：
var=var2+100
语法分析
语法分析器的输入是词法分析器识别的词法记号序列
var2 = var1 + 100
对应的抽象语法树
终结符：由图中可以看出来，所有的词法记号都出现在叶子节点，这样的叶子节点称为终结符
在了解语法分析器工作之前，需要有限获得高级语言的形式化表示，即文法。文法定义了远程需的书写规则，同时也是语法分析器构造抽象语法树的规则。
赋值语句的一般文法：
<赋值语句>=>标识符等号<表达式>分号
- 被<>括起来的内容标识非终结符，直接书写即可
- 上式可以读作：赋值语句推导出标识符、等号、表达式、分号
- 其中表达式也有自己的文法
有了高级语言的文法表示，就可以构造语法分线器来生成抽象语法树。
文法分析算法：
- 自顶向下的LL(1) 分析
- 自底向上的算符优先分析
- LR分析
书本中使用：LL(1)完成语法分析，使用递归下降子程序作为LL(1)算法的一宗便捷实现方式。
递归下降子程序的基本原则是：
-
将产生式左侧的非终结符转化为函数定义，
-
将产生式右侧的非终结符转化为函数调用，
-
将终结符转化为词法记号匹配。
赋值语句：
1void 赋值语句()
2{
3 match(标识符);
4 match(等号);
5 表达式();
6 match(分号);
7}
符号表
是记录符号信息的数据结构
符号存在两种形式：
-
变量
数据的符号化形式
-
函数
代码的符号化形式
变量形式
如：
1extern int var;
定义了一个外部全局变量
符号表结构中包含了：
- 变量的名称：
var - 变量的类型：
int
函数形式
如：
1int sum(int a,int b)
2{
3 int c;
4 c=a+b;
5 return c;
6}
符号表结构中包含了：
- 函数的返回类型：
int - 函数名：
sum - 参数列表：
int - 函数局部变量：
c - 参数变量：
a，b
由于局部变量的存在，符号表必须考虑代码作用域的变化。
符号表需要根据作用域的变化动态的维护变量的可见性
语义分析
语言的文法分为四种：
- 0型
- 1型
- 2型：又称为上下文无关文法，是目前计算机程序语言所采用的的文法。
- 3型 ：正规文法，词法分析器中有限自动机能处理的语言文法正式3型文法
这几类文法对语言的描述能力一次减弱
语义分析是编译器处理流程中对源代码正确性的最后一次检查。
代码生成
代码生成是编译器的最后一个处理阶段。
根据识别的语法模块翻译出目标机器的指令
编译优化
- 提高生成代码的质量
- 会使代码生成过程变得复杂
编译器设计被分为前端、优化器和后端三大部分。
- 前端包含词法分析、语法分析和语义分析。
- 后端包括指令选择、指令调度和寄存器分配。实际完成代码生成的工作
- 优化器则是对中间代码进行优化的操作
优化器
-
常量传播
-
冗余消除
-
复写传播
-
死代码消除
死代码消除优化会把无效的表达式从中间代码中删除
x86指令格式
intel手册
编译系统的汇编器需要把编译器生成的汇编语言程序转化为x86格式的二进制机器指令序列，然后将这些二进制信息存储为ELF格式的目标文件
x86指令结构中，指令被分为前缀、操作码、ModR/M、SIB、偏移量和立即数六个部分。
如下指令：
1add eax, ebx
在汇编语法的分析阶段，需要记录生成的二进制指令需要的信息：
- 指令名称决定操作码
- 指令的寻址方式决定
ModR/M和SIB字段 - 指令中的常量决定偏移量和立即数部分
ELF文件格式
ELF文件格式描述了Linux下可执行文件、可重定位目标文件、共享目标文件。核心转促文件的存储格式
Linux下可以使用readelf命令来查看ELF文件的信息
在ELF文件中，最开始的52个字节记录了ELF文件头部信息
通过它可以确定ELF文件中程序头表和段表的位置和大小
如下：
1[root@localhost c]# readelf -a hello.o
2ELF Header:
3 Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
4 Class: ELF64
5 Data: 2's complement, little endian
6 Version: 1 (current)
7 OS/ABI: UNIX - System V
8 ABI Version: 0
9 Type: REL (Relocatable file)
10 Machine: Advanced Micro Devices X86-64
11 Version: 0x1
12 Entry point address: 0x0
13 Start of program headers: 0 (bytes into file)
14 Start of section headers: 672 (bytes into file)
15 Flags: 0x0
16 Size of this header: 64 (bytes)
17 Size of program headers: 0 (bytes)
18 Number of program headers: 0
19 Size of section headers: 64 (bytes)
20 Number of section headers: 13
21 Section header string table index: 12
22
23Section Headers:
24 [Nr] Name Type Address Offset
25 Size EntSize Flags Link Info Align
26 [ 0] NULL 0000000000000000 00000000
27 0000000000000000 0000000000000000 0 0 0
28 [ 1] .text PROGBITS 0000000000000000 00000040
29 000000000000001a 0000000000000000 AX 0 0 1
30 [ 2] .rela.text RELA 0000000000000000 000001f0
31 0000000000000030 0000000000000018 I 10 1 8
32 [ 3] .data PROGBITS 0000000000000000 0000005a
33 0000000000000000 0000000000000000 WA 0 0 1
34 [ 4] .bss NOBITS 0000000000000000 0000005a
35 0000000000000000 0000000000000000 WA 0 0 1
36 [ 5] .rodata PROGBITS 0000000000000000 0000005a
37 000000000000000d 0000000000000000 A 0 0 1
38 [ 6] .comment PROGBITS 0000000000000000 00000067
39 000000000000002e 0000000000000001 MS 0 0 1
40 [ 7] .note.GNU-stack PROGBITS 0000000000000000 00000095
41 0000000000000000 0000000000000000 0 0 1
42 [ 8] .eh_frame PROGBITS 0000000000000000 00000098
43 0000000000000038 0000000000000000 A 0 0 8
44 [ 9] .rela.eh_frame RELA 0000000000000000 00000220
45 0000000000000018 0000000000000018 I 10 8 8
46 [10] .symtab SYMTAB 0000000000000000 000000d0
47 0000000000000108 0000000000000018 11 9 8
48 [11] .strtab STRTAB 0000000000000000 000001d8
49 0000000000000015 0000000000000000 0 0 1
50 [12] .shstrtab STRTAB 0000000000000000 00000238
51 0000000000000061 0000000000000000 0 0 1
52Key to Flags:
53 W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
54 L (link order), O (extra OS processing required), G (group), T (TLS),
55 C (compressed), x (unknown), o (OS specific), E (exclude),
56 l (large), p (processor specific)
57
58There are no section groups in this file.
59
60There are no program headers in this file.
61
62Relocation section '.rela.text' at offset 0x1f0 contains 2 entries:
63 Offset Info Type Sym. Value Sym. Name + Addend
64000000000005 00050000000a R_X86_64_32 0000000000000000 .rodata + 0
6500000000000f 000a00000002 R_X86_64_PC32 0000000000000000 printf - 4
66
67Relocation section '.rela.eh_frame' at offset 0x220 contains 1 entries:
68 Offset Info Type Sym. Value Sym. Name + Addend
69000000000020 000200000002 R_X86_64_PC32 0000000000000000 .text + 0
70
71The decoding of unwind sections for machine type Advanced Micro Devices X86-64 is not currently supported.
72
73Symbol table '.symtab' contains 11 entries:
74 Num: Value Size Type Bind Vis Ndx Name
75 0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
76 1: 0000000000000000 0 FILE LOCAL DEFAULT ABS hello.c
77 2: 0000000000000000 0 SECTION LOCAL DEFAULT 1
78 3: 0000000000000000 0 SECTION LOCAL DEFAULT 3
79 4: 0000000000000000 0 SECTION LOCAL DEFAULT 4
80 5: 0000000000000000 0 SECTION LOCAL DEFAULT 5
81 6: 0000000000000000 0 SECTION LOCAL DEFAULT 7
82 7: 0000000000000000 0 SECTION LOCAL DEFAULT 8
83 8: 0000000000000000 0 SECTION LOCAL DEFAULT 6
84 9: 0000000000000000 26 FUNC GLOBAL DEFAULT 1 main
85 10: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND printf
书中紧接着文件头的便是程序头表？？？
ELF文件中最关键的结构是段表:Section Headers
段表记录了ELLF文件内所有端的位置和大小等信息
- 保存代码二进制信息的代码段
- 存储数据的数据段
- 保存段宁的名称段表字符串表段
- 存储程序字符串常量的字符串表段
1Section Headers:
2 [Nr] Name Type Address Offset
3 Size EntSize Flags Link Info Align
4 [ 0] NULL 0000000000000000 00000000
5 0000000000000000 0000000000000000 0 0 0
6 [ 1] .text PROGBITS 0000000000000000 00000040
7 000000000000001a 0000000000000000 AX 0 0 1
8 [ 2] .rela.text RELA 0000000000000000 000001f0
9 0000000000000030 0000000000000018 I 10 1 8
10 [ 3] .data PROGBITS 0000000000000000 0000005a
11 0000000000000000 0000000000000000 WA 0 0 1
12 [ 4] .bss NOBITS 0000000000000000 0000005a
13 0000000000000000 0000000000000000 WA 0 0 1
14 [ 5] .rodata PROGBITS 0000000000000000 0000005a
15 000000000000000d 0000000000000000 A 0 0 1
16 [ 6] .comment PROGBITS 0000000000000000 00000067
17 000000000000002e 0000000000000001 MS 0 0 1
18 [ 7] .note.GNU-stack PROGBITS 0000000000000000 00000095
19 0000000000000000 0000000000000000 0 0 1
20 [ 8] .eh_frame PROGBITS 0000000000000000 00000098
21 0000000000000038 0000000000000000 A 0 0 8
22 [ 9] .rela.eh_frame RELA 0000000000000000 00000220
23 0000000000000018 0000000000000018 I 10 8 8
24 [10] .symtab SYMTAB 0000000000000000 000000d0
25 0000000000000108 0000000000000018 11 9 8
26 [11] .strtab STRTAB 0000000000000000 000001d8
27 0000000000000015 0000000000000000 0 0 1
28 [12] .shstrtab STRTAB 0000000000000000 00000238
29 0000000000000061 0000000000000000 0 0 1
30Key to Flags:
31 W (write), A (alloc), X (execute), M (merge), S (strings), I (info),
32 L (link order), O (extra OS processing required), G (group), T (TLS),
33 C (compressed), x (unknown), o (OS specific), E (exclude),
34 l (large), p (processor specific)
且程序头表提示没有信息
1There are no section groups in this file.
2
3There are no program headers in this file.
符号表段
表格形式
1Symbol table '.symtab' contains 11 entries:
2 Num: Value Size Type Bind Vis Ndx Name
3 0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
4 1: 0000000000000000 0 FILE LOCAL DEFAULT ABS hello.c
5 2: 0000000000000000 0 SECTION LOCAL DEFAULT 1
6 3: 0000000000000000 0 SECTION LOCAL DEFAULT 3
7 4: 0000000000000000 0 SECTION LOCAL DEFAULT 4
8 5: 0000000000000000 0 SECTION LOCAL DEFAULT 5
9 6: 0000000000000000 0 SECTION LOCAL DEFAULT 7
10 7: 0000000000000000 0 SECTION LOCAL DEFAULT 8
11 8: 0000000000000000 0 SECTION LOCAL DEFAULT 6
12 9: 0000000000000000 26 FUNC GLOBAL DEFAULT 1 main
13 10: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND printf
符号表段记录了汇编代码中定义的符号信息，重定位表段记录可重定位目标文件中需要重定位的符号信息。
可以看到main、print
重定位表段
表格形式
1Relocation section '.rela.text' at offset 0x1f0 contains 2 entries:
2 Offset Info Type Sym. Value Sym. Name + Addend
3000000000005 00050000000a R_X86_64_32 0000000000000000 .rodata + 0
400000000000f 000a00000002 R_X86_64_PC32 0000000000000000 printf - 4
5
6Relocation section '.rela.eh_frame' at offset 0x220 contains 1 entries:
7 Offset Info Type Sym. Value Sym. Name + Addend
8000000000020 000200000002 R_X86_64_PC32 0000000000000000 .text + 0
ELF格式定义
Linux提供了ELF文件格式的定义
在目录/usr/include/elf.h 中描述了ELF文件数据结构的定义。
在实现汇编器和连接器的代码中都使用了该头文件
— END —