本文中内容整理西安交通大学软件学院吴晓军老师的ppt中，仅供学习使用，请勿转载或他用
参考教材：《程序设计语言 编译原理》（第3版） 陈火旺等 国防工业出版社

文章目录

• 语法分析的前提
• • 方法
  • • 自上而下（Top-down）
    • 自下而上（Bottom-up）
• 语法分析--自上而下分析
• • 语法分析的任务与分类
  • 面临的问题
  • • 困难和问题
  • 问题的解决
  • • 区分三种类型的左递归
    • 1.消除左递归
    • • 直接左递归的消除
      • 间接和潜在左递归的消除
      • 消除一个文法一切左递归的算法
    • 2.消除回溯
    • • 回溯原因
      • 首符集定义
      • 定理
  • 递归下降分析程序构造
  • • 例子
  • 预测分析程序
  • • 预测分析程序的工作工程
    • • 预测分析程序
      • 分析程序的动作
    • 分析表的构造
    • • 定义首符集和后继符集
      • 构造首符集
      • 构造后继符集
      • 例子
      • 构造分析表
      • 例子：构造分析表
  • LL(1)分析法
  • 期末题！！！
  • • 2021 - A卷
    • 2021 - B卷

编译程序的结构

中间箭头不一定是单向的，有请求和响应，更多表现的是先后划分的因果关系

表格管理和出错处理是不可缺少的构建

红色字体是输入及输出

语法分析：判断若干个单词符号串是不是一个合规的语法单元

语法分析的前提

对语法的语法结构进行描述

• 采用正规式和有限自动机描述和识别语言的单词符号
• 用上下文无关文法来描述语法规则

语法分析的任务：分析一个文法的句子的结构

语法分析器的功能：按照文法的产生式（语言的语法规则），识别输入符号串是否为一个句子（合式程序）

方法

这个的分析的方法是针对语法树的

自上而下（Top-down）

• 从文法的开始符号出发，反复使用各种产生式，寻找匹配的推导
• 推导：根据文法的产生式的规则，把串中出现的产生式的左部符号替换成右部
• 从树的根开始，构造语法树
• 主要方法：递归下降分析法、预测分析程序

自下而上（Bottom-up）

• 从输入串开始，逐步进行到规约，直到文法的开始符号
• 规约：根据文法的产生式规则，把串中出现的产生式的右部替换成左部符号
• 从树叶节点开始，构造语法树
• 主要方法：算符优先分析法、LR分析法

语法分析–自上而下分析

本章内容

• 语法分析的任务与分类
• 自上而下分析面临的问题
• 递归下降分析程序构造
• 预测分析程序
• LL（1）文法

语法分析的任务与分类

$w$表示的是终结符串

语法分析的任务：对于任一给定$w\in V_T^{\ast }$，判断$w\in L(G)$

语法分析器是一个程序，他按照P，做识别$w$的工作

一个单词符号可能无法得到结果，然后会请求下一个单词符号

语法分析的分类：自下而上和自上而下

面临的问题

主旨：从文法开始符号出发，自上而下地为输入串建立一颗语法树

在该例子中有文法G：$S\to cAd,A\to ab,A\to a$

W：输入串

input pointer：输入字符指针

S：文法的开始符号

首先从开始字符开始生成语法树，然后判断当前输入字符（IP指向的字符）是否与当前语法树的左子节点匹配，如果匹配则进行下一步，如果不匹配就需要退回

c匹配上了之后IP向后移动，然后再次匹配，发现不一样，这时候就需要展开A，到这里有两种展开方法，一种展开为ab，一种展开为a，先按照ab来看

首先与第一个字符是a是匹配的，然后IP继续向后走，这时候发现不匹配了。这里发现不匹配了之后要回退回去，即撤销A展开为ab的过程。这种过程类似于超前搜索，读了之后要还回去

再将A展开为a，就可以完成匹配了，最后语法树如下：

上述分析方法的实现：

• 每一个非终结符对应于一个递归子程序，在只生成两个串的文法过程中过程无需递归；但是，对于生成无数个串的文法而言，递归不可避免。
• 递归子程序是一个布尔过程，一旦它发现自己的某个候选式与输入串匹配，它就按此式扩充语法树，返回true，指针移过已匹配的子串；否则，返回false，保持原来的语法树和指针不变

