编译原理

编译器的工作流程

编译程序的工作

词法分析

识别出正确的单词，转换成统一格式，备用。
转换
- 对基本字、运算符、界线符的转换
- 标识符的转换
- 常数的转换
- 转换完成后的格式：（类号、内码）
描述此法分析的有效工具：正规式、有限自动机

语法分析

在词法分析的基础上根据语法规则将单词分解成各种语法短语，一般表示为语法树。

语法规则：又称为文法；规定单词如何构成短语、语句、过程和程序。

语法规则的表示：

BNF: A::=B|C

巴科斯范式(Backus–Naur form)

BNF

课本上的 BNF 的构成规则

() ———— 提因子

例如： U -> ax|ay|az 改写成 U -> a(x|y|z)
{} ———— 重复指定次数

例如：<标识符> -> <字母>{<字母>|<数字> $}_0^5$ 表示标识符由 0-6个字符或数字构成，也可以不指定上下限定表示不限长度重复
[] ———— 任选符号

例如：[+|-]<数字>{<数字>}
-> ———— 有什么组成
| ———— 或者

维基百科上的 BNF 也是常用编程语言中的 BNF 表示方式

<symbol> ::= __expression__

其中： <symbol> 是非终结符(nonterminal variable aka. $V_n$)并且总是由尖括号包围.

::= 表示位于该运算符左边的符号总是被右边的表达式替代

__expression__ 表示一个或多个终结符($V_t$)或者非终结符($V_n$)构成的串

语法分析的方法：

推导(derive)

eg. 判断 x=a+b*50 是否是合法语句
语法规则：

    A::=V=E
    E::=T|E+T
    T::=F|T*F
    F::=V|(E)|C
    V::=Label
    C::=Const

A 
-> V=E      -> V=E+T    -> v=E+T*F  -> V=E+T*C  -> V=E+T*50
-> V=E+F*50 -> V=E+V*50 -> V=E+b*50 -> V=T+b*50
-> V=F+b*50 -> V=V+b*50 -> V=a+b*50