1.语法分析器的作用

  • 读取记号流，并检查是否符合文法(能否用文法产生)
  • 输出分析树的某种表示
  • 报告语法错误，并从语法错误中恢复
  • 其他任务，例如将记号信息存入符号表、进行其他语义、类型检查、产生中间代码

2.上下文无关文法/CFG

文法即描述编程语言语法的一套规则，而上下文无关文法是一类特殊的文法

定义

上下文无关文法G是一个四元组$(V_T,V_S,S,P)$，其中:

  1. $V_T$是终结符的非空集合
  2. $V_S$是非终结符的非空集合，并且$V_T\cap V_S=\emptyset$，即终结符不可能进一步推导，非终结符也一定可以进一步推导
  3. $S$是开始符号，其为某非终结符，由S推导得到的终结符串集就是该文法定义的语言
  4. $P$是产生式的有限集合，形式为$A\to \alpha$，且$A \in V_S,\alpha \in (V_S\cup V_T)^*$，$S$至少出现在一个产生式的左部

对于上述定义的说明：

  1. “终结”和“非终结”的含义是“能否进一步进行推导”或者说“推导到这里终结”，并不是指符号在串尾或者中间
  2. 对于编程语言的文法来说，终结符和记号是同义词，因为语法分析器处理来自词法分析器的记号流
  3. 值得注意的是，“上下文无关”体现在产生式左部只包含非终结符A，它与前后符号没有关系，所以称之为上下文无关。一般的程序设计语言例如C语言等，需要先定义变量才能使用，显然是上下文有关的。

上下文无关文法与正规式

共同点

  1. 都可以用于定义语言

不同点

  1. 表示语言的能力不同。例如正规式是不能表示固定次数的符号重复形成的串的，配对括号、语句嵌套正规式也无法表示。任意正规集可以用一CFG表示。
  2. 对应的表示不同。上下文无关文法可用分析树表示对某串的推导过程，而正规式采用FA进行描述

形式语言分类

文法 别名 对应模型
0型文法 短语文法 图灵机
1型文法 上下文有关文法/CSG 线性有界自动机
2型文法 上下文无关文法/CFG 下推自动机
3型文法 正规文法 有限自动机

对4种文法的简单理解
1.短语文法
$\alpha \rightarrow \beta,\alpha \in V^{} \cup V_N \cup V^{},\beta \in V^{}$，任何0型语言和递归可枚举集等价，即属于该语言的字符串一定可以被递归枚举加以验证，但是不属于该语言的字符串不一定能在有限时间内得到验证结果
一个0型文法的例子：$L_0 = {wcw|w\in(a|b)^}$，即w必须先出现才能引用(例如C，java)

2.上下文有关文法
$\alpha \rightarrow \beta, len(\alpha) \leq len(\beta)$,或者$\alpha A \gamma \rightarrow \alpha \beta \gamma,\alpha , \gamma \in V^*,\beta \in V^+$
可以看到$A$推导到$\beta$是与其前后内容有关的，必须前后分别是$\alpha,\gamma$才能推导

3.上下文无关文法
$A \rightarrow \alpha, \alpha \in V^*, A\in V_N$，有一位计数功能

4.正规文法
$A \rightarrow \alpha\ or\ A \rightarrow \alpha B, \alpha \in V^*_T, A,B \in V_s$，根据产生式的形式可以看出无法计数以及配对

扩展：递归可枚举指什么？

3.推导

基本概念

推导指将产生式作为重写规则，把符号串中的非终结符用右部的串代替

规范推导指最右推导，规范归约指最左规约。

文法产生的语言即符合某一文法规则的串的集合，或者文法产生的所有句子。例如用文法描述算数表达式。

算数表达式中左结合表示先出现先运算，故例如加法可写成：$E \rightarrow E + T$，其中E,T,F可用于表达其他的运算优先级。

4.二义性文法

二义性文法指的是对于某个句子，具有非唯一最左/最右推导的文法，或者具有非唯一分析树的文法
二义性语言指的是不存在能产生它的非二义性文法的语言，即产生其的文法都是二义性的

二义性文法例子

见ppt: if-then-else例子，并思考为什么要分为matched和unmatched两个产生式？(为了保证就近配对)

消除二义性方法

  1. 重写文法
  2. 引入标识符配对

