开始学编译原理一点有趣的东西

[AlexiaChen]

---

title: 开始学编译原理一点有趣的东西
date: 2017-03-28 10:48:27
tags:
- 编译原理
- 程序语言理论

唉，好像又回到大学被《编译原理》狂虐的时代了。因为最近在设计自己的脚本语言解释器，由于词法分析阶段用正则文法(3型文法)就能搞定，但是语法分析阶段不学习上下文无关文法(2型文法)是不行的了，所以出来混迟早是要还的

我在之前的文章《什么是类型安全》提到过著名语言学家乔姆斯基的一个例子，是为了说明语法和语义的区别。其实乔姆斯基作为世界顶级的语言学专家为语言学的研究发展做出了很大的贡献，不要以为人类的语言与程序设计语言没有半点关系（确实，它们之间的关系并不大），乔姆斯基的贡献之一，就是在形式语言(formal language)领域提出了著名的乔姆斯基层级谱系(Chomsky hierarchy)，它把所有的形式语言的形式文法分成了四大类，分别是0型文法，1型文法，2型文法，3型文法。从包含关系上来说，0型文法 > 1型文法 > 2型文法 > 3型文法。 符号'>'表示，X范围大于X， 0型文法是1，2，3型文法的超集(superset)。

那么计算机编程语言到底与上面的形式文法有什么关系呢？因为计算机编程语言的定义就需要用到上面的形式化文法来描述。

其实很多计算机相关的语言背后都有一定的基础。比如：

• LISP，背后是λ演算，这个数学基础给了LISP非常强大的表达能力；（虽然多数人不直接用LISP）至少，LISP给现在各种支持函数式编程的语言提供了借鉴。

• 正则表达式。背后是正则文法（也就是3型文法）。凡是可以使用正则文法定义的语言，都可以使用正则表达式定义描述。当然，经常有人试图用它来匹配各种编程语言的代码，这基本上是肯定要出bug的。原因很简单，多数主流编程语言都是『上下文无关语言』，它是正则语言的超集（参考乔姆斯基层级），记住，正则语言一定是上下文无关的，但是上下文无关的语言不一定能用正则语言来描述定义。

• BNF范式。背后是上下文无关文法（也就是2型文法）。这也是为什么各种编程语言（即使复杂如C++或C#，还包括SQL和正则表达式）的规范文档，甚至不少『标准格式』（如JSON，URI等）的规范文档都喜欢用BNF或EBNF定义。更好玩的是，当你用BNF定义好一门语言时，还可以使用一种称为Parser Generator的程序（如YACC及各语言上的移植，Flex，Bison，ANTLR等，它们有时候也被称作编译器的编译器）来生成这门语言的解析程序(Parser)！当然了，一般工业制作的编程语言的编译器前端部分大部分会这么干，定义好语言描述，用工具直接就生成该语言的抽象语法树了(abstract snytax tree), 不需要自己写词法分析和语法分析了，避免不必要的苦力劳动。为什么能做到这么厉害的功能？这涉及到计算理论的很多知识，但归根到底，就是上下文无关文法。

参考

• 有哪些匹配文本的需求是正则表达式做不了的?
• Context-free language
• 应该如何理解“上下文无关文法”？