哈工大编译原理实验语法分析_前端要以正确的姿势学习编译原理（上篇）

正在找工作&＃xff0c;有没有大佬带带我的&＃xff1f;

前言

最近在我的 timline 上面出现了很多类似《前端为什么要学编译原理》这类文章以及《前端怎么学AST》这类的问题&＃xff0c;但是却发现并没有人给大家介绍前端要如何以系统并且正确地学习编译原理&＃xff0c;所以我就结合自己的经验以及走过的弯路来给大家分享点心得和经验&＃xff0c;希望能让大家少走点弯路。

最后我并不是前端&＃xff0c;只是恰好会写点 Javascript 而已。

目录

上篇&＃xff1a;

• 编译原理为什么难
• 怎么学好编程语言
• 代码到底是什么
• 正则与上下文无关文法
• 编程语言从 AST 才正式开始

下篇&＃xff1a;

• 静态分析
• 类型推导
• AST 的转换
• Conitnuation
• 字节码虚拟机

编译原理为什么难

大家提起编译原理第一反应都是很难&＃xff0c;难到无从下手&＃xff0c;但是为什么难呢&＃xff1f;说白了&＃xff0c;编译原理不就是研究把一门语言解析并且转换成另一门语言的技术吗&＃xff1f;这项技术到底有哪些地方成为了阻碍呢&＃xff1f;我认为这个最大的阻碍其实就是“编程语言”本身。

我相信在看这篇文章的朋友至少已经学会了 Javascript 了吧&＃xff0c;但是我想多嘴问一句&＃xff0c;大家真的懂 Javascript 吗&＃xff1f;能描述出 Javascript 的语法规则吗&＃xff1f;能理解语法所代指的逻辑结构吗&＃xff1f;知道 Javascript 是如何在被解释和执行的吗&＃xff1f;所以&＃xff0c;大家真的懂 Javascript 吗&＃xff1f;反正我是至今没有底气说自己”精通“ Javascript &＃xff0c;原因是我还不懂如何实现一个 JIT。

我们多数时候称自己“精通”某编程语言的时候&＃xff0c;仅仅指会熟练使用某编程语言&＃xff0c;但是编译原理这门学科折腾的核心恰恰是编程语言&＃xff0c;它要求我们对编程语言有深入的了解&＃xff0c;了解它是如何构造和解释的。我们如果没有这项基础其实是很难学好这门学科的。

推荐阅读&＃xff1a;

• 《七周七语言》——看看不同的编程语言都长什么样子
• 编程语言 —— 维基百科
• 编程范式 —— 维基百科

怎么学好编程语言

部分国外高校的计算机专业喜欢用 Lisp 系的 Scheme 入门&＃xff0c;一开始我并不明白其中缘由&＃xff0c;直到我发现他们的课程作业中最后总会要求实现一个简易的 Lisp 解释器时我才恍然大悟。外国学校安排课程的水平真是高明&＃xff0c;学校教 Scheme 可不是为了让学生拿来写工程代码&＃xff0c;而是让学生学习编程以及编程语言本身到底是一个什么东西。

Lisp 是一门具备现代编程语言特性的几乎最简的实现&＃xff0c;所有编程语言都是 Lisp 方言真的不仅仅是一句玩笑话。简易的 Lisp 的解释难度很低&＃xff0c;Lisp 语法的解析只有解析 JSON 同等的难度&＃xff0c;我们会经常看到很多新手用百来行代码就能实现一个 Lisp 解释器。虽然实现一个 Lisp 解释器不难&＃xff0c;但是他对学生来说的意义非常重大&＃xff0c;它能让学生们对编程语言和程序的构造和执行有一个非常非常基础但又非常全面的认识。而这种对编程语言全面的认识&＃xff0c;也正是我们这些拿着 C/C艹 亦或者 Javascript 入门的大家所缺失的。

所以如何学好编程语言&＃xff1f;正途当然是啃我们的经典神书 《SICP》了&＃xff0c;不过考虑到 《SICP》严重的教科书属性&＃xff0c;讲地并不生动有趣&＃xff0c;所以还是给大家推荐一个科普性质更强的书&＃xff0c;叫做《计算的本质》大家可以用这本书先入门&＃xff0c;如果学有余力或者非常有兴趣再去啃《SICP》。

推荐阅读&＃xff1a;

• 《计算的本质&＃xff1a;深入剖析程序和计算机》—— 科普版 SICP
• 《计算机程序的构造和解释》—— 经典神书&＃xff0c;学有余力或者感兴趣再啃
• 《微信小程序也要强行热更代码&＃xff0c;鹅厂不服你来肛我呀》 —— 我自己写的文章&＃xff0c;用 Javascript 实现一个 Javascript 解释器

