编译原理课程设计
一. 虚拟机
stack
heap
data
text 代码区，存放指针和内存地址的数据
PC
SP
BP
AX
MSET 用于生成内存分配代码
call //1. push pc用于ret返回执行，jump pc让pc指向函数的地址
…
POP // bp回到父函数的基址，即销毁了栈帧
ret // 让pc指向call之前入栈的pc的地址，即下一条需要执行的指令
二. 词法分析
关键处理点：
（1）字符串放入data （2） 标识符识别时需要放入符号表内存问题
（1） 源代码字符串src并没有释放初始化问题
（1）我们每个模块现在都是重复调用初始化的代码，便于单个功能测试。
3.待完善功能
（1） 词法分析错误检查
（2）符号表调试代码，词法分析程序调用结束之后，我们需要检查符号表
三.
python字符串转换
c_void_p适合用于传递非字符串指针，c_char_p适合传递字符串。
四. 编译问题
windows中我们使用-l指定链接库文件时(这里不是说头文件不要搞混了)，是使用的动态链接库。
编译好的dll或exe文件只记录了其依赖的动态库库名，并没有记录具体的路径。所以，在链接器
进行动态链接的时候，可能会找不到动态库路径。windows默认查找动态链接库默认路径是当前可执行
文件的目录->C:\Windows\System32->系统变量PATH
解决方法是：
（1）先使用makefile或gcc原生命令将所有的库文件编译成dll放入/lib/目录，
然后在windos PATH添加该/lib/的路径
（2）如果不行则直接将dll复制到C:\Windows\System32。然后用管理员身份运行gitbash查看是否
复制成功
（3）在调试的时候，我们可以直接在launch.json添加系统路径，但是如果只是在launch.json
中添加环境变量则只会在调试时生效。要一直生效需要在windows PATH配置
（4）因为编译好的dll或exe文件只记录了其依赖的动态库库名，并没有记录具体的路径。所以在两个
项目具有相同名称的dll文件时就会导致链接错误。此时我们使用ldd链接器命令来查看哪些链接有问题，
之后将同名dll文件修改为不同名字，解决冲突。makefile和tasks.json
在需要链接库的时候使用makefile比tasks.json更好，因为task.json必须当存在链接库时才能完成编译。
而makefile更加灵活，当没有静态库时可以根据以来生成静态库然后用于编译编译过程
在 GCC 编译过程中，生成 .o 目标文件（汇编阶段生成）此时通常不需要指定动态链接库，而链接阶段才需
要显式链接这些库。因为在汇编阶段(生成.o文件)，编译器仅检查函数是否存在声明（通过头文件）。
只有在链接阶段时，才需要链接其他的动态库。此外我们特别需要注意的是.o文件是由单个.c文件生成的。
每个.c文件对应一个.o文件。多个.o文件链接起来就成为库文件或可执行文件。静态库和动态库都包含了链
接的所有代码，只是在链接生成exe文件时使用有区别。静态库会被打包到exe中，动态库只会在exe中保留
其地址。其中要注意的是链接生成exe时，使用链接.o文件生成和和链接静态库文件是一个道理，都是把所有代码
打包到了exe。
这里还要注意一点注意：不是链接生成exe文件或库文件了，
就能保证运行时可以找到并执行对应库文件或exe文件中的相关函数代码。静态链接确实链接成功之后就能保证
能够运行生成的exe和库文件中的代码。因为静态链接时把所有需要的库文件代码全部打包到了一起。但是如果
是动态链接，链接成功只是确保这些代码确实被定义。在运行时，可能还需要额外做一些操作指定dll路径，
如第一点说所，windwos需要指定dll搜索路径。
链接的作用是将.o文件和其他库文件链接生成可执行文件或库文件，分为动态链接，静态链接。
在生成.o时只会检查函数的声明，不管有没有定义。如果没有定义则先被标记为未定义的符号。
但不会报错。在链接阶段会对未定义的符号进行检查，如果在本文件中存在定义或是指定了函数定义所
在的链接库，则正确。否则报错
五. 运行时问题
对于一个c程序，如果编译时需要依赖各种头文件和动态库。在编译完成之后在运行的时候还需要依赖这
些头文件吗？
运行时动态库需要依赖，头文件不需要。因为头文件只是用于在汇编阶段(生成.o文件)时编译器检查函数是否存
在声明（通过头文件）。如果我们指定好运行时的dll路径，则可以直接在任何位置运行exe。如果不想指定
路径，那就编译时使用静态链接，把所有代码都编译到一个exe中。
词法分析分析标识符时，需要联动符号表，不然无法使用系统函数。
修改当前next函数，像xc-tutor.c的next函数一样正确处理标识符，计算标识符哈希值：
在符号表中查找， 没找到则添加新条目符号表字段定义 枚举是一个10元组，最后一个为标记有效数据为前面9个
五. 语法分析
EBNF 扩展巴克斯范式
（1）<非终结符>，表示<>中存放非终结符
（2）[“,” id ]表示按，id的顺序出现一次或0次。
（3）{“,” id} 表示按，id的顺序出现无穷次或0次我们项目中定义的终结符
type 关键字
id 标识符
empty_statement 空
enum {Token, Hash, Name, Type, Class, Value, BType, BClass, BValue, IdSize};
Type：函数的返回类型，变量的类型
Class: 函数是系统函数还是自定义函数，变量是否为局部变量
value: 函数的入口地址，变量的栈地址
抽象语法树AST的本质并不需要每遇到一个token就从语法树的树根(program)开始搜索，而是根据尽可能一次
匹配更多的token，直到不能再匹配再考虑回到上一层进行搜索。也就是先序遍历AST。树根为终结符，其他
节点为函数。所以叫抽象语法树，因为节点为函数的树是不存在的。
program ::= {global_declaration}+
global_declaration ::= enum_decl | variable_decl | function_decl
enum_decl ::= ‘enum’ [id] ‘{’ id [‘=’ ‘num’] {‘,’ id [‘=’ ‘num’] ‘}’
//variable_decl ::= type {‘‘} id { ‘,’ {’’} id } ‘;’
variable_decl ::= type {‘‘} id [’=’ ‘num’ | ‘string’ | ‘char’ ] { ‘,’ {'’} id [‘=’ ‘num’ | ‘string’ | ‘char’ ]} ‘;’
function_decl ::= type {‘‘} id ‘(’ parameter_decl ‘)’ ‘{’ body_decl ‘}’
parameter_decl ::= type {’’} id {‘,’ type {‘*’} id} // 函数参数
body_decl ::= {variable_decl} {statement} // 匹配函数体
statement ::= non_empty_statement | empty_statement
non_empty_statement ::= if_statement | while_statement | ‘{’ statement ‘}’
| ‘return’ expression | for_statement | enum_decl |expression ‘;’
if_statement ::= ‘if’ ‘(’ expression ‘)’ statement [‘else’ non_empty_statement]
while_statement ::= ‘while’ ‘(’ expression ‘)’ statement
for_statement ::= ‘for’ ‘(’ [expression] ‘;’ [expression] ‘;’ [expression] ‘)’ statement
条件表达式的特殊结构
cond_expr ::= expression ‘?’ expression ‘:’ expression
数组访问的特殊结构
array_access ::= expression ‘[’ expression ‘]’
expression - 表示一个完整的表达式，由一个单元表达式开始，可以后跟任意多个二元运算符和单元表达式的组合
unit_expr - 表达式的基本单元，包括：数字、字符串、sizeof表达式、标识符表达式、括号表达式、一元运算表达式和前置递增/递减
num - 数字常量，如整数
string - 字符串常量，由双引号包围
sizeof_expr - sizeof运算，用于获取类型或表达式的大小
type_name - 类型名称，可以是int或char，后面可跟任意数量的星号(表示指针)
id_expr - 标识符表达式，可能是函数调用或变量访问
func_call - 函数调用，括号内可以有零个或多个以逗号分隔的参数表达式
var_access - 变量访问（为空表示直接访问变量值）
paren_expr - 括号表达式，可以是类型转换或被括号包围的表达式
type_cast - 类型转换，将一个表达式转换为指定类型
unary_expr - 一元运算表达式，包括：解引用、取地址、逻辑非、按位非、正号和负号操作
pre_inc_dec - 前置自增或自减操作
bin_op - 二元运算符，包括多种运算符如赋值、条件、逻辑、算术等
cond_expr - 条件表达式，形如condition ? expr_if_true : expr_if_false
array_access - 数组访问表达式，形如array[index]
表达式计算测试 a+b, a+b*c (a+b)*c
函数返回值测试 pass
递归和内部块测试
系统函数测试
字符串测试
如果while块中存在变量定义呢
后期考虑增加for循环
保存旧基址，保存新栈帧的基址，分配形参和分配局部变量地址
pop恢复旧基址
ret恢复栈顶指针，将栈顶指针指向上一个调用函数栈帧的栈顶。等于释放掉了当前栈帧
call: 入栈保存下一条指令的地址，并将pc指向调用函数的地址，实现跳转
LEV：先释放栈帧，让sp指向保存旧bp的地址，然后恢复旧基址，然后释放掉这个保存旧bp的地址。
就等效于movl，pop，ret三条指令
六. 合并测试
对旧版本进行修改并提交后，然后在当前版本对新的旧版本进行merge后，会造成旧版本对新版本的完全覆盖吗，我只需要更新旧版本新修改提交的部分而不需要更新其他部分
比如，词法分析中init中存在next，语法分析是词法分析的后续版本，在语法分析中init中去掉的next，然后在
词法分析做一些修改并提交之后和当前语法分析合并，init中的next会又重新使用词法分析的吗？
按道理不会，因为
（1）如果旧版本和当前版本修改了不同文件 → 自动合并，互不影响。
（2）如果修改了同一文件的不同区域 → 自动合并，保留双方改动。
（3）如果修改了同一文件的同一区域 → 产生冲突，需手动解决。
唯一可能影响的根据第三点，除非又再次在词法分析中init中同样的位置添加next，
此时在语法分析合并会造成合并冲突。
解决方法：（1）如果冲突了就手动解决冲突，保留需要的版本。
（2）使用cherry-pick，精确合并指定的词法分析版本。但是还是会存在一个问题，如果词法分析中init
中next的删除恰好和词法分析中的其他修改在同一版本提交，那么精确合并这个版本还是需要手动解决冲突。
七. 虚拟机架构
text代码段，data数据段(字符串常量，全局变量)
八. 可能优化
1.
修改建议：如果要支持中途定义变量，我们只能替换body_decl ::= {variable_decl} {statement}
函数体匹配文法的{variable_decl}，使用先扫描一遍函数体，只寻找变量声明。把变量的地址分配好。
九. 符号表优化
（1）新符号表采用作用域栈的形式，每一个栈表示一个作用域，维护一张独立的哈希表。对于下述两种
情况，虽然会存在level相同的情况，但是他们不可能同时存在栈中。同一时刻栈中的每个作用域都是不同
的。
（2）关于作用域出栈之后被覆盖的问题。栈中位置被覆盖但内存中还是存在。您可以遍历全局作用域
的符号表，找出所有函数和全局变量，然后针对每个函数递归遍历其func_scope获取局部变量信息，这
已足够生成完整的目标代码。
同一函数中的多个代码块：
int main() {
// 函数作用域 level=1{
// 代码块1 level=2
}{
// 代码块2 level=2 (与代码块1相同level)
}
}不同函数中的作用域：
void func1() {
// 函数1作用域 level=1
}
void func2() {
// 函数2作用域 level=1 (与func1相同level)
}
系统块需不需要额外指定一种符号表类型
文法不支持在代码块，while,for中定义变量。while和for没有作用域。所以while和for就不新建作用域了。
文法支持在代码块中定义函数，所以代码块需要新建一个作用域。
没有代码块的文法，考虑在代码块中添加function_decl
non_empty_statement ::= if_statement | while_statement | ‘{’ statement ‘}’
| ‘return’ expression | for_statement | function_decl | expression ‘;’能够打印符号表
在语法制导的同时结合符号表和中间代码一起输出。只要是进行函数调用或变量定义和使用
都在对应中间代码后面加上其符号表信息。能够支持使用变量初始化，这里很简单直接存储变量的偏移，等分配完内存后生成赋值指令即可。
枚举只生成符号，没有中间代码。所以如果文法允许，可以很简单的集成到函数中
十. 函数栈帧
1. 访问函数参数时偏移为正往高地址方向偏移。
2. 函数的返回值并不在调用栈帧，而是分三种情况。
- 直接放在ax中或者把地址放在ax。
- 如果太大编译器会使用返回值优化修改函数签名,此时返回值内存就在主调函数栈上，被调函数通过指针修改主调函数内存。根本没有返回值拷贝，是很高效的。
structBigDatagetBigData()->voidgetBigData_Hidden(structBigData*hidden_ptr) - 临时变量拷贝(最稳妥)
- 编译器在主调函数的栈帧里，开辟一块匿名临时内存（也就是你说的临时变量）。
- 之后编译器优化把这个临时变量的地址作为隐藏指针传给 getBigData()
- 被调函数直接修改主调内存
- 主调函数调用赋值操作（memcpy 或 operator=），把这块临时变量里的数据，完完整整地拷贝 到 myData 里
3. sp指针的问题
因为函数调用栈帧是连续分配的，所以sp并不需要特殊处理，只需要再ret时清理掉当前栈帧就会自动恢复到之前的栈帧位置。
高地址
±---------------+
| 调用者栈帧 |
±---------------+
| 参数 n | bp + n
| 参数 2 | bp + 2
| 参数 1 | bp + 1
| 返回地址 | bp + 2 <- CALL指令压入，目的把PC重定向该地址执行下一条代码区指令。
| 旧bp指针 | bp + 0 <- ENT指令压人 bp指向这里
| 局部变量 1 | bp - 1
| 局部变量 2 | bp - 2
| … |
±---------------+
低地址
十一. 编译器的不足
- 按道理来说需要根据AST持久化保存语法节点，然后扫描AST生成中间代码和符号表，最后根据中间代码
和符号表生成汇编代码。
我们的编译器是单遍的：没有生成AST持久化保存每个语法节点的值。这带来的问题就是所有的语法节点
在语法分析后就被丢弃。导致问题：我们必须在语法分析时直接同步生成中间代码。设计的一部分，
并且语言特性也必须适应这种限制。 - 不可以在函数中直接定义函数
因为虚拟机栈中的中间代码是顺序生成的，所以如果在栈中定义函数会造成两个函数中间代码的重复嵌套。 - 不支持在块中定义函数
- 不支持函数声明
- 除非使用双栈结构，函数代码单独放到一个栈中。然后递归创建，如果函数中嵌套定义函数，则递归创建
函数代码段。递归创建的前提是，每个函数的代码段都要单独分配一块固定的大小。所以总体来看比较麻烦
，这是我们语法制导解释器的架构原因，因为我们需要生成函数的虚拟机中间代码。
十二. 优良编译器的实践特性
- 语法分析生成AST同时生成符号表(使用作用域栈，符号表的核心通过作用域地址找到上层作用域，通过
为每个作用域命名便于生成汇编代码标识) - 通过符号表生成中间代码(四元式)，注意不是把所有四元式全部放入一个列表，而是要用另外的数据
结构保存不同的四元式，目的是保存作用域地址来区分不同的变量和函数。比如全局变量的四元式放入
全局变量结构体，函数四元式放入不同函数的结构体。这样保证在生成汇编代码时，就能够区分作用域了。
同时注意汇编代码是根据标识来区分作用域的，这也是我们之前在符号表保存作用域的特定标识的原因。 - 有了汇编代码就可以直接通过汇编器生成obj文件
- 之后将obj交给链接器ldd处理。ldd查找是否有未定义的符号（函数，变量）。然后
查找需要链接的文件。