Xiqiu's blog

上表是乔姆斯基文法谱系，一个类型的文法的语言被对应的自动机接受。0型文法达到目前可以制造的最强机器——图灵机。更进一步的神谕机等被称作”超图灵计算“，包含在可计算理论内。

文法G是一个四元组$(V_N,V_T,P,S)$
$V_N$：非终结符集
$V_T$：终结符集
$P$：产生式集合
$S$：开始符号

产生式$\alpha \to \beta$

0型文法（PSG）：$\alpha \subset (V_N \cup V_T)*$，且至少包含一个$V_N$
$\beta \subset (V_N \cup V_T)*$，对产生式没有任何限制
0型文法也称短语文法，0型文法的能力相当于图灵机。任何0型语言都是递归可枚举的，递归可枚举集必定是0型语言。在0型文法的基础上对其产生式形式作出限制，得出1，2，3型文法的定义。

1型文法是context-sensitive，对任一产生式$\alpha \to \beta$都有$\lvert \beta \rvert >= \lvert \alpha \rvert$，仅仅$S \to \epsilon$除外（|β|表示的是β的长度。
注意：虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法。 ）
产生式的形式描述：${\alpha}_1 A {\alpha}_2 \to {\alpha}_1A{\alpha}_2$
(${\alpha}_1$、${\alpha}_2$、$\beta \subset (V_N \cup V_T)*$，$\beta \ne \epsilon$，$A \in V_N$)A只有出现在α1α2的上下文中，才允许用β替换。
　　产生的语言称“上下文有关语言”但S不能出现在产生式的右部。

2型文法是CFG(Context Free Gramma):对任一产生式$\alpha \to \beta$，都有$\alpha \in V_N,\beta \in (V_N \cup V_T)*$
产生式的形式描述：$A \to \beta (A \in V_N)$
以$\beta$取代A时，与A所处上下文无关。产生的语言称“上下文无关语言”

3型文法(RG)，也称正规文法
每个产生式均为$A \to \alpha B$或“ $A \to \alpha$ ”——右线性
$A \to Ba$或$A \to a$左线性。其中$A,B \in V_N,a \in V_T*$。产生的语言称为正规语言。

词法分析

    Thompson算法，子集构造算法（DFA，NFA)，Hopcroft算法

语法分析

    LL（1），消除左递归，提取公共左因子，构造预测分析表，分析过程
    LR（0），构造DFA，构造LR（0）分析表，进行语法分析，写出过程
    短语，巨型，产生式，直接短语，句柄概念

语义分析（语法制导翻译）

    逆波兰表示法
    if，while的逆波兰

中间代码生成（生成汇编）

    数组、if、while的中间代码

代码生成优化

    DAG图的优化

执行汇编（3地址或4地址代码的汇编执行）

参见:

Build Your Own Lisp翻译
此书使用了C语言设计lisp的编译器。以此作为C语言入门，学习C语言的同时认识程序语言的实现。
MyForth
使用C语言构建一个Forth解释器，相对简单。