一般而言，如果相同左部的产生式存在相同的前缀或者后缀，那么这个文法可能是二义性的，因为这样的文法对往往会在推导时产生两种不同的推导

5.自上而下分析

也称自顶向下分析，对应最左推导，本质是预测性的深度优先或者说前序遍历建立分析树。自上而下分析可以分为试探分析和预测分析。

5.1.基本过程

自上而下分析可以分为如下步骤：(以试探分析法为例，并假设暂未对文法进行提左因子操作)

  1. 从待分析的非终结符开始，其处于产生式左部，对其进行展开。如果有多个产生式，那么逐个尝试。
  2. 展开后从左至右依次递归进行1中所说的步骤(递归只是一种描述，实现可以是递归的也可以是循环的)，如果使用某产生式匹配失败，那么进行回溯，即删掉由该产生式产生的树，重新对待分析的非终结符进行分析；如果当前非终结符所有尝试均失败，那么向上回溯至上一层分析树重新分析。
  3. 当所有尝试均失败，可以认为分析失败

5.2.提左因子&消左递归

5.2.1.消左递归

意义：消左递归可以防止正在构建的语法树无限增长，但是符号指针没有实质性发生移动的情况发生。考虑自上而下推导语法树构建过程，先序遍历或者说深度优先在左递归产生式的作用下在最左侧不断增长树的高度，但是指针始终未移动。

直接\间接左递归

  • 直接左递归：指文法存在$A \rightarrow AB$形式的产生式，其中$A \in V_N, B \in V^+$
  • 间接左递归：指文法存在$A \implies ^+ AB$形式的产生式，其中$A \in V_N, B \in V^+$

消除左递归的方法

1.先将间接左递归化为直接左递归。通常将简单产生式带入复杂产生式即可化为直接左递归。
2.直接左递归通常可以通过文法变换变为右递归文法。通常形式为原文法为$A \rightarrow AB|\beta _1|…|\beta _i$，变换后为:
$A \rightarrow \beta _1 A^{‘}|…|\beta _iA^{‘}$
$A^{‘} \rightarrow BA^{‘}|\epsilon$
本质上是在考察文法的实际含义，例如上述文法表示的句子为$\beta _1|…|\beta _i$开头，后跟0至多个$B$的句子，很容易写出右递归形式的文法。

5.2.2.提左因子

意义：提左因子使得非终结符遇到某符号时不会有多种选择，也即将决定推迟一层 例如文法:
$A \rightarrow \alpha$
$A \rightarrow \alpha \beta$
提左因子后变为：
$A \rightarrow \alpha A^{‘}$
$A^{‘} \rightarrow \epsilon|\beta$
其中$\epsilon$表示除了$\beta$之外的任意符号，这个符号可以是属于语法树其他分支的一部分，也可以是句子的结束符。

5.3.预测分析

某文法经过可能的消除二义性、消除左递归、提左因子变换之后，即可以进行预测分析法(自上而下分析的一种)

概念

根据当前记号来准确、唯一地选择左部的某一个产生式，避免回溯。其实现方法为利用Fisrt和Follow集合构建预测分析表。

意义

预测分析可以保证一次分析即结束某非终结符的分析，若分析成功则接着进行，分析失败无需回溯，直接判定整体分析失败。

First\Follow符号集合

First符号实际上是分析A非空产生式时希望看到的符号，这样可以利用该符号确定某一产生式
Follow符号实际上是分析A空产生式时希望看到的符号,这样可以直接结束A的分析开始下一个符号的分析，在根据产生式推导Follow符号时要仔细考虑不同符号的follow之间的关系，不要简单的认为相同等。

First集合

First集合也称首符号集合，用于表示某终结符或非终结符开头的所有可能符号（包括$\epsilon$）。
算法核心思想为：对每个A为左部的产生式，逐个考察右部包含的项(假设各项First已求出来)，第一项的Fisrt是A的Fisrt，若第一项可为空，则第二项…，否则结束。递归或者说循环进行，直到考察完递归/循环完成。 首符号集合算法

Follow符号集合

Follow符号集合也称后继符号集合，用于表示跟随在某非终结符之后的所有可能符号。要注意如果跟在A后面的文法符号可以为空，那么要接着考察接下来的文法符号的First，不要遗漏。 后继符号集合算法

5.4.LL(1)文法

