toolchain » lex & yacc, 编译原理（一）

2020-10-16 :: 5906 Words

lex & yacc
编译原理
- 教程
- blog
- 术语
- Transpiler
- binary translation
- DSL
- Pass
- Python Language Services
- Android编译

lex & yacc

2014.2

前言

春节期间，空闲时间较多，于是研究了一下lex和yacc的用法。知道lex和yacc，那还是大四学习编译原理那门课时候的事情了。转眼之间，那已经是十年前的事情了。

编译原理在整个大学期间的专业课中，属于难度比较高的课程。而且如果不是计算机专业的话，基本没有可能学到这门课。当时的课程作业是完成一个支持脚本绘图的软件。其难度即使以我现在的眼光来看，也颇不容易。当时只有少数人能够做出来，但基本上是参考教这门课的老师出的一本教辅书来写的。

这个课程作业之所以复杂，主要在于老师要求词法和语法的分析器都必须要自己编码实现。如果退一步，可以使用lex和yacc的话，就没有那么困难了。当然这也与大学里以传授理论为主的思想有关，我还是相当认同这一点的。

再顺便说一句，lex的作者之一是google的前CEO Eric Schmidt，这是他20岁时，在贝尔实验室的作品。当然，不全是他的功劳。实际上lex和yacc都是贝尔实验室的作品，这从lex效仿yacc的书写风格就能略见一斑。相比而言，yacc的地位和复杂度更为重要些。

前置条件

要想研究lex和yacc，除了需要有C语言的基础之外。还需要对正则式和BNF（Backus-Naur Form）有所了解。

教材

LEX & YACC TUTORIAL by Tom Niemann——这本书比较简练，且附有代码，入门级的极品

心得

lex生成的代码中，最重要的是yylex函数，该函数每匹配一个词，就返回一次。yacc生成的代码中，最重要的是yyparse函数，这个函数调用yylex函数以获得所需要的语法词汇。

lex的词法分析，依据用法的不同，可分为三类：

1）需要匹配识别的词汇。

2）需要过滤的词汇。一般是空白、TAB之类的分隔符。

3）直译的词汇。就是那些lex不处理，也不吃掉，而是直接交给yacc分析的词汇。

这三类词汇必须仔细规划，因为被解析的文本中，一旦出现不在上述三类的任何一类中的词汇时，程序就会报错。

yacc的BNF中一般都要包括类似下面的语句：

stmt_list:
          stmt                  { }
        | stmt_list stmt        { }
        ;

其中stmt表示单个语句的语法目标，而stmt_list则是一系列语句的集合。

为什么要添加这一句呢？因为yacc在处理被解析的文本时，如果文本不能最终归结为一个单一的语法目标的时候，程序也会报错。

代码示例参见：

https://github.com/antkillerfarm/antkillerfarm_crazy/tree/master/mylex

这里使用的是lex/yacc在linux上现代版本——flex/bison。

Recursive Descent Parsing：负责解析语句。

Robert M. McClure于1961年编写的TMG(TransMoGrifier)，最早使用了该算法。

Operator-Precedence Parsing：负责解析具有优先级特性的运算表达式。

Polish notation由波兰逻辑学家Jan Łukasiewicz（1878～1956）于1931年提出。共有三种形式：（以3 + 4为例）

前缀表示法，即狭义的Polish notation：+ 3 4。这种表示法被LISP等语言所采用。
中缀表示法：3 + 4
后缀表示法，即reverse Polish notation：3 4 +。这种表示法由于和指令顺序相同（先load操作数，再进行运算），而被广泛应用于编译器领域。

https://www.zhihu.com/question/413146859

如何理解Pratt Parser？

https://zhuanlan.zhihu.com/p/663995549

56行代码用Python实现一个Flex/Lex

编译原理

教程

《Principles of Compiler Design Compilers: Principles, Techniques, and Tools》。该书由于封面上有龙的图案，又被称为“龙书”。下面的虎书、鲸书也是一样的。

《Modern Compiler Implementation in C》，虎书。

《Advanced Compiler Design and Implementation》，鲸书。

以上三本书，被称为编译器领域的圣经。

龙书的作者Alfred Vaino Aho和Jeffrey David Ullman获得了2020年图灵奖。

https://mp.weixin.qq.com/s/UGhHM1jCN0S7TX9jwLcMmQ

2020图灵奖重磅出炉！龙书作者、编程语言先驱共获大奖，是他们解放了一代又一代程序员

https://www.zhihu.com/question/315313590

学习编译原理有什么好的书籍?

https://parsing-techniques.duguying.net/

《Parsing Techniques》的中文译本

blog

https://zhuanlan.zhihu.com/frozengene

一个编译器方面的专栏

http://frozengene.github.io/

一个LLVM方面的blog

https://zhuanlan.zhihu.com/c_1250484713606819840

一个LLVM方面的专栏

术语

AST：abstract syntax tree

ABI：Application Binary Interface

API：Application Programming Interface

比如，int register_netdevice(struct net_device *dev)这个内核函数，原型基本上是不会变的，所以保持这个API稳定是很简单的，但它的ABI就未必了，就算是这个函数定义本身没变，即API没变，而struct net_device的定义变了，里面多了或者少了某一个字段，它的ABI就变了，你之前编译好的二进制模块就很可能会出错了，必须重新编译才行。

CSE：Common subexpression elimination

DCE：Dead code elimination

peephole optimization

ub：undefined behaviour

LHS：Left-Hand-Side

RHS：Right-Hand-Side

