编译原理

词法分析

1. 什么是形式语言？

   人们把用一组数学符号和规则来描述语言的方式称为形式描述；

   把所用的数学符号和规则称为形式语言。

2. 说明词法分析器的作用？

   主要任务：读入输入字符，将它们组成词素，生成并输出词法单元序列，提供给语法分析使用。

   辅助任务：

   1. 过滤注释和空白；
   2. 将各阶段发现的错误与源程序位置联系起来；

3. 划分词法分析和语法分析的原因？

   1. 简化编译器的设计；
   2. 提高编译器的效率；
   3. 增强编译器的可移植性；

4. 什么是词法单元、模式、词素？

   1. 词法单元由一个词法名和一个可选的属性值组成；
   2. 模式描述一个词法单元的词素可能具有的形式；
   3. 词素是源程序中的一个字符序列；

5. 串和语言的相关概念

   1. 字母表：符号的有限集合；
   2. 串：字母表中符号的有穷序列；
   3. 串的长度：出现在串中的符号个数；
   4. 语言：字母表上的一个串集合；
   5. 句子：属于语言的串；

6. 串的运算

   1. 连接：串是同一字母表，直接拼接；
   2. 积：串与自身的n-1次连接；

7. 语言的运算

   1. 和：$L∪M = {s | s∈L 或 s ∈M}$
   2. 连接（积）：$LM = {st | s∈L 且 s ∈M}$
   3. 指数：$L^0$是${\epsilon}$，$L^i$是$L^{i-1}L$
   4. 闭包：$L^*=L^0 \cup L^1 \cup L^2 \cup …$
   5. 正闭包：$L^+=L^*-{\epsilon}=L^1 \cup L^2 \cup …$

8. 正则表达式

   用于匹配一系列符合某种规则的字符串，它表示的语言叫做正规集合。

   1. $(r)|(s)$是正则表达式，表示$L(r) \cup L(s)$
   2. $(r)(s)$是正则表达式，表示$L(r)L(s)$
   3. $(r)^$是正则表达式，表示语言$(L(r))^$
   4. 约定如下：
      1. 闭包运算（算符*）具有最高的优先级，并且是左结合。特别地，具有幂等性；
      2. 连接的优先级次之，也是左结合；
      3. 或运算的优先级最低，同样是左结合

9. 正则定义

   对正则表达式命名，并用这些名字定义正则表达式。

10. 正则表达式的扩展

    1. +表示正闭包
    2. ? 表示零个或一个出现 $r|\epsilon$
    3. 字符类缩写$[a_1a_2..a_n]$或$[a-z]$

11. 状态转换图

    用于识别或接受一定的字符串。

    *代表最后一个字符不属于字符串，输入需要回退一个位置。

    有关超前搜索，特别地，

    1. 所有基本字都是保留字，用户不能用它们作自己的标识符；
    2. 基本字作为特殊的标识符来处理，使用保留字表；
    3. 基本字、标识符和常数直接没有确定的运算符或界符，则必须使用一个空白符作间隔；

12. 有穷自动机

    1. 有穷自动机是识别器，能对输入串回答“是”或“否”；

    2. 分类：

       1. 不确定的有穷自动机 NFA
       2. 确定的有穷自动机 DFA

       NFA与DFA能够识别的语言集合相同。

13. 不确定的有穷自动机

    与状态转换图的区别：

    1. 同一个字符可以标记同一个起始状态到多个目标状态的转换；
    2. 边不仅可以是输入字母表中的符号，也可以是空符号串

语法分析

1. 什么是文法？什么是上下文无关文法？

   描述语言的语法结构的形式规则称为文法。

   四元组$G=(V_T,V_N,S,P)$

   1. $V_T$是终结符集合
   2. $V_N$是非终结符集合，且$V_T \cap V_N=\varnothing$
   3. $S$是文法的开始符号，$S ∈ V_N$，开始符号必须在某个产生式左部出现一次
   4. $P$是产生式集合（有限）形式为$P→\alpha,P∈V_N,\alpha∈(V_T \cup V_N)^*$

   上下文无关文法是四元组，且文法中所有产生式的左边只有一个非终结符。

   上下文无关体现在：无论非终结符前后的串是什么，只要它在文法定义内有某产生式，就可以使用该产生式进行推导。