5.4.1.概念

文法$G$是$LL(1)$文法，等价于对于文法的任意两个产生式$A \rightarrow \alpha | \beta$，满足：

  1. $First(\alpha) \cap Fisrt(\beta) = \emptyset$
  2. 如果$\epsilon \in First(\beta)$，那么$First(\alpha) \cap Follow(A) = \emptyset$

对LL(1)文法的理解：LL(1)文法第一个“L”表示从左至右扫描，第二个“L”表示最左推导，“1”表示看1位，即根据当前指针指向符号来预测推导。LL(1)文法的限制条件说明遇到某个符号时，对于任何一个非终结符，都有唯一的预测。

5.4.2.性质

LL(1)文法有如下性质

  • LL(1)文法是非二义性的，原因是一定可以通过当前符号预测下一步推导，最终确定如何推导或者检测到语法错误
  • LL(1)文法的产生式没有左因子，否则不满足定义要求的$First(\alpha) \cap Fisrt(\beta) = \emptyset$
  • LL(1)文法没有左递归，否则必然存在产生式First相同的情况,不符合定义；当然存在左递归的文法也是不能进行预测分析的，原因相同。
  • 其他

5.4.3.递归下降分析

递归下降分析实际上就是按照构建好的预测表，编写对应的递归程序。预测表通过if(lookahead==symbol)-else if-else语句体现在递归程序里。
这里直接使用一个来自《编译原理》p56的Pascal语言例子。产生式为：

\[\begin{aligned} type & \rightarrow simple \\ & |\ \uparrow\ id \\ & |\ array\ [simple]\ of\ type\\ simple & \rightarrow integer \\ & |\ char \\ & |\ num\ dotdot\ num \end{aligned}\]

对应递归下降分析程序如下。以产生式$type \rightarrow array\ [simple]\ of\ type$为例，可以看到type()函数中第二个else if正是按照该产生式的顺序进行匹配，而这个else if的条件也正是lookahead==array，即$Fisrt(type)$中的一种情况。

递归下降分析程序对于$\epsilon$可以认为是与任何符号相配的，如果出现错误，返回之后交给其他程序处理；也可以显式地检查lookhead是否是follow中的一个。

递归分析

5.4.4.非递归的预测分析

非递归的预测分析实际上利用栈来实现递归相同的功能，利用栈顶符号和当前符号预测应该进行的最左推导，并将最左推导倒序入栈（实际上是当做队列在使用，当然也是深度优先遍历，每次对栈顶符号展开），继续进行，直到整个符号串读到$（结束符），然后停机。
非递归预测分析

具体流程为：将$和起始符入栈，然后进行以下操作：

  1. 如果当前符号为$，并且和栈顶符号相等，那么说明已分析完符号串，停机
  2. 如果当前符号a和栈顶符号X相等（只可能是两个终结符相等），那么说明匹配，X出栈，指针向后移动一个位置
  3. 如果当前符号a和栈顶符号X不相等（只可能是两个终结符不相等），那么说明不匹配，根据预测分析的特性，可以知道出现语法错误，转错误处理程序
  4. 如果当前符号a是非终结符，根据分析表$M[X,a]$这一项，确定使用哪个产生式，并在X出栈后，将产生式右部倒序入栈（目的是让最左符号处于栈顶，从而接着进行最左推导），然后继续对栈顶非终结符进行预测分析或者对栈顶终结符进行匹配。

5.4.5.预测分析表

预测分析表的思想为：其指示了栈顶符号和当前符号确定时，应该如何推导。预测分析表的构建过程实际上是从三方面指示了推导的选择：

  1. 当对$A$进行推导时，$A \rightarrow \alpha$中$\alpha$所有首符号$s$($s \neq \epsilon$)都表明应该按照$A \rightarrow \alpha$推导，因此将该产生式填入M[A,s]
  2. 当对$A$进行推导时，如果$A \rightarrow \alpha$中$\alpha$的首符号包含$\epsilon$（这表示$\alpha$可通过若干步推导到空），那么对于$A$所有后继符号$t$(包括结束符)，都应按照$A \rightarrow \alpha$推导，因此将该产生式填入M[A,t]，表示结束A的推导，接着进行最左推导
  3. 当对$A$进行推导时，如果出现的符号不是$A$的首符号，且在$A \implies ^* \epsilon$成立时也不是$A$的后继符号，那么一定出现了推导上的错误。由于推导一直按照预测分析的方式进行，这时可以断言出现语法错误，将error()填入（可空白省略），无需回溯。

