CLQ工作室开源代码 - ⭐[网文收集]编译器实现文章收集合集

您的位置：首页 >> CLQ工作室开源代码 >> 主题: ⭐[网文收集]编译器实现文章收集合集 [回主站] [分站链接]

您的位置：首页 >> CLQ工作室开源代码 >> 主题: ⭐[网文收集]编译器实现文章收集合集 [最新] [回主站]

标题

⭐[网文收集]编译器实现文章收集合集

clq

浏览(100) + 2023-12-19 14:01:12 发表编辑

关键字:

[2023-12-29 20:27:33 最后更新]
[网文收集]编译器实现文章收集合集

其实内容很多。精选一部分备查。

--------------------------------------------------------

1.
https://baike.baidu.com/item/%E7%BC%96%E8%AF%91%E7%A8%8B%E5%BA%8F/8290180

"
分析部分源程序的分析是经过词法分析、语法分析和语义分析三个步骤实现的。词法分析由词法分析程序（又称为扫描程序）完成，其任务是识别单词（即标识符、常数、保留字，以及各种运算符、标点符号等）、造符号表和常数表，以及将源程序换码为编译程序易于分析和加工的内部形式。语法分析程序是编译程序的核心部分，其主要任务是根据语言的语法规则，检查源程序是否合乎语法。如不合乎语法，则输出语法出错信息；如合乎语法，则分解源程序的语法结构，构造中间语言形式的内部程序。语法分析的目的是掌握单词是怎样组成语句的，以及语句又是如何组成程序的。语义分析程序是进一步检查合法程序结构的语义正确性，其目的是保证标识符和常数的正确使用，把必要的信息收集和保存到符号表或中间语言程序中，并进行相应的语义处理。
"

2.
https://www.zhihu.com/column/c_1538128122850877440
"
计算机自制编译器
从0开始自制计算机编译器
"
网友的文章。还有
https://www.zhihu.com/column/c_1383722427357159424
"
上一个专栏，我仿照着别人的案例自制了一个解释器：
计算机自制解释器
www.zhihu.com/column/c_1383722427357159424

那么接下来，就该自制编译器了。
"

3.
https://zhuanlan.zhihu.com/p/659845972
"
编译原理中，lex，flex，yacc，bison是四个非常常用的工具，下面我来深入地分别说明一下它们的使用场景、作用和原理。

-1. Lex：Lex是一种用于创建词法分析器的工具，也称为扫描器生成器。它的主要作用是将输入的字符流转换为一系列的标记（tokens）。使用场景主要是在编译器的前端阶段，用来进行词法分析。它的工作原理是通过正则表达式来描述词法规则，然后根据这些规则生成相应的C语言代码。

-2. Flex：Flex是Lex的另一种实现，同样是用来生成扫描器的工具。它与Lex的最大区别是，Flex生成的扫描器是可重入的，这使得它可以在多线程环境中使用。Flex的使用场景和作用与Lex基本相同，都是用来进行词法分析。其工作原理也是通过正则表达式来描述词法规则，然后生成相应的C语言代码。

-3. Yacc：Yacc（Yet Another Compiler-Compiler）是一个用于生成语法分析器的工具。它的主要作用是根据输入的语法规则生成一个语法分析器，用来进行语法分析。使用场景主要是在编译器的前端阶段，用来进行语法分析。Yacc的工作原理是通过BNF（巴科斯-诺尔范式）来描述语法规则，然后根据这些规则生成相应的C语言代码。

-4. Bison：Bison是Yacc的一种实现，也是用来生成语法分析器的工具。它与Yacc的主要区别在于，Bison生成的语法分析器是可重入的，这使得它可以在多线程环境中使用。同时，Bison还提供了更多的功能和更好的错误报告。Bison的使用场景和作用与Yacc相同，都是用来进行语法分析。其工作原理也是通过BNF来描述语法规则，然后生成相应的C语言代码。

