编译器

http://lisperator.net/pltut/

https://github.com/jamiebuilds/the-super-tiny-compiler

vocabulary symbol 词汇符号: 最小单元
interpreter 解释器: 分析/执行语句
translator 翻译器: 将语言翻译成另一个语言

用于遍历整棵树的访问者模式, 该模式通常是为了就地修改特定类型的节点.

如果对节点的修改会改变树的结构, 则需要明确向树的遍历器传达以下信号之一:

  • EXIT: 停止树的遍历(罕见, 因为通常不会只修改一处节点)
  • CONTINUE: 继续遍历(假装没修改树的结构)
  • SKIP: 停止继续遍历此节点的后续节点(当前节点被删除, 或子节点列表被替换)

一种从旧树生成出一颗新树的函数.

通常伴随着各种函数式实用函数:

  • map
  • flatMap
  • filter

测试节点是否是我们想要的节点, 通常可以以节点的属性, 类型, 父节点作为测试条件.

递归下降解析意味着解析程序通过递归实现了自上而下的解析, 函数会递归调用其他函数以完成各自的解析任务.

递归下降解析模式被广泛用于编译器的各种部分, 最有名的是递归下降语法解析器, 这是将token解析为AST的最简单方式.

基于Earley算法的解析器生成器, 具有自己的文件格式, 该文件格式内可以嵌入JavaScript函数.

是npm下载量最大的解析器生成器.

解析器生成器, 具有自己的文件格式.
在业内享有声誉.
强烈建议配合官方书籍《ANTLR4权威指南》来使用.

性能一般, 但在JavaScript里已经是Chevrontain以外性能最高的方式了.

ANTLR4有一个可以生成TypeScript代码的实验性模块antlr4ts.
该模块的开发似乎已经停滞, 且文档跟不上实际版本.

lexer grammar NAME; 开头的文件是词法规则.
grammar NAME; 开头的文件是语法规则, 语法规则里可以包含词法规则, 语法规则通常写在词法规则之前.

词法规则必须首字母大写.
语法规则必须首字母小写.

import Name; 导入词法规则.

mode NAME; 进入新的词法分析模式, 此行以下的内容归属于该模式.
-> mode(NAME) 按规则切换到特定模式.
还可以用 -> pushMode(NAME) 以栈的形式进入特定模式, 用 -> popMode 退出模式.

fragment 用于声明之后的内容只是一种可以被词法规则使用的片段, 而不是单独的词法符号.
该片段只能被词法规则使用, 对语法规则不可见.

ANTLR4的规则隐式包含从上到下, 从左到右匹配的优先级.
由于词法分析过程早于语法分析执行, 词法分析中出现的歧义项目会优先选择匹配结果最长的规则,
因此 所有规则都应该优先围绕着词法分析来设计.

<assoc=right=> 写在规则正文的最左侧, 表示该规则是右结合的
('a'...'z'|'A'... 'Z') 等价于正则表达式中的 [a-zA-Z], ANTLR4也支持直接用正则表达式中的此模式.
(...) 子规则
(... | ... | ...) 有一个或多个备选分支的子规则
x? 可选
x* 零次或多次
x+ 至少1次
. 通配符
.*? 非贪婪匹配所有字符, 通常用于匹配字符串词法规则.
~x 匹配除x之外的字符
[abc] 匹配字符a 或 b 或 c
'text' 字符串常量

在不嵌入特定于编程语言的谓语的情况下, ANTLR4不能支持对行首的匹配.

一种替代方法是将换行符作为行首的标识符使用,
这种做法的缺点在于无法匹配位于文件头的行首标识符, 此外也扭曲了标识符本来的语义.

如果语言本身构建在大量与行首有关的规则之上, 则更合理的做法是使用 (statements NEWLINE)* 这样的模式,
如此一来就不需要匹配行首.

参考: https://stackoverflow.com/questions/31903723/how-to-detect-beginning-of-line-or-the-name-getcharpositioninline-does-not/31910284

词法分析器的一种特性, 允许在一种语言里混杂多种不同的语法, 例如在HTML里混杂JavaScript和CSS.

ANTLR4生成的类有不同的用途.

  • 访问者(Visitor): 编写特定名称的方法来覆盖特定语法的处理函数, 可以被用来创建语言解释器.
  • 监听者(Listener): 监听事件, 在回调函数中执行一些副作用, 无法干涉语法的处理过程.
  • 词法符号流重写器(TokenStreamRewriter):
    用来改变从语法树转换为文本时的行为(插桩, 常见于覆盖率测试和单元测试框架),
    重写器主要与监听者配合使用.