程序实现：使用两个过程：S()和A()，他们送回true or false，决定于他们是否在输入串汇总找到相应的终结符所构成的串

使用记号：

• input_symbol：当前符号内容
• input_pointer：输入字符指针

使用过程：ADVANCE()，把input_pointer移到下一输入符号位置，置input_symbol是当前符号内容

过程A的上半部分是去尝试匹配ab，下半部分是去尝试匹配a

困难和问题

• 文法的左递归
• 回溯
• 使用候选式的顺序会影响所接受的语言
  • 如：$A\to ab|a改为A\to a|ab$
• 难以报告出错的确切位置
• 穷举试探法----低效的分析方法

问题：进行自上而下语法分析时，下列哪些问题必须首先解决否则无法有效生成语法树？

• 回溯问题（√）
• 文法右递归问题
• 文法左递归问题（√）
• 多个候选式问题

解释：多个候选式问题和回溯问题可以看成是相关的，但是存在多个候选式不一定会发生回溯

问题的解决

• 左递归问题
• 回溯问题

相对而言，左递归问题危害更大，因为会使程序陷入无线迭代

区分三种类型的左递归

• 直接左递归

  形如 $N\to N\alpha$

• 间接左递归

  形如 $N\to A\alpha ,A\to B\beta ,B\to N\gamma$

• 潜在左递归

  形如 $N\to \alpha N\beta ,而\alpha \stackrel{+}{\Rightarrow }\epsilon$

1.消除左递归

直接左递归的消除

直接左递归改造前不能有空字产生式，即右侧不能含有$\epsilon$

消除方法：

• 如果$A\to A\alpha |\beta$，其中$\beta$不以A开头
• 则修改规则为$A\to \beta A^{\prime }{A}^{\prime }\to \alpha A^{\prime }|\epsilon$

$\alpha$不能为空字，这是在开始就已经进行限制了，如果是空字了，那么通过吸收律可以得到$P\to P$，这样就没有意义了，式子可以直接转换成$A\to \beta$

一般规则：

假定P的全部产生式是$P\to P{\alpha }_1|...|P{\alpha }_m|{\beta }_1|{\beta }_2|...|{\beta }_n$，其中每个$\alpha$都不等于$\epsilon$，每个$\beta$都不以P开头

那么可以将其由左递归转换为右递归：
$$\begin{gathered} P\to {\beta }_1{P}^{\prime }|{\beta }_2{P}^{\prime }|...|{\beta }_n{P}^{\prime } \\ {P}^{\prime }\to {\alpha }_1{P}^{\prime }|{\alpha }_2{P}^{\prime }|...|{\alpha }_m{P}^{\prime }|\epsilon \end{gathered}$$
例子：

新的非终结符的记号最好与原非终结符对应上，即只在其右上角加个单引号

现有文法：
$$\begin{gathered} E\to E+T|T \\ T\to T\ast F|F \\ F\to (E)|i \end{gathered}$$
消去直接左递归后：
E→TE′E′→+TE′∣εT→FT′T′→∗FT′∣εF→(E)∣i\begin{aligned} &E\to TE'\\ &E'\to +TE'|\varepsilon\\ &T\to FT'\\ &T'\to *FT'|\varepsilon\\ &F\to (E)|i \end{aligned} ​E→TE′E′→+TE′∣εT→FT′T′→∗FT′∣εF→(E)∣i​

间接和潜在左递归的消除

一个文法消除左递归的条件

• 不含以$\epsilon$为右部的产生式
• 不含回路

即不会后面的式子不会成立$P\stackrel{+}{\Rightarrow }P$

代入法：将一个产生式规则右部的$\alpha$中的非终结符N替换为”N的候选式“。如果N有n个候选式，则右边的$\alpha$重复n次，而且每一次重复都用N的不同候选式来代替N

例子

这里右部产生式有空字可以理解成是为了消除直接左递归时引入的，不然会与上面的消除左递归的条件发生冲突

