[Compiler 笔记 (2)]：一些名词

本文是 Crafting a compiler ch4: Parsers and Recognizers 的笔记。

建议读者：对于 CFG, terminal, nonterminal, production 有一些认识的人，以及正在看本书第四章的人。
本文目标：说明一些我个人对于一些词的理解如 terminal alphabet, nonterminal alphabet, start symbol, vocabulary, derivation, sentential form, phrase, handle, regular grammar, BNF, recongnizer, LL parser, LR parser, set, list, iterator, first set, follow set, 我并不会注重在这些词的定义，而是注重在我个人的解释。

G = (N, Σ, P, S)

一个 grammer 可以表示为 G = (N, Σ, P, S), 其中

G (grammer)：代表语法N 代表 non terminalΣ 代表 terminalp 代表 productionS 代表 start symbolderivate: 使用了一个 production(rewriting rule)L(G): 实际上所有可能的程式码的集合

一些取名惯例：

大写开头：nonterminal

小写开头或标点符号：terminal

X, Y 开头：terminal 以及 nonterminal 的集合

希腊字母：数个 terminal 以及 nonterminal, 但不一定可以从 start symbol derivate 而来

sentential form：可以想成是从 S(start symbol) derivate 到一半的 string

leftmost derivation: 从最左边的 nonterminal 开始 derivation

rightmost derivation(canonical derivation): 从最右边的 nonterminal 开始 derivation

Backus-Naur form(BNF)：多加了一些功能的 CFG，以一个 production 为例子：
Declaration → [ final ] [ static ] [ const ] Type identifier { , identifier }
中括号内的可有可无，大括号内的可以重複数次。

First( α) = { a ∈ Σ | α ⇒* a β }
Follow( A ) = { b ∈ Σ | S ⇒+ α A b β }