HTML_STRING: '<' (TAG|~[<>])* '>' ;
fragment TAG: '<' .*? '>' ;
OPEN: '<' -> mode(ISLAND) ; // 匹配到<就进入ISLAND模式
TEXT: ~'<'+ ;
mode ISLAND;
CLOSE: '>' -> mode(DEFAULT_MODE); // 匹配到>就切换回默认模式
SLASH: '/'
ID : [a-zA-Z]+ ;
COMMENT: '<!--' .*? '-->' -> skip ;
CDATA: '<![CDATA[' .*? ']]>' ;
TAG: '<' .*? '>' ;
ENTITY: '&' .*? ';' ;
TEXT: ~[<&]+ ;
STRING: '"' (ESC|.)*? '"' ;
fragment ESC: '\\"' | '\\\\' ; // 转义\"和\\
LINE_COMMENT: '//' .*? '\r'? '\n' -> skip ;
COMMENT : '/*' .*? '*/' -> skip ;
grammar Expr;
prog: stat+ ; // 一条或多条语句
stat: expr NEWLINE # printExpr // 求值
| ID '=' expr NEWLINE # assign // 赋值表达式
| NEWLINE # blank // 单纯的换行符
;
expr: expr op=('*' | '/') expr # MulDiv // 乘/除运算
| expr op=('+' | '-') expr # AddSub // 加/减运算
| INT // 整数
| ID // 标识符
| '(' expr ')' // 带有括号的表达式
;
MUL : '*' ;
DIV : '/' ;
ADD : '+' ;
SUB : '-' ;
ID : [a-zA-Z]+ ; // 标识符
INT : [0-9]+ ; // 整数
NEWLINE: '\r'? '\n' ; // 换行符
WS : [ \t]+ -> skip ; // 丢弃空白字符, skip是为此设计的一种内建的词法分析模式

op=() 是可选的, 目的是给运算符一个人类可读的名称, 即op, 在生成的解析器里会作为上下文属性出现.
# 是可选的, 目的是给规则加上人类可读的标签, 在生成的解析器里, 标签名会作为访问者模式的方法名出现.

解析器生成器, 具有自己的文件格式.

性能极差.

缺乏维护: https://github.com/pegjs/pegjs/issues/639

PEG.js的主要fork.

解析器组合器使用软件工程方法创建基于编程语言的DSL, 而不是基于文本的DSL.
通过解析器组合器创建的解析器更模块化, 易于进行单元测试,
因此通常要比通过解析器生成器创建的解析器要容易维护.

用来解析语言时可读性不高, 但很适合用来解析正则表达式无法处理的小段文本.

性能一般.

一种解析器构建工具包, 它的功能是以JavaScript语言描述类似CFG或PEG的DSL, 具有较好的可读性.

根据benchmark, 它是JavaScript里性能最好的解析器, 远远甩开其他的库, 甚至好于手写的解析器.
然而, 在fast-toml包的benchmark中, 使用Chevrontain编写的TOML解析器Bombadil是最慢的解析器.

  • 尽管是用TypeScript编写的, 但对TypeScript支持得很差.
  • 相比解析器生成器, 需要手动编写大量代码.
  • 该项目是作者的业余项目, bug不会及时修复, 具有很高的巴士因子.

https://github.com/bd82/regexp-to-ast/issues/118
https://github.com/Chevrotain/chevrotain/issues/1670

这使得Chevrontain无法使用 [\S^xxx] 模式, 也无法将Unicode字符视作token.
对于任何需要支持多语言标识符的项目来说, 这都是一项很大的缺陷.

https://github.com/Chevrotain/chevrotain/discussions/1536#discussioncomment-851016

尽管支持正则表达式, 但Chevrontain的Lexer和一般的解析器生成器语言一样, 无法处理以下情况:

  • 带有 ^$ 的Token模式.
    因此, Chevrontain里不能创建与一行开始或结束有关的关键字.
    为处理此情况, 只能解析换行符, 然后在解析器里完成相关的匹配.
    在这一点上, Chevrontain并不如ANTLR4这样的解析器DSL有可读性.

一个由Chevrontain编写的解析器按执行顺序分为3个部分:

  1. 1.
    Lexer: 实现tokenization, 将文本转换成token.
  2. 2.
    CST Parser: 实现parsing, 将token转换成CST(具体语法树, 是AST的前一级)
    CST与AST的不同点:
    • CST包含详细的语法信息, 而这些信息对AST来说可能是不需要的.
    • 可以从CST重建出一模一样的原始文本, 但不能从AST重建出来.
    • AST往往会对CST进行结构上的变换, 以便更好地使用.
  3. 4.
    Interpreter: 将CST转换为AST, 供外部程序使用.
    有两种实现方式:
    • 编写CST的递归下降解析器.
    • 使用Chevrontain提供的访问者类(BaseCstVisitor).
    • 编写内嵌版本的CST Parser, 这允许最大的自定义, 但代码很难阅读和维护.