$N\to a|Bc|\epsilon$在$S\to pNq$中的代入结果：$S\to paq|pBcq|pq$

间接和潜在左递归通常通过代入能转换为直接左递归

消除一个文法一切左递归的算法

一般是按照字母表的升序排序的

for循环是完成代入的

化简在课本上有例题，可以尝试着变一下排序的策略，看看做出来的文法有什么差异

例子

现有文法：
$$\begin{gathered} S\to Qc|c \\ Q\to Rb|b \\ R\to Sa|a \end{gathered}$$
方法一：排序顺序为R、Q、S

将R带入到Q中：

$Q\to Sab|ab|b$

将Q带入到S中：

$S\to Sabc|abc|bc|c$

整个文法为：
$$\begin{gathered} S\to abc{S}^{\prime }|bc{S}^{\prime }|c{S}^{\prime } \\ {S}^{\prime }\to abc{S}^{\prime }|\epsilon \end{gathered}$$
方法二：排序顺序为S、Q、R

将Q带入到S中：

$S\to Rbc|bc|c$

将S带入到R中：

$R\to Rbca|bca|ca|a$

整个文法为：
$$\begin{gathered} R\to bca{R}^{\prime }|ca{R}^{\prime }|a{R}^{\prime } \\ {R}^{\prime }\to bca{R}^{\prime }|\epsilon \end{gathered}$$

• 对文法G的所有非终结符进行排序

• 按上述顺序对每一个非终结符$P_i$依次执行：

  • for(j = 1; j < i - 1; j++)

    将$P_j$代入$P_i$的产生式（若可代入的话）

  • 消除关于$P_i$的直接左递归

• 化简上述所得的文法

2.消除回溯

回溯原因

若当前符号 = a，对A展开，而$A\to {\alpha }_1|{\alpha }_2|...|{\alpha }_m$，那么，要知道哪一个${\alpha }_i$是获得以a开头的串的唯一替换式。即：选择哪一个${\alpha }_i$，亦即通过查看第一个（当前）符号来发现合适的替换式${\alpha }_i$

怎样选择${\alpha }_i$？

• 以a为头的${\alpha }_i$
• 如有多个${\alpha }_i$以a为头，则这是文法的问题

例如，有产生式：$语句\to 条件then语句else语句|while条件do语句|begin语句表end$

若要寻找一个语句，那么关键字if，while，begin就提示我们哪一个替换式是最有可能成功的替换式

抽象地看问题：若问题不得回溯，文法G（当然G不含左递归）的必要条件是什么，也即对文法有什么要求？

若由${\alpha }_i\stackrel{+}{\Rightarrow }a\cdot \cdot \cdot$，选该$\alpha$必中，但若${\alpha }_j\stackrel{+}{\Rightarrow }\cdot \cdot \cdot$，就会导致无法百发百中。解决办法是对文法本身提出要求：“不要出现以上情况”。把上述要求阐明清楚可以采用如下顶替的FIRST($\alpha$)，即$\alpha$的首符集

首符集定义

$FIRST(\alpha )=\{a|\alpha \stackrel{\ast }{\Rightarrow }a\cdot \cdot \cdot ,a\in V_T\}，若\alpha \stackrel{\ast }{\Rightarrow }\epsilon ，规定\epsilon \in FIRST(\alpha )$

$FIRST(\alpha )$不可以称为首终结符集，因为有$\epsilon \in FIRST(\alpha )$

定理

若一个$A\in V_N$，有许多$FIRST({\alpha }_i)$，如果A的任何两个候选式${\alpha }_i和{\alpha }_j$之间均满足$FIRST({\alpha }_i)\cap FIRST({\alpha }_j)=\Phi$，意味着，A的每一候选式$\alpha$推倒后所得到的字符串第一个$V_T$均不同。

于是，对输入符号a，如果$a\in FIRST({\alpha }_i)$，则$a\notin FIRST({\alpha }_j),(j\ne i)$，因此，对A的展开无疑应选择候选式${\alpha }_i$，否则无法命中

清除回溯的方法：使非终结符A所有候选式的首符集两两不相交

方法：提取公共左因子