总结来说，这四个工具都是用来帮助我们生成编译器的重要组成部分——扫描器和语法分析器。其中，Lex和Flex主要用来生成扫描器，而Yacc和Bison主要用来生成语法分析器。这些工具都通过将词法或语法规则转化为C语言代码，从而实现了从源代码到目标代码的转换。
"

3.2
http://studyofnet.com/893594635.html
"
扫描器和解析器生成器

ebnf2y - 用于将 EBNF 语法转换为 yacc 兼容的骨架 .y 文件的实用程序。
flexgo - 可以生成 Go 代码的 flex 版本。
fsm - FSM（NFA，DFA）实用程序。
gocc - Go 编译器编译器
golex - Lex/flex 类快速（DFA）扫描仪生成器。
gopp - 去解析器解析器
goyacc -Goyacc 是生成 Go 解析器的 yacc 版本。
lexmachine - Golang词法分析框架
Ragel - 状态机编译器
y - 包 y 将 .y (yacc) 源文件转换为适合解析器生成器的数据。
yy - yacc 到 yacc 编译器。
"

4.分完词后一般就是生成语法树，现在流行的做法是生成 AST

在 lua/TL 中这是在源码的
parse_statements = function(ps, i, toplevel) --//clq 应该是在这里生成了具体的语法树
local node = new_node(ps.tokens, i, "statements")

它会在
function tl.parse(input, filename)
local tokens, errs = tl.lex(input, filename)
local node, required_modules = tl.parse_program(tokens, errs, filename) --//分词结果在这里生成 ast?
return node, errs, required_modules
end

中被调用。

流行的 js 版本可以看以下两篇文章

https://zhuanlan.zhihu.com/p/599311621?utm_id=0
"
ESLint是基于抽象语法树来进行工作的,ESLint默认使用的编译器(parse)是「Espree」,通过它来解析我们的JS代码生成AST,基于AST,我们就可以对我们的代码进行检查和修改了。
"
https://mp.weixin.qq.com/s/wYYDG7yU9h3-6DBYTCkuiA
"
import fs from 'fs';
import path from 'path';
import * as tsParser from '@typescript-eslint/parser';

const filePath = path.resolve('./src/test.ts')
const text = fs.readFileSync(filePath, "utf8")
// 编译成 AST 这里是不是和eslint的配置项对上了，没错就是透传而已
const ast = tsParser.parse(text,{
comment: true, // 创建包含所有注释的顶级注释数组
ecmaVersion: 6, // JS 版本
// // 指定其他语言功能，
// ecmaFeatures: {
// jsx: true, // 启用JSX解析
// globalReturn: true // 在全局范围内启用return（当sourceType为“commonjs”时自动设置为true）
// },
loc: true, // 将行/列位置信息附加到每个节点
range: true, // 将范围信息附加到每个节点
tokens: true // 创建包含所有标记的顶级标记数组
})
"

5.
"词法分析器 js 版本" 关键字下可以看以下几个篇小文章。都很短小，结合起来看倒是可以加深理解。
https://www.jb51.net/article/277655.htm
https://fiime.cn/blog/203656
还有一篇比较复杂的，可以扫一眼。
https://zhuanlan.zhihu.com/p/362075651

6.
生成 AST 理论上应该可以和解释器做在一起。
有了解释器其实就可以执行脚本了。
参考上面作者的同系列文章的示例
https://zhuanlan.zhihu.com/p/377521560

⭐7.重要！
龙书中提到的重要概念和没提到的重要概念

为了对比先说上我手头上的版本。《编译原理》机械工业出版社 2003 年版本，对应的龙书版本未知，不过译本中有原书的页码标识，这是比较好的。
（另外我觉得要自己实现编译器，或者学习编译器课程，一定不要把龙书作为主书目，而应当应它当成一本字典。当你对某些概念不明白或者不深入的时候再翻开龙书。直接学龙书就是一场灾难，因为它将几十年的人类智慧结晶直接告诉了你，没有说逐渐完善的过程。在短短有限时间内要掌握几十年的精华，结果可想而知。）