上述构建过程的规范化描述如下，其中$a,b,c$均为非终结符：
\(\begin{aligned} M[A,a] = {A\rightarrow \alpha} &\iff a \in Fisrt(\alpha) -{\epsilon}\\ M[A,b] = {A\rightarrow \alpha} &\iff \epsilon \in Fisrt(\alpha) \And b \in Follow(A)\\ M[A,c] = error() &\iff c \notin Fisrt(A) \And \\ (&A \implies ^* \epsilon \And c \notin Follow(A)) \end{aligned}\)

根据$LL(1)$文法的性质，如果文法是$LL(1)$的，那么上述填表过程不会产生任何冲突，这是因为$LL(1)$文法决定了相同左部的产生式的左部符号first集合不冲突，并且可为空的产生式左部follow集合与其first集合不冲突，这样对于任意符号，只有一种选择(按某一产生式推导或者错误)。

5.5.一个完整LL(1)文法例子

6.自底向上分析

6.1.句柄

某最右推导序列$S \Rightarrow ^* \alpha A \delta \rightarrow \alpha \beta \delta$中产生式$A \rightarrow \beta$以及其在右句型中的位置称为右句型$\alpha \beta \delta$的句柄(handle)

例如：某右句型为$aAbcde$，如果有产生式$A \rightarrow Abc$被用于最右推导以产生$aAbcde$，那么称$Abc$是$aAbcde$的句柄

注意：二义性文法中右句型的句柄可能不唯一，因为可能存在两个不同的最右推导；非二义性文法的右句型句柄是唯一的。

活前缀即不超过句柄右端的右句型的前缀，此时称其为右句型的活前缀，发生归约前，分析栈内的符号构成了活前缀。

对活前缀有效的LR(0)项目，如果有最右推导$S \rightarrow t A \omega \rightarrow t \alpha \beta \omega$，那么项目$A \rightarrow \alpha \cdot \beta$ 对活前缀$t\alpha $有效，同理项目$A \rightarrow \alpha \beta \cdot$ 对活前缀$t\alpha \beta$有效。反应在FA上，即从开始状态读过的路径到达某一状态，那么状态内项目对这个路径对应的活前缀有效。

6.2.移进-归约分析

移进-归约分析是自上而下分析的一般风格，移进-归约分析过程本质上是：发现句柄(对当前右句型是唯一的)，并将右句型中句柄对应部分用对应产生式的左部非终结符替换的过程，每次替换都是一次最左归约，即最右推导的逆过程。

6.2.1.移进-归约分析基本实现

可考虑用符号栈以及四个动作实现移进-归约分析。四个动作为：

  1. 移进(shift)：读取符号，入栈
  2. 归约(reduce)：句柄出现在栈顶，将句柄弹出，并将相应产生式左部入栈（由分析表根据当前符号以及栈内的记号来决定如何归约）
  3. 接受(accept)：分析完成
  4. 错误(error)

6.2.2.冲突

可能发生的冲突包括：归约-归约冲突和移进-归约冲突。
只要出现这两种冲突，那么文法一定不是LR(k)文法

归-归冲突

概念：位于栈顶的句柄匹配两个及以上的产生式右部，且无法通过栈内符号的信息来确定如何选择归约对应的产生式。

注意：归-归冲突不代表文法是二义性的，只是根据现有的信息（例如栈内符号和下k个符号），无法判断如何归约，但是客观上，若文法是非二义性的，这个时候只有一种归约方法是对的，因为最右推导序列是唯一的；错误的归约依然会引起报错，只是当时不知道如何选择对的。解决方法可以是对词法分析器进行改进，对记号进行更细致的分类。

实例参考编译原理p68关于数组和过程文法引起的归-归冲突

移-归冲突

概念：根据栈内信息和当前k个符号，无法确定进行移进还是归约。

例子：二义性文法可能存在移-归冲突，因为考虑相同左部产生式可能一个是另一个前缀，这样势必会导致移进-归约冲突。

6.3.LR(0)分析