例如：若$A\to \delta {\beta }_1|\delta {\beta }_2|\cdot \cdot \cdot |\delta {\beta }_n|{\gamma }_1|{\gamma }_2|\cdot \cdot \cdot |{\gamma }_m$（其中，每个$\gamma$不以$\delta$开头）

那么，可以把这些规则改写成
$$\begin{gathered} A\to \delta A^{\prime }|{\gamma }_1|{\gamma }_2|\cdot \cdot \cdot |{\gamma }_m \\ {A}^{\prime }\to {\beta }_1|{\beta }_2|\cdot \cdot \cdot |{\beta }_n \end{gathered}$$
问题：清楚回溯问题时，可以检查多个候选式的首符集。请问，首符集被称为终结首符集是否正确？

答案：首符集不能被称为终结首符集或者首终结符集，因为其中可能会包含有$\epsilon$

递归下降分析程序构造

在不含左递归和每个非终结符的所有候选式的首符集都两两不相交的条件下，构造一个不带回溯的自上而下分析程序，该分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。也就是说前提条件已经消除了左递归和回溯。

这样的一个的分析程序称为递归下降分析器

例子

有如下文法：
E→TE′E′→+TE′∣εT→FT′T′→∗FT′∣εF→(E)∣i\begin{aligned} &E\to TE'\\ &E'\to +TE'|\varepsilon\\ &T\to FT'\\ &T'\to *FT'|\varepsilon\\ &F\to (E)|i \end{aligned} ​E→TE′E′→+TE′∣εT→FT′T′→∗FT′∣εF→(E)∣i​
每个非终结符所对应的递归子程序如下所示：

针对空串没有给出任何的处理，老师给出的说法是不管它，hhh

例如对于$i_1+i_2\ast i_3$有如下分析过程：

注意

• 有$\epsilon$，自动匹配，不会失败；
• 无成功/失败消息返回
• 出错位置不确切

问题：构造递归下降分析程序时，它由一组递归过程组成。每个递归过程对应文法的一个什么？

回答：非终结符

预测分析程序

问题：用递归子程序描写递归下降分析器，要求实现该编译程序的语言（高级或汇编）允许递归

改进：使用一张分析表和一个栈同样可以实现递归下降分析。用这种方法实现的语法分析程序叫做预测分析程序

上面的那个叫做递归下降分析程序

预测分析程序的工作工程

• 中间是预测分析程序的总控程序
• 预测分析表事先需要建好，在过程中需要去查找这个表
• 左边的栈最下面需要放置一个界符#，在终结符串右侧也有一个#

预测分析程序

预测分析程序包含有四部分：

一个输入：含有要分析的终结符串，右端有#

一个栈：栈底是#，栈内是一系列的文法符号；开始时，#和S（开始符号）先进栈

分析表：二维数组M[A,a]，其中$a\in V_T;A\in V_N$，行数是文法非终结符的个数，列数是文法终结符的个数+1（有#号），这里一定不要忘了列数是终结符个数加1

输出：根据分析表内元素作规定的语法分析动作

分析程序的动作

栈顶符号X和当前输入符号a，由（X，a）决定程序动作，三种可能：

若$X=a=\#$，分析停止，宣告成功地完成分析

若$X=a\ne \#$ ，则X弹出栈，前移输入指针

若$X\in V_N$，则去查分析表M的元素M[X，a]，该元素或为X的产生式，或者为一个出错元素

对于情况三，这里注意在替换的时候需要出栈之后将后面的元素反序压栈

如$M[X，a]=\{X\to UVW\}$，就用WVU（U在顶）替换栈顶的X

如果$M[X,a]=error$，则调用error程序

下面这个表把出错处理全部隐去了，实际上所有地方都有东西

记得开始一定要初始化栈底为一个#号，自己推的时候注意一下栈顶元素和当前输入元素分别是什么

到17步，左#和右#相遇，这表示分析是成功的，根据输出的顺序生成最终的语法树

结论：

• 输出的产生式就是最左推导的产生式。栈中放右部，等待与$\alpha$匹配
• 分析表中出现（栈顶，a）时，指出如何扩充树，并且能马上发现错误

实质：

• 栈：残缺规范句型
• 表：指出$V_N$按哪一条扩充，依赖于$V_T$

