引言
乖乖，以为不用在学编译原理了，谁知道复试还要考。。可怜我的大黑书在学校。。。忘记完了。。
概述
编译器的核心功能
- 把源代码翻译为目标代码
- 分析源代码：词法分析，语法分析，语义分析
- 转换为等价目标代码：中间代码生成，目标代码生成
- 优化
各个模块的功能
- 每一个阶段都将源代码从一种表示转换为另一种表述
- 词法分析器：字符流->单词流
- 语法分析器：单词流->语法树
- 语义分析器：识别标识的属性信息（如int）,语义检查，
- 中间代码生成器：抽象语法树->中间表示
- 代码优化器
常用名词
- 源语言：编写源程序所用的语言
- 目标语言：翻译程序的输出语言
- 翻译器：ide
- 编译器：将源码翻译成中间代码
- 解释器：将高级汇编语言一行一行直接转译运行
词法分析
引言
- 词法分析器的任务是把构成源程序的字符流翻译成词法记号流
- 构造词法分析器的一种简单方法是用状态转换图来描述源语言词法记号的结构，然后用手工把这种状态转换图翻译成识别词法记号的程序
- 词法分析几乎发现不了源程序的错误，词法分析器只能发现诸如没有’;’的错误
术语
词法记号，模式，词法单元
记号举例
词法记号 词法单元举例 模式的非形式化描述 var var var for for for relation <,<=,>,=等 <或<= num 234,E6 任何数值常数 词法分析器需要给记号以属性，用属性来记住记号的附加属性：记号影响语法分析的决策，属性影响记号的翻译<id, 指向符号表“这个id”条目的指针>
串，语言，还有运算，诸如：和，连接，闭包，正闭包
正规式：设字母表为Σ，辅助字母表Σ`={Φ，ε，|，·，*，(，)，}。–>我抄的
① ε和Φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和{ }；
② 任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；
③ 假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1|e2, e1·e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e1)∪L(e2), L(e1)L(e2)和(L(e1))。
④ 仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集状态转换图：图库过期了先略过
有限自动机——>。。。。。。。。。。
- 不确定的有限自动机（NFA）：开始状态是唯一的，一个输入对应一个状态的转换
- 确定的有限自动机（DFA）：开始状态时一个状态的集合，一个输入对应多个状态转换，
- NFA到DFA的转换：记到oneNote上了
- DFA的化简：
- 从正规式到有限自动机：也记到oneNote上了
语法分析
引言
每种程序设计语言都有描述程序语法结构的规则 ，两种常用的文法分析方法都是从左到右扫描输入，每次一个符号。分析期读取词法分析器提供的记号流，检查它是否能够由源语言产生，输出分析树的某种表示
上下文无关文法
定义：上下文无关文法是这样一个四元组（VT , VN , S, P）
VT：终结符集合，非空有限集合，记号名是其同义词
VN：非终结符集合，非空有限集合且VT∩VN=Φ
S：开始符号
P：产生式集合，形如A -> a，A∈VN，a∈(VN∪VT)*
其中，终结符可以理解为词法单元，即是符号的最终形式，非终结符就是匹配终结符过程中引入的中间量
推导—–>用来描述文法定义的语言
分析树—>推导的图形表示
二义性—->一些文法的句子不止一颗分析树
自下而上分析
- 对任何输入串，试图用一切可能的办法，从文法开始符号（根节点）出发，自上而下，从左到右地为输入串建立分析树。
- follow集和first集