基本概念

  • 活前缀(viable prefix)：即产生式中右句型的一组前缀，这些前缀不会超过右句型最右句柄的右端。LR分析栈内的符号总是构成活前缀，因为这样才能等待移进某终结符或者入栈某非终结符来进行最左归约。
  • LR(0)项目：即向产生式右部某处加点形成的产生式，点的左边代表已经分析完成的历史信息，点的右边表示接下来期望看到的信息。
  • 闭包函数$closure(I)$：即将项目$A \rightarrow \alpha \cdot B \beta$可能进行相同操作的项目合并为一个集合，即将$B \rightarrow \cdot X$全部加入该集合。这表示识别了某个活前缀到达了项目$A \rightarrow \alpha \cdot B \beta$，接下来要进行$B$的分析，在开始B的分析前有所有的这些可能性。
  • (LR(0))项目对活前缀有效：如果$S^{,} \Rightarrow ^* \alpha A \omega \rightarrow \alpha \beta _1 \beta _2 \omega$，那么称项目$A \rightarrow \beta _1 \cdot \beta _2$对活前缀$\alpha \beta _1$有效。实际上即该项目处于DFA中读取该活前缀后所处状态的集合内，并且相应活前缀经过该项目期待的输入$\beta _2$后依然是活前缀。LR(1)项目对活前缀有效，那么项目的搜索符要对应正确，同样可以通过FA来判断。

LR(0)分析表

构建LR(0)分析表实际上是在构建识别活前缀的DFA主要包含以下步骤：

  1. (可省)构建识别活前缀的NFA
  2. 添加$S^{‘} \rightarrow S$形成拓广文法，列举出所有的LR(0)项目
  3. 构造$S^{‘} \rightarrow \cdot S$的闭包作为初始状态，构造$S^{‘} \rightarrow S\cdot$的闭包作为结束状态。
  4. 从初始状态开始，根据状态内项目接受某符号后形成的新项目构建新状态，并计算新状态的闭包，形成项目集规范族
  5. 根据DFA构建分析表。先对产生式编号，然后以项目编号为纵列，终结符(包括$)为action横列，非终结符为goto横列，写出对应的动作和转移到的集合号。要注意的是，LR(0)分析表只要看到点处于最后，直接按对应产生式归约。

LR(0)分析栈使用

LR(0)分析栈本质上和移进-归约分析栈相同，但是每次移进时先后进栈当前终结符和状态标识，状态标识起到的作用就是让分析器知道当前栈内的信息而不用去搜索栈。
LR(0)分析器同样有四种操作action[S,a]：

  1. $s_i$：对应移进，即将$a$和状态$s_i$依次入栈
  2. $r_i$：对应归约，即将栈顶符号按第i个产生式归约，将产生式右部内容全部弹出(包括状态和符号，共$2\mid S \mid$个)，用归约使用的产生式左部非终结符来对栈顶状态进行转移，即将这个非终结符和栈顶状态对应非终结符转移后状态依次入栈，然后再考虑符号a和当前栈顶状态对应动作关系。实际上，这一步即退回到之前的某个状态，然后把归约结果入栈，再根据归约得到的结果再移动到某个状态（对应FA上某一个转移），即最左归约后再考虑后续符号。
  3. $acc$：对应接受，只可能是读取到了结束符后从包含项目$S^{‘} \rightarrow S \cdot$的状态得到
  4. $error()$：对应分析表项为空，表示发生语法错误

其他的LR文法分析栈和分析表的配合使用与LR(0)相同。

LR(0)文法

文法是LR(0)文法 $\iff$ 文法的LR(0)分析表没有多重定义，也即任意项目规范族中任意状态不能同时含有移进和归约的项目

理解：LR(0)分析之所以k=0，是因为其仅根据当前栈顶状态本身的信息来判断归约还是移进(虽然要根据当前符号判断是否出错，以及移进转移到什么状态，这是必须的)，这也是LR(0)分析能力弱的原因(有移进-归约冲突，当然也可能存在归约-归约冲突，即两个同左部归约项目在同一状态，虽然LR(0)一定要归约但不知道按照哪个归约)

6.4.SLR(1)分析

6.4.1.SLR(1)分析表