上述分析过程生成的语法树：

分析表的构造

行对应的是非终结符，列对应的是终结符（以及#号）

定义首符集和后继符集

先要构造两个与G有关的集合：$FIRST(\alpha )和FOLLOW(A)$，（首符集和后继符集）

定义：对于文法G，$\alpha \in V^{\ast },S,A\in V_N$

$FIRST(\alpha )=\{a|\alpha \stackrel{\ast }{\Rightarrow }a\cdot \cdot \cdot ,a\in V_T\},若\alpha \stackrel{\ast }{\Rightarrow }\epsilon ，规定\epsilon \in FIRST(\alpha )$

$FOLLOW(A)=\{a|S\stackrel{\ast }{\Rightarrow }\alpha Aa\beta ,a\in V_T,\alpha ,\beta \in V^{\ast }\}$，即句型当中的跟在非终结符后面的终结符

构造首符集

这里其实可以看一下书，非常清楚

复习整理时候在这里重新做了梳理，可以参考这个规则：

• 如果是终结符，则首符集就是自己，即$FIRST(X)$是$\{X\}$
• 如果是非终结符（$X\in V_N$），
  • 情况一：右侧第一个是终结符（$X\to a\alpha$），则$\{a\}\cup FIRST(X)$
  • 情况二：右侧是空串（$X\to \epsilon$），则$\{\epsilon \}\cup FIRST(X)$
• 如果是非终结符，并且右侧的第一个元素是另一个非终结符（这里有个前提是，文法中已经不包括左递归了，所以这里只能是其他非终结符而不能是自己），Y中的首符集的非空串全部纳入X的首符集中
  • 形式化语言描述是，若$X\in V_N,X\to Y\cdot \cdot \cdot ,Y\in V_N$，则$FIRST(Y)\setminus \{\epsilon \}\cup FIRST(X)$
  • 如果Y的首符集包含空串$\epsilon$，则继续看Y后面的元素，按照这三个规则继续扩充X的首符集
• 如果右侧所有字符的首符集都包含空串，则把空串也加入X的首符集中

先构造所有元素的首符集$FIRST(X),X\in V$

然后使用以下规则，直至再无终结符或$\epsilon$加入任一$FIRST$集为止

• 如果是终结符，则首符集就是自己，即$FIRST(X)$是$\{X\}$
• 如果是非终结符（$X\in V_N$），
  • 情况一：右侧第一个是终结符（$X\to a\alpha$），则$\{a\}\cup FIRST(X)$
  • 情况二：右侧是空串（$X\to \epsilon$），则$\{\epsilon \}\cup FIRST(X)$
• 如果是非终结符，并且右侧的第一个元素是另一个非终结符（这里有个前提是，文法中已经不包括左递归了，所以这里只能是其他非终结符而不能是自己），Y中的首符集的非空串全部纳入X的首符集中
  • 形式化语言描述是，若$X\in V_N,X\to Y\cdot \cdot \cdot ,Y\in V_N$，则$FIRST(Y)\setminus \{\epsilon \}\cup FIRST(X)$

进而：$X\to Y_1{Y}_2\cdots Y_{i-1}{Y}_i\cdots Y_k,Y_j\in V_N$

如果$\epsilon \in FIRST(Y_j),1\le j\le i-1,即Y_1{Y}_2\cdots Y_{i-1}\stackrel{\ast }{\Rightarrow }\epsilon$，则：
$$(\bigcup _{j=1}^{i-1}FIRST(Y_j)\setminus \{\epsilon \})\cup FIRST(X)$$
只有当
$$\epsilon \in \bigcap _{j=1}^{k}FIRST(Y_j),则\{\epsilon \}\cup FIRST(X)$$

右部前$i-1$个都是非终结符

上面这个的意思是如果X推导出的所有非终结符中，如果对于$1\le j\le i-1$的所有$j$来说有$\epsilon \in FIRST(Y_j)$，那么把$FIRST(Y_j)$的所有非$\epsilon$元素都加入到$FIRST(X)$中