2. 什么是句型、句子、短语、句柄、素短语？

   1. 句型：如果$S\Rightarrow*\alpha，\alpha∈(V_T \cup V_N)^*$，则称$α$是G的一个句型

      句型中既可以有终结符，又可以有非终结符，还可以有空串

   2. 句子：不包含非终结符的句型（句型的一个完全的推导实例）

   3. 短语：句型的分析树中的每一棵子树（一个结点不算子树）的所有叶结点所组成的符号串称为该句型的一个短语

      直接短语：句型分析树只有父子两代结点的子树（简单子树）

   4. 句柄：句型的分析树中最左简单子树为该句型的句柄。

      这取决于推导方法是最左推导还是最右推导，或者取决于是自顶向下还是自底向上。

   5. 素短语：是指一个短语至少包含一个终结符，并且除它自身之外不再包含其他短语。

3. 左递归的消除

   1. 消除立即左递归

      1. $A→A\alpha_1|A\alpha_2|…|A\alpha_m|\beta_1|\beta_2|…\beta_n$

      2. $A→\beta_1A’|\beta_2A^{’}|…|\beta_nA^{’}$

         $A’→\alpha_1A’|\alpha_2A’|…|\alpha_mA’|\epsilon$

   2. 消除两步及以上的左递归

      1. 排列非终结符$A_1,A_2,…A_n$

      2. 从1到n的每个i，从1到i-1的每个j

         将每个$A_i→A_j\gamma$替换成$A_i→\delta_1\gamma$

      3. 消除立即左递归

4. 提取左公因式

   将产生式 $A\rightarrow\alpha\beta_1|\alpha\beta_2|..|\alpha\beta_n|\gamma$ 替换为：

   1. $A\rightarrow\alpha_1A’|\gamma$
   2. $A’\rightarrow\beta_1|\beta_2|…|\beta_n$

5. 递归下降语法分析

   从开始符号开始，对每一个文法中的每一个非终结符号，都根据相应的产生式的右边出现的非终结符，调用对应的过程，识别该非终结符号所表示的语法范畴，最终实现自顶向下语法分析。

6. 自顶向下语法分析的缺陷

   1. 不能处理左递归
   2. 需要复杂的回溯
   3. 难以报告出错的确切位置
   4. 低效

7. First集和Follow集

   简而言之：

   1. FIRST(α)是可从α推导得到的串的首符号的终结符号集合，其中α是任意的文法符号串

      算法：

      1. X是终结符号，则$FIRST(X)=X$；
      2. X是产生式，且$X\rightarrow Y_1Y_2…Y_n$，若a在FIRST($Y_i$)中，且$\epsilon$在FIRST($Y_1$)，FIRST($Y_2$)，…，FIRST($Y_{i-1}$)中，则把a加入FIRST(X)，如果$\epsilon$在所有的FIRST($Y_i$)中，则加入$\epsilon$ 到FIRST(X)中；
      3. 如果$X→\epsilon$是产生式，将$\epsilon$加入FIRST(X)中。

   2. FOLLOW(A)是可能在句型中紧跟在A右边的终结符号集合，其中A是非终结符号。

      注：这里假设结束标记#不是任何文法的符号。

      算法：

      1. 对于文法开始符号S，令$∈FOLLOW(S)

         $是输入串的结束符；

      2. 如果$A\rightarrow \alpha B \beta$，则将FIRST(β)中除ε以外的符号都放入到FOLLOW(B)中，即： $$ FIRST(\beta) －{\epsilon} ⊆FOLLOW(B) $$

      3. 如果$A\rightarrow \alpha B$，或$A\rightarrow \alpha B \beta$，其中FIRST(β)中包含ε（$\beta \Rightarrow *\epsilon$），则将FOLLOW(A)中所有符号都放入到FOLLOW(B)中，即： $$ FOLLOW(A) ⊆FOLLOW(B) $$

8. LL文法和LR文法

   1. LL(1)文法是自顶向下分析法

      自顶向下：从开始符号出发，根据产生式推导给定的句子，用推导，最右推导是规范推导。

   2. LR(0),LR(1),SLR(1),LALR(1)是自底向上分析法

      自底向上：从给定的句子归约到文法的非终结符号，用归约，最左归约是规范归约。

9. LL(1)文法

   L表示从左到右扫描，L表示产生最左推导，1表示作决定时每次向前看1个输入符号。

   对于产生式$A \rightarrow \alpha | \beta$，需要满足条件：

   1. 不存在终结符号a使得α和β都能推导出以a开头的串 $$ FIRST(\alpha) \cap FIRST(\beta)=\varnothing $$

   2. α和β最多只有一个可以推导出空串

   3. 若$\beta \Rightarrow *\epsilon$ $$ FIRST(\alpha) \cap FOLLOW(A)=\varnothing $$

   特点：

   1. 无公共左因子
   2. 无二义性
   3. 无左递归

10. LR(0)

    L表示从左到右扫描，R表示反向构造一个最右推导序列，0表示作决定时每次向前看0个符号。

11. LR(1)

12. SLR(1)

13. LALR(1)