SCC：strongly connected component，即强连接分量。一般通过SCC pass获得DAG图。

REPL：Read–eval–print loop

https://juejin.cn/post/7218564871831748664

C++ Standard Library ABI是什么？

https://zhuanlan.zhihu.com/p/125197727

_GLIBCXX_USE_CXX11_ABI

FFI：Foreign Function Interface

libffi提供了一种在运行时调用函数的方式，它允许一个程序动态地调用另一个程序中定义的函数，即使这些函数是用不同的编程语言编写的。

https://blog.ihomura.cn/2021/07/30/%E6%8A%8A%E9%97%AD%E5%8C%85%E5%8F%98%E6%88%90%E5%87%BD%E6%95%B0%E6%8C%87%E9%92%88%E2%80%94%E2%80%94libffi-%E9%97%AD%E5%8C%85%E5%8E%9F%E7%90%86%E8%A7%A3%E6%9E%90

把闭包变成函数指针——libffi闭包原理解析

https://rootjhon.github.io/posts/Lua-FFI/

Lua FFI

Transpiler

Transpiler是一个经常用来和Compiler比较的术语。它用于将一种语言编写的源代码转换为另一种具有相同抽象层次的语言。

当你编译C#时，编译器将函数体转换为中间语言（IL）。这不能称为Transpiler，因为这两种语言的抽象层次完全不同。

而当你编译TypeScript时，编译器将它转换为JavaScript。二者的抽象层次相同，所以你可以称之为Transpiler。

可以看出transpiler和compiler的区别，主要在于两种语言的抽象层次是否相同。因此，transpiler也被称为source-to-source compiler。

binary translation

binary translation是跨指令集平台互操作的一种方法。

https://www.zhihu.com/question/29851229

二进制翻译(binary translation)有没有成熟的现实应用？请介绍一下实现方式与性能瓶颈?

https://zhuanlan.zhihu.com/p/546892934

【连载1/2】谈谈BT二进制转译技术 - 跨指令集平台互操作的兼容性和局限性

https://zhuanlan.zhihu.com/p/548318341

【连载2/2】谈谈BT二进制转译技术 - 跨指令集平台互操作的兼容性和局限性

DSL

tf实现了神经网络的计算图语义模型，但由于其镶嵌于python中，所以是内部DSL编译器。

外部DSL编译器，典型的如verilog、systemverilog，他们是硬件描述语言，应用的领域是数字IC设计，目标代码不是汇编代码，而是逻辑网表文件。

Pass

以上两图展示了One pass/Single pass与Two pass/Multi pass之间的差异。所谓Pass，就是将代码/AST扫描并处理一遍。

早期的编译器一般是Single pass的，它虽然结构简单，但是不便于扩展。所以后来又出现了Multi pass。与之对应的编译器流程，亦被分为前端和后端两部分。

前端：source code -> AST

后端：AST -> target code

而编译流程的每一步，则被抽象为Pass，这个称呼最早为LLVM采用，进而扩展到整个编译原理领域。

pass分为两类，一类是分析(analysis)pass，负责收集信息共其它pass使用，辅助调试或使程序可视化；另一类是变换(transform)pass，改变程序的dataflow/controlflow。

https://www.geeksforgeeks.org/single-pass-two-pass-and-multi-pass-compilers/

Single pass, Two pass, and Multi pass Compilers

https://xz.aliyun.com/t/7257

初探LLVM&clang&pass

http://llvm.org/docs/WritingAnLLVMPass.html

Writing an LLVM Pass

https://www.cnblogs.com/BobHuang/p/17640378.html

从零开始教你写一个LLVM Pass

https://zhuanlan.zhihu.com/p/290946850

LLVM中的pass及其管理机制

Python Language Services

Python Language Services提供了一系列接口用于观察Python程序的运行。比如：

ast：分析abstract syntax tree。

symtable：访问符号表。

官网：

https://docs.python.org/3/library/language.html

Android编译

AOT：Ahead Of Time，指在运行前编译，比如普通的静态编译。

JIT：Just In Time，指在运行时编译，边运行边编译，比如java虚拟机在运行时就用到JIT技术。

https://mp.weixin.qq.com/s/vnaI8FwB4Ot46weAgq18Eg

华为新贵！方舟编译器的荣光和使命

https://www.zhihu.com/answer/812481811

周志德（Fred Chow）

JIT编译最大的优势就是可以通过FDO（feedback-directed optimization）或者叫PGO（profile-guided optimization）来做优化，这样可以以少量的初始运行时开销，换取一些本来要通过重量级静态分析才可以得到、或者静态分析根本无法得到的一些运行时信息，然后基于它来做优化就可以事半功倍。

因此，JIT并不一定不如AOT。

AOT主要为了性能，大多数脚本都是动态类型，即使加了AOT，由于没编译期针对类型的优化，性能也比不上带静态类型的语言的AOT。这种场景提升性能最好的办法还是JIT。

https://zhuanlan.zhihu.com/p/19977592

JIT编译，动态编译与自适应动态编译

https://zhuanlan.zhihu.com/p/48236683

使用Profile Guided Optimization提升Application的性能

https://www.zhihu.com/question/484961291

怎么看现在java等语言纷纷编译成机器码（aot）的趋势？脚本为什么没有出现该趋势？

为了在Android中支持新的Java7-8-9的新特性，Google又开发了D8和R8。

https://juejin.im/post/5d70fb2ce51d4557ca7fddaa

Android CPU, Compilers, D8 & R8

您的打赏，是对我的鼓励