代码到底是什么

上一节我们提过&＃xff0c;Lisp 的解析难度和 JSON 是一样的&＃xff0c;那我们能不能干脆用 JSON 代替代码呢&＃xff1f;当然可以&＃xff0c;Javascript 的解析后的语法树就是用 JSON 表示的。所以就表达能力来说&＃xff0c;Javascript 的代码和 JSON 是没有差别的。那么问题来了&＃xff0c;代码到底是什么&＃xff1f;

其实代码跟 JSON 一样&＃xff0c;是一种结构化的文本数据格式。在这里我们要仅仅抓着两个特点——“文本”和“结构化”。

代码的第一个特点是文本&＃xff0c;那意味着我们所有对字符串的拼接、截取或者替换等所有操作&＃xff0c;都可以应用在代码上面。很多程序员虽然都能对各类文本的读写了如指掌&＃xff0c;但大家好像都没有意识到代码文件&＃xff0c;也可以是那个可以读写、修改的文件之一。

对代码文件的读写和操作是进入编译世界的第一个重要门槛&＃xff0c;有的时候并不需要太复杂的算法就能够对代码做一些有意义的转换&＃xff0c;比如我们可以直接通过正则分析 import / export / require 来实现一个简易的 webpack&＃xff0c;比如在我之前一篇文章也是通过简单的正则优化尾递归代码。真正有意识地把代码文件当成文本文件以后&＃xff0c;我们就能把代码从此拉下“神坛”&＃xff0c;可以让大家能够像思考文本一样思考代码。

代码的第二个特点则是结构化。不知道大家能不能理解&＃xff0c;代码里面除了字面量意外&＃xff0c;其他部分都只是标识结构而并不具有实际意义&＃xff0c;赋予这些结构意义是解释器如何和执行这段代码。这个特点就是要求我们在看待代码的时候&＃xff0c;要在脑中形成一种结构&＃xff0c;而不再是一行一行的字符串。

比如上面这串简单的 Javascript 代码&＃xff0c;var 这是一个抽象符号&＃xff0c;他是 var 也好是 val 也好&＃xff0c;就算是 #%$ 都没有任何问题&＃xff0c;唯一的目的就是标识了这个结构&＃xff08;语句&＃xff09;是一个声明赋值。变量名 a 标识的是一种联系&＃xff0c;这个 a 具体是什么也是无关紧要的&＃xff0c;只要它所标识的联系不变&＃xff0c;a 也是可以替换成任何字符。这里面唯一有实际意义的就是那个 123&＃xff0c;我不能把它换成 456。

知乎之前有一个问题问为什么一些大佬能够在两个星期内学会一门编程语言&＃xff0c;我的回答是两个星期都够我们造一门编程语言了&＃xff0c;就像 Javascript 也就是 布兰登·艾克 大佬花了一个星期设计的。我虽然肯定不及这些大佬们&＃xff0c;但是让我两个星期内拿 C艹 造一个 Javascript 1.0 还是没什么太大问题的。所以只要把文章到这里之前推荐的书好好看了&＃xff0c;基础补上了&＃xff0c;那么其实大家每个人都能轻松在两个星期内学好一门编程语言。

最后还是要提一下&＃xff0c;能够用两个星期学好一门编程语言并不代表能用两个星期学好一个领域。就像你不能说你学会了 Javascript 就等于学会了前端&＃xff0c;也不能说学会了 Python 就等于学会了人工智能&＃xff08;虽然现在很多坑爹培训班打着人工智能旗号教 Python 基础&＃xff09;&＃xff0c;编程语言仅仅是编程语言&＃xff0c;仅仅是一个工具。

推荐阅读&＃xff1a;

• 《尾递归为啥能优化&＃xff1f;》 —— 我写的文章&＃xff0c;使用简单的字符处理来优化尾递归函数成循环

推荐工具&＃xff1a;

• AST Explorer —— 看看自己常写的 Javascript 长什么样子

正则与上下文无关文法

这篇文章到这里已经是第四个小节了&＃xff0c;但直到这里才算能够正式抱起我们的经典教材——龙书、虎书或者鲸鱼书进行学习了。这一节简单介绍一下编译器前端技术 —— Parser。

编译器前段就在干一件事&＃xff0c;把代码这个结构化的文本文件解析成我们计算机可以理解的数据结构 —— 抽象语法树&＃xff08;AST&＃xff09;。解析代码是一个比较无聊、复杂而又繁琐的过程。这种复杂和繁琐是来由于编程语言本身语法设计的繁琐和复杂导致的。比如我们前文讨论过的 Lisp 由于语法设计的非常简单、一致而又无歧义&＃xff0c;所以解析起来非常轻松&＃xff0c;但是作为代价的就是 Lisp 那个被吐槽很多的括号括号括号。