PEG总是会在出现歧义时选择第一个匹配项, 因此PEG只会生成一棵AST.
CFG在出现歧义时, 选择的结果是不确定的, 因此CFG可能会生成多棵AST.
总是应该优先使用PEG.

词法分析(lexical analysis, lexing 或 tokenizing):
词法分析器(lexer)去除源代码(一串连续的长字符串)里的空白字符,
将词法单元提取出来生成token(标识, 源代码的最小单位),
该过程称作tokenization.

sum = 3 + 2; 为例
词法分析之后, 得到
sum: 标识符, identifier
=: 操作符, operator
3: 字面量, literal
+: 操作符, operator
2: 字面量, literal
;: 分隔符, separator

此外, 还有keyword关键字(if, while, return), 注释(comment)等token类型.

词法分析通常是上下文无关的或接近上下文无关的, 分析过程通常不需要向前回溯词法单元.

词法分析器通常由词法分析器生成器生成, 且与语法分析器配对使用.

当出现歧义时, 词法分析器通常会采取以下行动中的一种:

  • 使用第一个成功匹配的规则.
  • 使用匹配到的字符串最长的规则.

最常见的歧义是语法关键字可以被当作标识符的情况:
class是一个关键字, 由于词法分析是逐字进行的, 会将classmate这个标识符拆分成class和mate完成匹配,
而这仅仅因为这个标识符是以class开头的.

token需要标识自己的类型(type)和携带与之相关的信息(value).
token可能会带有元信息(例如该token起始和结束位置的行号, 列号, 位于字符串的位置等).

常见的手写形式是构建一个读取字符的字符输入流, 然后用if语句配合正则表达式对字符进行转换.

在匹配过程中会经常出现需要临时向后获取更多字符的情况,
例如需要匹配由多个字符组成的关键字, 字符串类型或连续的数字.

分析器的组件有一些约定俗成的函数命名方式:

  • 偷看, 预读 peek() 读取一个字符, 但不会将它从流中删除.
  • 吞噬 next()或eat() 读取掉一个字符, 将它从流中删除.
    该函数也可能支持一个整数参数, 以便一次吞噬掉多个字符.
  • 文件尾 eof() 在流没有值的情况下返回true.
  • croak(msg) 出现错误, 抛出异常.

从字符输入流解析:

function readNext() {
readWhile(isWhitespace)
if (input.eof()) return null
const ch = input.peek()
if (ch === '#') {
skipComment()
return readNext()
}
if (ch === '"') return readString()
if (isDigit(ch)) return readNumber()
if (isIdStart(ch)) return readIdent()
if (isPunc(ch)) {
return {
type: 'punc'
, value: input.next()
}
}
if (isOpChar(ch)) {
return {
type: 'op'
, value: read_while(isOpChar)
}
}
input.croak("Can't handle character: " + ch)
}

在词法分析之后, 是语法分析(parsing, syntax analysis 或 syntactic analysis).

语法分析器称作parser或syntax analyzer, 其作用是构建出表述语法的数据结构, 例如抽象语法树(AST).

一些语法分析器不需要词法分析阶段, 因为它们直接把字符作为token使用,
这被称为无扫描的语法分析器(scannerless parser).

语法分析通常需要回溯之前的词法单元以决定一组token应该构建出怎样的语法树.
回溯有两种实现方法:

  • 在发现构造有误时, 撤销回先前的状态, 尝试下一种构造.
  • 预读之后的词法单元, 以决定构造的类型.

正则表达式只能解析 常规语言,
无法表述具有成对无限嵌套的模式(例如编程语言中嵌套的成对括号, 具有这种模式的语言被称为 非常规语言),
其根本原因在于正则表达式是一种有限状态机, 只能处理有限状态.

因此, 语法解析通常使用BNF这种支持递归定义的语法来描述语法结构, 生成解析器.

如果手动编写语法解析器, 则会多次用到递归来处理无限嵌套的模式.
例如当语法解析器先遇到了一个 ( 的token, 在未遇到 ) 之前又再次遇到了一个 (
(即该表达式内有两层或更多的成对括号), 解析函数将直接递归调用自己, 以处理下一组括号.
我们把递归函数视作一种只处理当前局面的函数, 它不在乎之自己是否是被谁调用的, 也不关心递归调用有多深,
只关心它自己眼前这一阶段的事情.

AST(抽象语法树)采用DFS(深度优先搜索)进行遍历.
在遍历AST时, 会使用访问者模式(visitor pattern)分离遍历代码和处理代码.

function traverser(ast, visitor) {}
const visitor = {
NumberLiteral(node, parent) {}
, CallExpression(node, parent) {}
}
  • skipSomething 跳过某种类型的token, 让i值自增
  • eatSomething 期望当前token为某种类型, 让i值自增, 如果不是则报错
  • parseSomething 期望某种类型的语法结构, 这个函数通常还会包含更多skipSomething和eatSomething.