只有$\forall j\in [1,k],\epsilon \in {\bigcap }_{j=1}^{k}FIRST(Y_j)$来说（也就是X推出的所有文法符号的首字符集都包含$\epsilon$），才可以把$\{ϵ\}$加到$FIRST(X)$中

进而再构造$FIRST(X_1{X}_2\cdots X_n)$

• $FIRST(X_1)$的非$\epsilon$终结符加入$FIRST(\alpha )$
• 若$\epsilon \in FIRST(X_1)$，则$FIRST(X_2)$的所有非$\epsilon$终结符加入$FIRST(\alpha )$
• 若$\epsilon \in FIRST(X_1),\epsilon \in FIRST(X_2)$，则$FIRST(X_3)$的所有非$\epsilon$终结符加入$FIRST(\alpha )$

最后，若$\epsilon \in FIRST(X_i),i=1\cdots n,则\{\epsilon \}加入FIRST(\alpha )$

大概意思就是当前面的文法字符的首字符集包含空串的时候，$\alpha$的首字符集才包括后面的文法字符的所有非$\alpha$的首字符集

只有当所有的元素的首字符集都包含空串的时候，$\alpha$的首字符集才包含空串

构造后继符集

$FOLLOW(A)=\{a|S\stackrel{\ast }{\Rightarrow }\alpha Aa\beta ,a\in V_T,\alpha ,\beta \in V^{\ast }\}$，即句型当中的跟在非终结符后面的终结符

后继符集只关注非终结符后面的终结符

#属于FOLLOW（S），一定不能忘了

应用下列规则，直到再没有什么加进任一$FOLLOW$为止

#属于$FOLLOW(S)$

若存在$A\to aB\beta$，则$FIRST(\beta )\subset FOLLOW(B),\epsilon$除外

若有$A\to aB,或A\to aB\beta 且\epsilon \in FIRST(\beta ),则FOLLOW(B)\supset FOLLOW(A)$，把A的位置用$\alpha B$替换之后，原来跟在A后面的现在就跟在B的后面了

问题：构造首符集与后继符集是实现预测分析程序的必要准备。请问，下列哪些选项可以求首符集？

• 终结符（终结符的首符集就是自己）
• 非终结符
• 文法符号串
• 候选式

答案：ABCD

首符集可以针对任何文法符号，后继符集只能针对非终结符

例子

首符集的构造

观察产生式的两边，F的首符集中非空串的元素都是T首符集的元素，T的首符集中非空串的元素都是E首符集的元素

后继符集的构造

这里一定不要忘记了E（开始符号）的后继符集中还有#

• 看看有没有两个非终结符挨着的，
• 看看左右两边有没有都有非终结符的

各个推导用到的都是规则三

第一个是E的后继符集都加入E‘的后继符集

最终构造结果

求出所有非终结符的首符集就够了，然后可以根据其他规则构造串的首符集

构造分析表

这个输入不包含左递归以及回溯

• 对于文法的每一个产生式，确定填入的位置
• 这时候就要看产生式右部到底包含了什么终结符，第二条实现确定列，然后根据左部把他加入分析表中
• 下面这个$b\in FOLLOW(A) $可能有不止一个b

问题：构造预测分析表时，是否有必要专设 # 列？

• 没必要
• 有必要（√）

例子：构造分析表

最终得到如下分析表

LL(1)分析法

因为把需要看多个（回溯）的情况已经排除了

有多个候选式，但是只能有一个候选式可以成为空串，不会有多个为空串，如果有多个，则他们的首符集都会包括空串这个元素，就不满足第一个条件了

条件2中的alpha表示除beta外的任意一个。。。叫啥？？

A->alpha表示A可以直接推出来a，A->beta表示A后面跟着的第一个是a，这时候就不知道怎们操作了

答案：ABC

如果只是判断一个文法能不能构成LL(1)文法则可以只求出首符集和后继符集，然后检查集合的关系

也可以构造分析表去查找有没有多重入口，也就是一个各自会不会有两个候选式

如果有嵌套的话，内层一定是多分支的，外层才有可能是单分支的

期末题！！！

2021 - A卷

一定不要忘了#！！

2021 - B卷

总结

以上是生活随笔为你收集整理的编译原理第四章--自上而下的语法分析的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。