7.1 龙书中提到的重要概念

这些概念其实很重要，但在龙书中通常是在某个不起眼的地方提一嘴。

7.1.1
“后缀表示是语法树的线性化表示”。

工作很多年后我第一次想自己实现一个求值式子时我就知道要实现一个简单的编译器（实际上还不是），其实在学校学习时，在老师的作业中就实现过了。
当时的方法是后缀表达式算法。多年来我一直很疑惑，那么复杂的算法到底是谁想出来的，特别是那么多的堆栈算法，完全没有道理，我们只是机械的按书去实现而已一点不知道为什么那样做，更是不敢改。
所以在实现这个表达式时我就决心不用这么复杂的数据结构，要用最简单的线性数据直接完成。做了大概一星期吧，结论是简单 list 实现不了（除非当堆栈用），最后得到的最简单而又直观的方式是树形，而这在对应到当时的 delphi 的 treeview 时可以说一目了然!

多年来我一直认为这是一个大发现，我现在都认为当时之所以用堆栈是因为树形在当时还不方便实现造成的，估计是内存有限吧。当然了我知道这不正确，堆栈主要是可以在很简单的数据结构里实现树结构。所以一旦有什么算法用到了堆栈你又不理解的，
相信我，把它重新用树结构实现一遍你就明白了！

这一句说明见于第8章的第一页，“8.1 中间语言” 的一段说明中。中文 299 页，英文 463 页。

7.1.2
构造语法树时其实已经可以完成求值和语言的翻译了。原文说的是可以分离，那反过来就是说其实可以合在一起。
见于中文书 p189 英文 p285.

另外在背页还提到 “构造表达式的语法树类似于把表达式翻译成后缀表示”，所以说这也从一个侧面说明了两者的算法其实是一样的。

7.1.3
实现简单的翻译没必要构造语法树。
见于中文 p26 英文 p39 。 “2.3.6 翻译的输出” 小节。
不过我不太同意不用，因为用语法树真的好理解得多。

7.1.4
需要词法分析程序的原因。比如连续空白在语法分析时用 BNF 很难实现。这解决了我的一个疑惑，因为我确实发现不用词法分析也是可以的，而且我经常与语法分析写成同一个函数实现，没觉得有什么困难。
另外词法分析通常占好多的书内容，其实词法分析是个特别简单的程序。还要用什么程序去生成，至少对于小程序来说完全没有必要，lua 的一个有类型变体 TL 就没用，而且它还没用正则表达式，这可是实际的生成型语言。
中文书 p37 英文 p54 。

7.2 龙书中没提到的重要概念
有一些是我的经验，我也不确定的参考了一本德国人的 golang 实现 monkey 语言的书。以免我自己的说法误人子弟。

7.2.1
并不一定需要了解和使用 BNF 这样的工具。

7.2.2
并不一定需要正则表达式。
另外说一下，现在这版本的 TypeScript 在一些做得很好的 js 解析器，例如 otto 上无法正确运行的原因就是因为它大量使用了 js 原生才支持的正则表达式，而没有考虑通用性。

7.2.3
并不一定需要 yacc 这样的程序的生成程序。那本 go 的书也说到了，不过我是见到 lua/TL 版本这样实现后才确认实际工作中可以这样做的。
参考上面的 7.1.4 ，词法分析器就不一定需要生成器生成。

8.
https://github.com/search?q=interpreter&type=repositories
解释器的英文为 “interpreter” 所以用它作为关键字可以在 github 找到很多很好的资源。例如

https://github.com/lotabout/write-a-C-interpreter
这个有中文教程
https://lotabout.me/2015/write-a-C-interpreter-2/

https://github.com/NeilFraser/JS-Interpreter

8.1
https://lotabout.me/2015/write-a-C-interpreter-1/
很多文章都提到了用 bison
“
一般而言，编译器的编写分为 3 个步骤：