解析代码一般分成两个步骤&＃xff0c;第一个步骤是词法分析&＃xff0c;将文本的代码转化成一个个 Token。看到这里的大家应该都有一些正则表达式的基础吧&＃xff0c;在解析代码的过程中&＃xff0c;我们需要用正则来分词做词法分析。在编译原理面我们学习正则的时候就不仅仅是学习正则表达式了&＃xff0c;也会学习正则的内核 DFA&＃xff0c;不过这部分难度不大就是了。

解析代码的第二个步骤是语法分析&＃xff0c;语法分析是将我们上面词法分析出的 Token 转化成 AST。语法分析我们要学习上下文无关文法&＃xff08;CFG&＃xff09;&＃xff0c;并且可以用 BNF 这个表示。CFG 比正则表达能力更强&＃xff0c;强在 CFG 能表达递归结构&＃xff0c;常见的递归结构有表达式和代码块。在语法分析这个部分&＃xff0c;会基本的 LL(1) 算法&＃xff0c;能够对自顶向下的分析有足够的了解&＃xff0c;就已经足够了。

无论是正则还是 CFG&＃xff0c;他们都是在用一种形式语言&＃xff08;我们的编程语言也是一种形式语言&＃xff09;&＃xff0c;来描述一种抽象结构&＃xff0c;所以在学习的过程中&＃xff0c;脑子里面一定要这种从抽象结构的概念&＃xff0c;能够事半功倍。

Parser 在编译原理里面是难点但却不是重点&＃xff0c;所以在这一部分大家觉得复杂的算法完全可以跳过&＃xff0c;不建议浪费太多时间。Parser 都是可以根据正则和 CFG 自动生成的&＃xff0c;并不需要自己手写。所以这部分主要目的是学好的是正则和 CFG&＃xff0c;那些复杂的算法学起来意义很小。

最后还有一个非常有趣的现象&＃xff0c;正则表达式是上下文无关文法&＃xff0c;而 BNF 却又是正则文法&＃xff0c;大家可以想想为什么&＃xff1f;

推荐阅读&＃xff1a;

• 对 Parser 的误解 —— 我自己的真正入门的文章
• 龙书、虎书或者鲸鱼书任选 —— 经典编译原理经典教材
• 当然我在扯淡 —— 垠神的博客&＃xff0c;看的时候请自动屏蔽垠神的主观自嗨

推荐工具&＃xff1a;

• Acorn —— Javascript Parser
• REGEXPER —— 将正则表达式以图形的形式展示
• Ohm —— 可以可视化的 BNF 编辑器
• Jison —— 用正则和 BNF 构建通用的 Parser

编程语言从 AST 才正式开始

其实在大多数眼里的编译原理&＃xff0c;都停留在 Parser 这个阶段&＃xff0c;因为大部分人都在学习的时候卡在了个这个阶段。但是事实上 Parser 不过是这个领域最表面的一层技术而已。编程语言从 AST 才算正是开始&＃xff0c;只有到了 AST 的阶段&＃xff0c;我们的计算机才可以对我们的编程语言进行包括分析、解释或者翻译&＃xff0c;而我们前面我们所辛辛苦苦写的代码只不过是给我们这些愚蠢的人类看的罢了。

对编程语言 AST 的分析、转换、解释以及翻译理应是编译原理中最重要的一个部分&＃xff0c;但由于我们经典编译原理书出版时间都比较早&＃xff08;1985年&＃xff09;&＃xff0c;并且也只着眼于当时流行的以 C 为主的编译型语言&＃xff0c;所以它的重点都放在了解析代码和生成汇编两个部分。但是以现在的编程语言角度来看的话&＃xff0c;前端有 Parser Generator&＃xff0c;后端有 LLVM 那么我们更多的重点其实应该跟多地放在中端上来。

不过到这里为止&＃xff0c;我们介绍的内容其实已经足够大部分小伙伴给自己写个 DSL&＃xff0c;给自己写一个编译到 Javascript 的小语言玩了。 但是这足够了吗&＃xff1f;我们到底可以对 AST 做些什么呢&＃xff1f;让我们下篇再见吧。

参考项目&＃xff1a;

• bramblex/blx-fsm —— 自己造的用于描述 FSM 的玩具 DSL
• bramblex/Smooth —— 自己造的玩具小语言

Hello World!