门 III · 语言与编译PW-0006 · r1
语法分析器Parser
把词法单元流组织成语法树的组件。递归下降、LL 与 LR 是三种主要的构造方法。
核糖体读取信使 RNA — 核糖体沿一条线性的 RNA 逐个读取三联密码，按规则把氨基酸接成链，链再折叠成有层次的结构。语法分析器同样逐个读入线性的记号，按文法把它们组装成一棵语法树。
语法分析器读入词法单元流，依照上下文无关文法构造语法树，或报告语法错误。
A parser reads a stream of tokens and builds a syntax tree according to a context-free grammar — or reports a syntax error.
递归下降Recursive descent
为每个非终结符写一个函数，函数体照着产生式调用其他函数。手写方便、报错友好，是许多生产编译器的选择。
Write one function per nonterminal whose body calls the others exactly as the productions say. It is easy to write by hand and gives good error messages, which is why many production compilers use it.
// expr := term (("+" | "-") term)*
function expr(): Node {
let left = term();
while (peek() === "+" || peek() === "-") {
const op = next();
left = { op, left, right: term() };
}
return left;
}
LL 与 LRLL and LR
LL 分析器自顶向下、从左到右推导，向前看 个符号决定用哪条产生式；LR 分析器自底向上，把输入移进栈中，在栈顶匹配到产生式右部时归约。LR 能处理的文法更多，通常由工具生成。