-1. 词法分析器，用于将字符串转化成内部的表示结构。
-2. 语法分析器，将词法分析得到的标记流（token）生成一棵语法树。
-3. 目标代码的生成，将语法树转化成目标代码。

已经有许多工具能帮助我们处理阶段1和2，如 flex 用于词法分析，bison 用于语法分析。
”
bison 命名就是 GNU Bison 。参考 https://www.oschina.net/p/bison?hmsr=aladdin1e1
“
GNU Bison 是一个通用的解析器生成器，它可以将注释的无上下文语法转换为使用 LALR (1) 解析表的确定性 LR 或广义 LR (GLR) 解析器。Bison 还可以生成 IELR (1) 或规范 LR (1) 解析表。一旦您熟练使用 Bison，您可以使用它开发广泛的语言解析器，从简单的桌面计算器中使用的解析器到复杂的编程语言。

Bison 与 Yacc 向上兼容：所有正确编写的 Yacc 语法都可以在 Bison 上正常使用。熟悉 Yacc 的任何人都应该可以轻松使用 Bison。您需要精通 C，C ++ 或 Java 编程才能使用 Bison。

Bison 及其生成的解析器是可移植的，它们不需要任何特定的编译器。
”

不过根据我的经验 gnu 的东西都很难用。可以看下它右边推荐的 langcc 。

8.2
https://www.oschina.net/p/langcc
https://zhuanlan.zhihu.com/p/571965728 [此文非常值得一读，它还推荐了一个从图片生成 3d 模型的工具 https://github.com/nv-tlabs/GET3D]
https://github.com/jzimmerman/langcc

“
langcc 是一个工具，它以标准 BNF 风格的格式获取语言的形式化描述，并自动生成一个编译器前端，包括语言的抽象语法树（AST）和遍历的数据结构定义、一个词典、一个解析器和一个 pretty-printer。

langcc 也是以下技术报告的配套软件实现，这些报告描述了对经典 LR 解析范式的若干创新：

Zimmerman, Joe. Practical LR Parser Generation. arXiv, 2022.
Zimmerman, Joe. langcc: A Next-Generation Compiler Compiler. arXiv, 2022.

langcc 可以用来替代 lex 和 yacc（或 flex 和 bison）的组合。但 langcc 提供了许多额外的功能，包括：

通过独立的数据类型编译器 ( datacc) 自动生成 AST 数据结构。
完整的 LR 解析器生成作为默认值，而不是更具限制性的 LALR。
通过明确的 “混淆输入对”，而不是不透明的移位 / 减少错误，清晰地呈现 LR 冲突。
LR 自动机的新效率优化。
LR 范式的扩展，包括递归下降 (RD) 解析操作，从而产生更小、更直观的自动机。
LR 范式的扩展，包括每个符号属性，这对于许多工业语言结构的有效实现至关重要。
LR 语法 (CPS) 的一般转换，显着扩展了该工具可以支持的语法类别。

与以前的编译器前端生成器不同，langcc 高效且通用，足以捕获完整的工业编程语言，包括 Python 3.9.12 ( grammars/py.lang ) 和 Golang 1.17.8 ( grammars/go.lang )。在这两种情况下，langcc 自动生成比每种语言的标准库解析器更快的解析器（分别快 1.2 倍和 4.3 倍）。事实上，langcc所支持的语法类足够通用，该工具是 self-hosting 的：即可以勇 “语言的语言” 本身中表达 “语言的语言”，并用于 langcc 生成自己的编译器 front-end。

更多细节可见源码库中 bootstrap.sh 和 grammars/meta.lang 文件。

langcc 是一个研究原型，尚未在生产中广泛使用。但开发团队表示，它本质上是稳定的且功能完整的，并且可以用作独立工具来促进对新编译器和编程语言的快速探索。
”

8.3
https://lotabout.me/2016/write-a-C-interpreter-8/
上文中的子篇 “手把手教你构建 C 语言编译器（8）- 表达式”。
主要推荐看其中的利用堆栈来计算表达式的方法。其实也就是语法树方法，因为我们说过了堆栈的现代表示就是树。