SLR(1)分析即simple-LR(1)分析，核心思想为：通过向前看一个符号解决LR(0)分析中可能出现的冲突，包括以下两点：

  1. 同一个状态同时含有移进$A \rightarrow \alpha \cdot a \beta$和归约$B \rightarrow \gamma \cdot$，对于LR(0)分析表，这时不能将整行都填归约，那么只有当当前符号$\in Follow(B)$时进行归约，而当前符号为$a$则移进。
  2. 同一个状态同时含有归约$A \rightarrow \alpha \cdot$和$B \rightarrow \beta \cdot$，对于LR(0)分析表，这时无法确定应该填写按哪个产生式归约，那么只有当当前符号$\in Follow(A)$时按前者归约，当前符号$\in Follow(B)$时按后者归约。

6.4.2.可能的冲突

  1. 区分同一个状态的移进和归约时，若移进符号$a \in Follow(B)$，冲突仍然存在
  2. 区分同一个状态的两个归约时，若当前符号$a \in Follow(A) \cap Follow(B)$，冲突仍然存在

6.4.3.SLR(1)文法

文法是SLR(1)文法 $\iff$ 文法的SLR(1)分析表没有多重定义

6.5.LR(1)分析

6.5.1.LR(1)项目

相比LR(0)项目，添加一个搜索符。作用是：让归约项目与对应的最右推导对应，只有当前符号是项目搜索符才进行归约；搜索符不影响移进，因为移进和归约的冲突已经解决(理想情况下已经解决)。

例子：
$[A \rightarrow \alpha \cdot \beta,a]$，即由LR(0)项目和搜索符构成

6.5.2.LR(1)分析表

LR(1)分析表也称规范的LR分析表，核心思想为：SLR(1)分析的归约信息过于粗略，可能会造成归约“扩大化”，引起不必要的冲突，即某个后继符号并不对应某个归约而是对应另一个相同左部的归约项目，但是却把该符号认为是归约的标志，进而可能又和同一状态其他项目发生了冲突；因此应该精确地将某归约项目与对应的最右推导那一步后面跟随的终结符进行对应，也即$Follow$的子集。

构建DFA的步骤与SLR(1)类似，但是所有的项目要改为LR(1)项目。并且有以下技巧和注意事项：

  1. 某项目后的搜索符一定是该项目最终归约时，跟着的后继符号。尤其要注意从某个项目产生出的新项目(点在最前面)的搜索符，一定要是产生它的项目产生式中其后符号的那个首符号，或者产生它的项目左部符号的Follow符号(当后面没有其他符号时)。
  2. 从一个项目转移到另一个项目，后面的搜索符不会发生改变。
  3. 一定要注意不要漏写项目，具体可参考homework4.(6)，尤其是产生式有递归形式时比较容易忘记写新产生的项目。
  4. 空产生式对应项目可以认为刚开始看，也可以认为要归约，并且搜索符仍然符合第一条所说的必须是归约时对应的那个后继符号。

6.6.LALR(1)分析

6.6.1.同心集

同心集指的是具有完全相同的LR(0)项目的LR(1)项目集，它们的搜索符不尽相同，在LALR(1)分析中可以将这些集合合并以减少项目集的数量，并将相应的状态转移关系修改。

例如如下两个LR(1)项目集：
${[A \rightarrow \alpha \cdot a \beta,a_1],[B \rightarrow \gamma \cdot,b_1]}$
${[A \rightarrow \alpha \cdot a \beta,a_2],[B \rightarrow \gamma \cdot,b_2]}$
可以合并为一个LALR(1)项目集 ${[A \rightarrow \alpha \cdot a \beta,a_1|a_2],[B \rightarrow \gamma \cdot,b_1|b_2]}$

6.6.2.LALR(1)分析表

LALR(1)分析是SLR(1)和LR(1)的折衷，构造DFA的核心思想为：先构造LR(1)对应DFA，然后合并同心集

6.6.3.LALR(1)文法

文法G是LALR(1)文法 $\iff$ LALR(1)分析表没有冲突表项

6.6.4.可能的冲突

从LR(1)创建LALR(1)文法时：

  1. 从LR(1)创建LALR(1)文法时绝不可能出现移归冲突，因为如果出现移归冲突，那么原来必然存在某LR(1)项目集中存在移归冲突
  2. 从LR(1)创建LALR(1)文法时可能出现归归冲突，即有可能状态1的某个归约项目对应后继符号与状态2某个归约项目后继符号相同，这是允许的