解析器的实现

语法解析在制作编程语言过程中处于关键的起始步骤，不过相较于其他部分，其入门难度确实偏高。

简介

在多数情形下，解析器可划分为两个主要部分，也就是分词器与语法解析部分。分词器的作用是对代码进行分割，以便后续能更便利地解析代码，而像像 Python 这种将缩进作为语法组成部分的语言，分词器需要承担更多额外的工作任务。对于分词器的实现，既可以借助现成的工具来生成，比如 Flex，也可以通过手写一个状态机的方式来达成。语法分析环节会复杂得多，在学术领域，虽然普遍认为语法分析问题已得到解决，并且确实存在众多优秀的解析器生成器，但要想很好地运用这些工具，仍需对它们的底层原理有比较深入的理解才行。

快速入门

编程语言的语法能够通过一个非终结符的集合来描述。例如，最基础的加法运算可以相对不那么严谨地描述为规则 E -> E + T | T 以及 T -> 0 | ... | 9。更为学术性的解释可以参考上下文无关文法（CFG），是业界学界都常用的用于语法描述的方式。此处就不过多深入阐述了。在具体的算法实现方面，存在多种选择，例如自上而下的 LL 算法以及自下而上的 LR 算法，还有它们的各类变体。LL 算法实现起来相对简单，但有着较大的局限性；LR 算法则与之相反，功能更为强大但实现难度更高。在实际应用落地层面，有像 YACC/Bison 以及较为现代的 ANTLR4 这类工具，后者支持的编程语言种类较多，有兴趣的话可以自行深入学习，它们都属于非常成熟的技术了。

即便不采用这些成熟的技术，出于对高度定制化以及性能优化方面的考量，很多语言还是会选择手写一个递归下降解析器，例如 Rust 的解析器就是纯手写完成的，Felys 在早期也是如此。只不过手写这种解析器对于项目的结构设计要求颇高，很容易出现结构设计不合理的情况。

另外，还有一种相对较新的解析器思路，即解析表达式语法（PEG）及其变体 Packrat 解析器。这种解析器更像是一种功能强大的正则解析器，与传统解析器有所不同的是，Packrat 解析器支持无限回溯，并且它通过缓存机制，采用以空间换时间的策略来避免重复解析，最终能够达到线性时间复杂度，本质上就是动态规划的思路。其实际落地的代码与手写的递归下降解析器比较相似，但代码结构会更加清晰美观。不过需要注意的是，PEG 的语法注解方式和 CFG 是不一样的，主要差异在于 PEG 中规则是有顺序要求的，而在 CFG 规则顺序是无关紧要的。比如在 PEG 语法中，A -> B \ C 和 A -> C \ B，是不等价的，但在 CFG 里这两个表达式则是等价的。而追其根本的差异在于 PEG 描述的解析过程，但 CFG 描述的是语言。Packrat 解析器在实际应用中不算广泛，主要是由于其性能表现欠佳，尤其是在内存占用方面，据了解，目前只有 Python 有使用到它。更多的细节内容可以参考原论文。

INFO

PEG 语法中使用 \ 而不是 | 来强调顺序的重要性，以此与传统语法描述方式形成区别。

技术选型

最终决定选用 Packrat 解析器，主要原因如下：Python 在早几年已经将原本的 LL 解析器替换成了 PEG 解析器，而且从实际情况来看，性能方面并没有出现明显的差异，同时可维护性却得到了极大的提升。再者，考虑到 Packrat 解析器实现起来较为直观、简单，并且 Python 是现成的案例可供参考，还有 Guido 的相关教学博客能够辅助学习。而对于其他传统的解析器生成器，我只了解皮毛，它们的学习曲线同样比较陡峭，并且各自都存在一定程度的局限性。综合多方面因素考虑，最终决定自己手写一个 Packrat 解析器。

语法设计

这个语法文件单纯是用来表达语法的，并不能丢给哪个解析器生成器来生成。有些非终结符我这里没写出来，因为代码实现的时候直接调用 Rust 的内置函数。此外，有些细节和实际的实现略有不同或者简化，有需求直接参考源代码。

入口语法

program -> stmt* eof

语句语法

stmt -> \
    \ expr ';'
    \ expr
    \ ';'

block -> '{' stmt* '}'

模版语法

pat -> \
    \ '_'
    \ ident
    \ '(' ','.pat+ ')'
    \ lit

ident -> (alphabetic \ "_") (alphanumeric \ "_")*

表达式语法

expr -> \
    \ assign
    \ tuple
    \ block
    \ "break" expr?
    \ "continue"
    \ "for" pat "in" expr block
    \ "match" expr '{' ','.(pat '=>' expr)+ '}'
    \ "if" block ("else" expr)?
    \ "loop" block
    \ "return" expr?
    \ "while" expr block

assign -> \
    \ pat '=' expr
    \ pat '+=' expr
    \ pat '-=' expr
    \ pat '*=' expr
    \ pat '/=' expr
    \ pat '%=' expr

tuple -> \
    \ '(' ','.expr+ ')'
    \ disjunction

disjunction -> \
    \ disjunction "or" conjunction
    \ conjunction

conjunction -> \
    \ conjunction "and" inversion
    \ inversion

inversion -> \
    \ "not" inversion
    \ equality

equality -> \
    \ equality '==' comparison
    \ equality '!=' comparison
    \ comparison

comparison -> \
    \ comparison '>' term
    \ comparison '>=' term
    \ comparison '<' term
    \ comparison '<=' term
    \ term

term -> \
    \ term '+' factor
    \ term '-' factor
    \ factor

factor -> \
    \ factor '*' unary
    \ factor '/' unary
    \ factor '%' unary
    \ unary

unary -> \
    \ '+' unary
    \ '-' unary
    \ primary

primary -> \
    \ lit
    \ ident
    \ '(' expr ')'
    \ '|' ','.ident* '|' expr

字面量语法

lit -> \
    \ float
    \ int
    \ str
    \ bool

float -> \
    \ '0' '.' digit+
    \ digit+ '.' digit+

int -> \
    \ '0x' hex+
    \ '0o' oct+
    \ '0b' bin+
    \ '0' !digit
    \ digit+

bool -> \
    \ "true"
    \ "false"

str -> '"' (!'"' char)* '"'

经验分享

编程语言本身实则也是一种产品，用户体验至关重要。正因如此，绝大多数流行的编程语言都会引入大量的语法糖并允许副作用，借此简化重复性工作，提升代码可读性，但这也会破坏语言在学术方面的严谨性。像 Python 就是极致易用的代表，而 Haskell 则有着绝对的学术严谨性，所以 Haskell 在学术研究中被大量运用，但在业界的使用量并不算多。总之，在两者之中找到平衡才是关键。

在设计编程语言时，开发者很容易不自觉地朝着函数范式靠拢，因为从代码实现角度来看，这样做就是很合理，但必然会牺牲诸多便利性。例如，比如最简单的变量赋值，由于需要在后端存储变量内容，所以同样会产生副作用，而函数式语言中因不允许重复赋值，才能实现无需后端存储的效果；再或者说绝大多数语言都具备的打印函数，会自动和系统交互输出，但在函数范式里，和系统交互的接口必须手动传入才行。

就个人观点而言，Go 和 Rust 等语言在权衡方面做得比较好，整体风格偏向函数式，同时也提供了不少语法来实现更高层次的抽象，无需像 C 语言那样把各类信息全都塞在函数名当中，进而避免了代码可读性欠佳的问题。不过就单单日常实用性而言，我应该还是会毫不犹豫的选择 Python，毕竟平时写个脚本之类的逻辑严谨性并不这么重要。