编译原理经典算法的可视化实现
4 语法分析
4.1 语法分析的基本概念
所谓语法分析就是对我们给定的符号串α，通过一定的算法来判断它是否是某个文法的合法句子，换句话说，就是检查语法是否错误的过程。
语法分析包括自顶向下的推导和自底向上的归约这两类。这两种方法都是通过构造语法树来模拟这个分析过程。
而在本演示系统中，我们只研究自顶向下的LL(1)文法的演示。
4.2 语法分析的任务
语法分析器就是执行语法分析的程序，它是编译器的核心部分。而它的主要任务就
是识别不同的语法成分，判断其语句是否符合该语法，并为语法分析和代码生成做必要的准备。它是以词法分析器生成的单词来作为分析对象或输入。其基本的任务是根据语法规则，分析源程序的语法结构（分析如何将这些词法单元组成各种语法，如各种表达式，语句，函数等），并在分析过程中，还要检查语法的正确性。它的分析结果是识别出没有错误语法的语法成分。
4.3 语法分析基础
4.3.1 上下文无关文法
程序设计语言的许多结构都包含固有的递归结构，这种递归结构可以用上下文无关文法定义。上下文无关文法由终结符、非终结符、开始符号和产生式组成.
（1）通俗的说，终结符就是语言中用到的基本元素，一般不能再分，而终结符也是组成字符串的基本符号。而在讨论程序设计语言时，“记号”和“终结符”是同义词。 （2）非终结符是语法中用到的元素。而非终结符所规定的字符串集合将对定义该文法所产生的语言有所帮助。非终结符给语言强加一种层次结构，而这种层次结构对语法分析和翻译都是非常有用的。
（3）有一个非终结符将在文法中被指定为开始符号。而开始符号所表示的字符串
17
编译原理经典算法的可视化实现 集合就会是该文法所定义的语言。
（4）文法的产生式说明了非终结符和终结符组合成串的方式。每个产生式将由非终结符开始，后面跟随一个箭头，然后是非终结符和终结符组成的串。例如有下述产生式的文法： expr→expr op expr expr→( expr ) expr→-expr expr→id op→ + op→- op→* op→/ op→↑
在这个文法中，我们定义了简单的算术表达式，文法的终结符包括id、+、-、*、/、↑、( 和 )，文法的非终结符包括expr和op,开始符号是expr。 4.3.2推导和分析树
推导是描述文法定义语言过程的有用方法，其核心思想是把产生式看成重写规则，即用产生式右部的串来代替左部的非终结符。而事实上，推导可以给出自顶向下构造分析树过程的精确描述。例如，有这样的算术表达式文法：
E→ E + E| E * E | ( E )｜－E | id
其中，非终结符E表示一个表达式。产生式E→-E意味着前面带有减号的表达式仍然是表达式。这个产生式允许用-E代替出现的任何E，以便从简单的表达式产生更复杂的表达式。如果用-E代替单个E，这个动作可以描述为E错误！未找到引用源。 -E，我们可以将它读为“E推导出-E“。产生式E→（E）表示可用（E）代替在文法符号串中出现的任何E。如E*E错误！未找到引用源。 (E)*E或E*E错误！未找到引用源。E*(E). 在上面的文法中，我们从E开始，不断地（以任何顺序）应用产生式，得到一个替换序列。例如，E错误！未找到引用源。-E错误！未找到引用源。-(E)错误！未找到引用源。-(id),这个替换序列被称为从E到-（id）的推导。
更抽象地说，αAβ=>αγβ,如果A→γ是产生式，而且α和β是任意的文法符号的串。
18
编译原理经典算法的可视化实现 如果α1错误！未找到引用源。α2错误！未找到引用源。…错误！未找到引用源。αn，则说α1推导出αn。符号错误！未找到引用源。表示“一步推导“。通常错误！未找到引用源。表示”零步或多步推导“，因此，
（1）对任何串α，α错误！未找到引用源。α。
（2）如果α错误！未找到引用源。β，而且β错误！未找到引用源。γ，则α错误！未找到引用源。γ。
类似地，我们也用错误！未找到引用源。表示“一步或多步推导“。对于开始符号为S的文法G,我们可以用错误！未找到引用源。关系来定义G所产生的语言L(G)。L(G)中的字符串只包含G的终结符。当且仅当S错误！未找到引用源。w时，那么终结符w在语言L(G)中。终结符w称为G的句子。由上下文无关文法产生的语言称为上下文无关语言。如果两个文法产生同样的语言，则称这个文法等价。而对于开始符号为S的文法G,如果S错误！未找到引用源。α,则称α为G的句型，其中α可能含有非终结符。而句子则是不含非终结符的句型。
在推导的每一步都有两个选择，首先需要选择被替换的非终结符，然后再选择用于替换该非终结符的候选式。而在推导的过程中，我们考虑每一步都替代最左非终结符的推导，这样的推导叫做最左推导。而如果我们考虑的是每步推导都替代最右非终结符的推导，则这样的推导就叫最右推导，
分析树可以看成是推导的图形表示，但它不能显示出替代顺序的选择。分析树的叶节点用非终结符或终结符来标记，它们从左到右构成一个句型，称为树的边界或果实。
对于推导和分析树之间的关系，我们考虑任意的推导α1错误！未找到引用源。α2错误！未找到引用源。…错误！未找到引用源。αn，其中α1是单个非终结符A。对推导中
的每个句型αi，构造产生αi的分析树。该过程是对i的归纳。α1=A对应的分析树是标有A的单个节点，是归纳的基础。为了完成这种归纳，假设我们已经构造了产生αi-1=X1X2…Xk(Xi代
表一个非终结符或终结符)的分析树，假设
αi是用β=Y1Y2…Yr代替αi-1中的非终结符
αi-1应用产生式Xj→β,推导出αi=
Xj所产生的，即在推导的第i步中，对X1X2…Xj-1βXj+1…Xk。
如果L(G)中存在一个具有两棵或两棵以上分析树的句子，或者是L(G)中存在一个
19
编译原理经典算法的可视化实现 具有两个或两个以上最左（或最右）推导的句子，则称G是二义性文法。 而有些二义性文法是可以通过改写来消除二义性。
4.3.3消除左递归
如果文法G具有一个非终结符A使得对某个字符串α存在推导A错误！未找到引用源。Aα,则称G是左递归的。自顶向下语法分析法不能处理左递归文法，而下面的算法能够系统地消除文法中的左递归。 输入：无循环推导和ε产生式的文法G 输出：与G等价的无左递归文法
方法：对文法G应用图4.1中的算法。注意，得到的非左递归文法可能含有ε产生式。
1.以某种顺序排列非终结符A1,A2,? An; 2.for i:=1 to n do begin for j :=1 to i-1 do begin 用产生式Ai→δ1γ|δ2γ|?|δkγ代替每个形如Ai→Ajγ的产生式。 其中，Aj→δ1|δ2|?|δk是所有的当前Aj产生式； end 消除Ai产生式中的直接左递归end
图4.1 从文法中消除左递归的算法
该算法对于所有无循环推导和ε产生式的文法都有效，循环推导和ε产生式都可以系统地从文法中消除掉。 4.3.4 提取左因子
我们想要构造有效的自上而下的分析器，就要消除回溯。而提取左因子是一种有效
的消除回溯的文法变换。提取左因子的基本思想是：当不清楚应该用两个或多个选择中的哪一个来替换非终结符A时，可通过改写A产生式这种方法来推迟这种决定，然后直到看见足够多的输入并且能做出正确的选择为止。提取左因子方法的算法思想描述如图所示：
20