9.
不喜欢 c/c++ 或者嫌 langcc 安装太麻烦的话，可以看下面这篇 goyacc 的入门文章。
https://zhuanlan.zhihu.com/p/264367718

9.1
https://zhuanlan.zhihu.com/p/321360679?utm_id=0
TiDB源码学习笔记：Parser模块
goyacc 似乎是没有对应的分词工具的，此文中说 TiDB 的分词也是自己写的，然后再用 goyacc 。

10.
https://m.w3cschool.cn/article/44752392.html
这篇文章简短，但要素非常齐全，很值得一看。
“编译器开发”为关键字。

转帖了一份
http://newbt.net/ms/vdisk/show_bbs.php?id=7D24CA0E93EA10AA2D10D8D9038200F8&pid=160

11.
对于 javascript 这样的现有语言，直接写它的 BNF 与生成解析器是不太现实的。
可以考虑用 babel ，似乎支持不同的分析器。

或者使用 Esprima ，代码可以很简单。参考
https://zhuanlan.zhihu.com/p/634371655

“
首先，我们需要安装 Esprima，可以使用 npm 命令：

npm install esprima --save

然后，我们可以在 Node.js 环境中引入 Esprima，并使用它的 parseScript 或 parseModule 方法来解析 JavaScript 代码，例如：

var esprima = require('esprima');
var code = 'var a = 1 + 2;';
var ast = esprima.parseScript(code);

console.log(ast);

”
值得注意的是，Esprima 只支持 JavaScript，不支持 flow 或者 TypeScript 格式。
babel 是支持自定义分析器的，不过似乎比较难弄。

--------------------------------------------------------
原因如下，看下它的语法文件有多大就知道了。
https://www.coder.work/article/6696423

我正在开发 JavaScript 程序的合并工具，我需要在 JavaCC 中为 JavaScript(版本 >= ES6)编写语法格式。

为此，我想为 ES6 使用一个公开可用的 BNF 语法，然后我会用它以 JavaCC 格式编写语法。

我只能找到那些(来自 Stack Overflow question ):
http://tomcopeland.blogs.com/EcmaScript.html
http://www.ccs.neu.edu/home/dherman/javascript/

然而，这些都是非常古老的 BNF(而且 StackOverflow 上的问题也非常古老，从 11 年前开始)。这些语法仅适用于 - 并且以有限的方式 - 适用于 < ES6 的版本。

你知道一种较新的公开可用的语法(BNF、JavaCC 文件等)吗？

有可用于 ES6 的解析器，例如 Esprima , 但是，由于我必须使用 JavaCC 环境，我需要语法来处理。

最佳答案

完全认可的 ECMAScript 最新版本 (ES2017 = ES8) 位于 https://www.ecma-international.org/publications/standards/Ecma-262.htm

下一个版本(ES2018)的最新草案在https://github.com/tc39/ecma262 (源代码库)和https://tc39.github.io/ecma262/ (渲染)。

所有这些都是公开可用的，并包含该语言的语法。语法符号主要是带有一些扩展的 BNF。

--------------------------------------------------------

11.2
ESlint -- 这个 js 代码检查工具应该也是可以生成 AST 的。参考
https://zhuanlan.zhihu.com/p/184951182

这是篇很长的文章写得很好。

11.3 [tag: 表达式]
“纯手工实现一个「Javascript」版公式计算器”
https://zhuanlan.zhihu.com/p/362090014

11.4
https://cloud.tencent.com/developer/article/1561720
JavaScript 实现 JSON 解析器

12.
https://www.cnblogs.com/chenxx08/p/3913198.html
介绍了一个比较老的工具，不过用来学习肯定是没问题的。http://goldparser.org/

似乎 AntLR 和 yacc 常用。

