/tmp/duangsuse.sock

解析组合子是什么？
下面会简单科普一下 LL(1)、LR(1)、LALR 和一般手写的递归下降(recursive descent)解析器的一些知识（

每次看到很多各种各样的线性数据结构，比如说，字符串
不管是采用怎样的字符集、怎样的编码，字符串都是一堆可以判断相等性的『字符』组成的『序列』
那么，如果为了方便，想从这个序列里提取出一些结构（比如从 "$a . $b" 里提取 [dollar a, '.', dollar b]）
就需要一种依据序列进行语法树推导的算法
一般被称作解析算法

LL(1) 的第一个 L 是 "Left to right"，指这是个解析器 Left-To-Right 从左到右扫描输入序列
LL(1) 的第二个 L 是 "Leftmost derivation"，LL(1) 是自顶向下构造提出数据（推导）的
LL(1) 的这个 (1) 代表任何时候，LL(1) 只需向前阅读一个项目，即可决定解析流程走向了（终结符 terminal 推导预判）
LL 解析器一般用的是显式的栈(stack) 而非递归下降法的机器栈（语言提供的调用栈）

LR(1) 的第二条则正好相反，它不是自顶向下收束，而是自底向上规约（大概吧... Parser 和 grammar 的关系还是蛮大的，LR 的 back-substraction 是什么鬼，我怎么感觉这些自动机有点重造编程语言执行者的嫌疑...

LALR 我听过《Ruby 原理剖析》说是“Look-Ahead Left Rightmost derivation”

以上都可能很不准确，中国国内能找到很少的资料（恐怕大部分都还是转发...）而且我懒得看资料（因为我又不是专门学面向解析器的编译原理的.... 或者 NLP 什么的）

总之我不是特别喜欢这类自动机... 看起来虽然优化明显一些，但是它们也是只能一个字符一个字符的推导... SIMD 扫描字符串可能都没有。而且很多 parser compiler 生成出的程序还贼大... 对手动优化也不友好的

不过这里要讲的是一般的手写递归下降法解析器
即使很多语言官方都是在用 Lex/Yacc style 的 parser combinator (比如 PHP 就是 re2c、GCC C 前端之前也应该用过自动生成的解析器）

这个递归下降呢... 思路很简单，就是利用所用编程语言自有的结构，比如判断、循环、递归，来扫描目标输入
自动机的状态，是由这门编程语言的控制流转换图构成的

比如扫描一个简单的数字（类似 130, 229 这种 /(\d+)/）：

#include <stdio.h>
#include <ctype.h>

#define PARSER int ch;
#define GETC (ch = getchar())
unsigned int readUnsigned() {
  PARSER
  unsigned readn = 0;
  while (isdigit(GETC)) { readn*=10; readn+=(ch -'0'); }
}

就是用这个 while，那这个实际上有一点问题，就是不能保证（实际上是 /d*/），其实 int ch; 可以提升到全局作用域，这样在函数入口处就可以检查下（是不是 isdigit，会不会至少循环一次）语法正确与否了

跑题了... 不过的确是有『工业级』语言使用手写的递归下降解析器的，比如 Lua

这个 fp.js 的解析器呢... 一般会把输入看成是流，最好还能 mark/reset，这样就能轻而易举地实现（多） branch

不过目前看来，虽然（intoIter 从 array-like 转化的） iterator 是可以随便 tell/seek 的，但是没有 API 来 reset。
不过 LookAhead-1 还是可以实现的。方法就是预取 — 利用 lookAhead1 函数得到的流，有一个 next 属性可以窥视到下一个项目，这样可以实现需要预判的语法

Python 的缩进语义需不需要预判呢？其实缩进语义本身是有点 Non-Context free 的，毕竟你没法写出一种刻板的描述，
一个 ':' 会开启新 layout（语法布局，就是缩进层次），可是 CFG 可以有 sequence 和 branch，但它没法有 context — 算不出来下一层布局是多少个空格开头什么的，也就是 Non-CFG 的了（当然，这种情况可以先扫描一遍转化 layout 语法为 CFG 语法（添加 <begin> 和 <end> 之类的隐藏关键字什么的），这样就依然可以扫描

Python 的列表 List comprehension LL(1) 能不能实现呢？

先来看看例子：里面 '' 包裹的是文本，[] 包裹的是可选内容、<> 包裹的也是文本、{} 包裹是重复 0-n、{{}} 是 1-n
大写的是非终结符（可以被替换为终结符序列），小写的是终结符。

List = '[' Items ']'
Items = Expr {',' Expr}
[1,2,3,4] #valid
[0] #valid

ListComp = Expr <for> ident <in> Expr [ <if> Expr ]
Items |= ListComp

[x for x in xs] #valid
[sin(x) for x in xs if x < 10] #valid

那这是不是 LL(1) 可以推导的呢？Left, Leftmost derivation, LookAhead(1)
首先重写一下式子

List = '[' Expr {',' Expr}
  | Expr <for> ident <in> Expr
  | Expr <for> ident <in> Expr <if> Expr
']'

我们看看，是不是靠着 LookAhead1 就可以判断解决所有的 | 分支呢？这关系到解析器状态的转换 🤔

首先咱收束个 Expr，然后怎么办呢？从字符组织，不得不看看字符的情况了
当然这里是不可能的，不过还是可以做到。下一项的可能性：
1.

{',' Expr}

看 ',' 即可
2,3. 都是 <for> 这就混了（

  | Expr <for> ident <in> Expr
  | Expr <for> ident <in> Expr * <if> Expr
']'

不过两边左的文法都是一致的，所以找一下最右边的情况 (*)
这个时候也是可以通过预取 1 推导的：为什么？判断是 <if> | ']' 即可

所以 Python 的这个语法也是 LL(1) 兼容的

12 viewsedited 08:22