扫描器是词法分析器，它接收输入的源程序，对源程序进行词法分析并识别出一个个单词符号，输出单词符号。

上下文无关语言

表示上下文无关文法规则的形式被称为BNF，其扩展表示就是EBNF。

在BNF中，重复是使用递归表示的，重复实际分两种：嵌套重复和并列重复，并列重复对应到程序是可以用循环来实现的。

EBNF

重复表示{…}

下面两种重复的递归形式表达的就是并列重复：

$A\rightarrow A \alpha|\beta$

$A\rightarrow \alpha A |\beta$

其中第一条中要求$\beta$ 不能以A开头， 而第二条中要求$\beta$不能以A结尾。对应的正则表达式为：$\beta \alpha^$和$\alpha^\beta$
EBNF中使用{…}来表示这种重复：
$A\rightarrow \beta {\alpha}$

$A\rightarrow{\alpha} \beta$

可选表示[…] 有点类似消除左因子。

语句序列：
$stmt-sequence \rightarrow stmt; stmt-sequence | stmt$
可以表示为：
$stmt-sequence \rightarrow stmt [ ; stmt-sequence ]$
$stmt-sequence \rightarrow stmt { ; stmt } $

消除左递归

直接简单左递归

$A\rightarrow A \alpha |\beta$

改写文法为：

$A\rightarrow \beta A’$

$A’\rightarrow \alpha A’ |\epsilon$

间接左递归

会出现$A\Rightarrow^*A$的左递归。

处理方法：

将文法的所有非终结符按任意一种顺序排序，得到$A_1,A_2…A_n$

对每个$A_i$，如果存在一个编号比它小的非终结符，编号大的非终结符可以含有推出编号小的非终结符的句型，而且编号小的非终结符还能够推出一个句型，那么就可以进行代入操作。
如果有直接左递归，那么直接消除即可。

$S\rightarrow Qc|c$

$Q\rightarrow Rb|b$

$R\rightarrow Sa|a$

1) 对S、Q、R编号1、2、3

2）i=1，无法代入，i=2，无法代入

i=3, 代入有 $R\rightarrow Qca|ca|a$,可再次代入：$R\rightarrow Rbca|bca|ca|a$

3)化简直接左递归：

$R\rightarrow bcaR’|caR’|aR’$

$R\rightarrow bcaR’|\epsilon$

消除左公因子

对每个非终结符A，找出它的两个或多个选项之间的最长公共前缀$\alpha$,如果$\alpha$不为空，即存在一个非平凡的公共前缀，那么将所有A的产生式$A\rightarrow \alpha\beta_1|\alpha\beta_2|…\alpha\beta_n|\gamma$,

替换为：

$A\rightarrow \alpha A’|\gamma$

$A’\rightarrow \beta_1|\beta_2|…|\beta_n$

递归构造上下文无关文法

左递归：左侧非终结符出现在右侧第一个位置。
$A\rightarrow A a | a$
右递归：左侧非终结符出现在右侧最后一个位置
$A \rightarrow a A | a$

表示$\alpha\beta^*\gamma$一样的语言：

1）$A\rightarrow B\gamma$ ,$B\rightarrow B\beta|\alpha$

2) $A\rightarrow \alpha B$ ,$B\rightarrow \beta B|\gamma$

3)$A\rightarrow\alpha B\gamma$,$B\rightarrow\beta B| \epsilon$

所有的正则语言都能被上下文无关文法表示。