12.2
https://zhuanlan.zhihu.com/p/483679676
"
一般如果语法非常复杂，会基于Lexer和Parser写到两个不同的文件中（例如Java，可参考：https://github.com/antlr/grammars-v4/tree/master/java/java8），如果语法比较简单，可以只写到一个文件中（例如Lua，可参考：https://github.com/antlr/grammars-v4/blob/master/lua/Lua.g4）。
"

--------------------------------------------------------
另外它应该是支持生成 c++、java、c# 等不同源码的。

https://zhuanlan.zhihu.com/p/25028169
"
首先确定好我们要做的事，开始写语法文件：
grammar SomeLanguage; // 声明语法头
/*
*========================
* 一些 options 配置
*=======================
*/
options {
language = Java; //设定生成代码的语言
}
"

12.3
https://zhuanlan.zhihu.com/p/347329881
"本文分享自华为云社区《Antlr4简明使用教程》，原文作者：maijun "
这是篇非常好的文章。改日转帖下。

12.4
https://blog.csdn.net/poised/article/details/51420478
"使用解析代码,high起来
利用命令行(请在cmd下操作)可以进行解析验证操作，不必写代码就能玩得转

java -jar antlr-4.5.3-complete.jar C.g4
--
antlr4.bat

java org.antlr.v4.Tool %*
----
grun.bat

java org.antlr.v4.runtime.misc.TestRig %*
--
org.antlr.v4.runtime.misc.TestRig是antlr4 runtime内置的测试工具，它可以查看解析的tokens和AST结构。
"

13.
JavaScript parser
常用的 JavaScript parser ，一般对解析器的术语就是 “parser”。所以可以用它用关键字来搜索相当资料。

https://www.cnblogs.com/mfoonirlee/p/7054939.html
acorn做语法解析，类似的还有babel使用的babylon
“
大家都知道，webpack是做模块绑定用的，那么就不得不牵涉到语法解析的内容，而且其极高的扩展性，也往往需要依赖于语法解析，而在webpack内部使用acorn做语法解析，类似的还有babel使用的babylon，今天就带来两者的简要分析。
　　官方给两者的定义都叫做JavaScript parser，内部也一致的使用了AST（Abstract syntax tree，即抽象语法树）的概念。如果对这个概念不明白的同学可以参考WIKIAST的解释
　　因为babylon引用了flow，eslint等一些checker，所以整个项目结构相当的规范
”

14.
"bnf 算术优先级" 关键字

说是按 bnf 很容易转换成实际代码。以下是三篇用 bnf 直接写出对应代码的文章。
https://www.cnblogs.com/pivotfuture/p/16297301.html
https://blog.csdn.net/dexter_morgan/article/details/41513723
https://blog.csdn.net/lanuage/article/details/129713560

最后一篇文章还有篇小代码 ...
https://github.com/aMonst/MMTCC

15.
通过上面的一大堆文章可以知道难点重点都在算术优先级，上文有依照语法文件做的多次嵌套循环的方式，我手头上的 go 的书的 TL 的应该是一样的，都是新的基于关键字的 “普拉特解析” 方式。
这个方法是龙书中没有的，所以高校的《编译原理》真的应该更新了，不过传统解析的方法还是很有意思，还是值得回头一看。改天我传几个常见的 c 语言文法文件上来。

“普拉特解析” 应该是不用按文法的。不过我仍然觉得太复杂，代码倒是很简单，比文法扩展的代码少很多，但理解起来太困难。有点象快速排序，我们都知道它有效，但它的作用机理那可难说。

我想有没有更容易理解的方法，又不用文法扩展那么啰嗦。搞了两周，我重写了一个。确实是可以实现的。原理也很简单，它们不是树嘛，跳过节点，把它们当树节点看就好了，如果单纯当语言看，那太难理解了。
改日我发文细说。

NEWBT官方QQ群1: 276678893
可求档连环画,漫画;询问文本处理大师等软件使用技巧;求档softhub软件下载及使用技巧.
但不可"开车",严禁国家敏感话题,不可求档涉及版权的文档软件.
验证问题说明申请入群原因即可.