【龙书笔记】编译器前端之语法分析涉及的基本概念

前一篇龙书笔记主要介绍了编译器内部实现的几个主要步骤，本篇笔记主要说明编译器前端涉及到的重要基础概念。
编译器前端主要包括词法分析、语法分析、语义分析及中间码生成4个阶段，一个典型的编译器前端处理模型如下图所示：

下面出现的术语或基础概念均是语法分析阶段会涉及到的。

2. context-free grammar
上下文无关文法（简称文法，grammar）是一种约定的标记法（notation），用来描述由编程语言构造的层次语法结构。考虑下面的语法形式：
if(expression) statement else statement
这种语法构造规则可以被表达成下面的形式：
stmt -> if (expr) stmt else stmt
这种规则在术语上称为产生式（production）；在产生式中，关键词（如if/else）和括号元素被称为终结符号（terminal）；而expr和stmt这样的变量用来表示由terminals构成的序列，它们被称为非终结符号（nonterminal）。
context-free grammar有4个要素，如下所列：
1) 包含一组终结符号（又称为"tokens"），它们通常是由编程语言预留的一些基础符号（如关键字或括号或常数）
2) 包含一组非终结符号（又称为"syntactic variables"），每个nonterminal表示一个终结符号串的集合
3) 包含一组产生式，其中每个产生式由3部分组成：一个被称为产生式的head或left side的非终结符号；一个箭头（表示"can have the form"）；由终结符号或非终结符号构成的序列（被称为产生式的body或right side）
4) 指定一个非终结符号作为start符号
在描述文法时，通常会列出该文法的产生式且首先列出start符号对应的产生式。
若某个非终结符号是某个产生式的头部，则该产生式是该非终结符号的产生式。
根据文法推导符号串时，通常从开始符号出发，不断将某个非终结符号替换为其对应的某个产生式。可以从开始符号推导得到的所有非终结符号串的集合称为该文法定义的语言（language）。
语法分析的任务是：以终结符号串为输入，找出从文法的开始符号推导出这个串的方法。如果找不到对应的方法，则应该抛出语法错误。

3. parse tree
语法分析树以图形方式展示了如何从文法的start符号来推导相应语言中的符号串。
给定一个上下文无关文法，其对应的语法分析树具有以下性质：
1) 树的root节点被标记为start符号
2) 每个叶子节点被标记为终结符号或空串
3) 树的内部节点被标记为非终结符号
4) 如果非终结符号A是某内部节点的标号，且它的子节点的标号从左至右分别为X1, X2, ..., Xn，则必然存在产生式A->X1X2...Xn，其中X1至Xn既可以是终结符号也可以是非终结符号
假设某个语言的文法规则由如下产生式组成：

则表达式9-5+2的推导过程可由下面的语法分析树来展示：

一颗语法分析树的叶子节点从左至右构成了树的结果，也就是从这颗语法分析树的根节点上的非终结符号推导得到的符号串。
一个文法的语言的另一个定义是指能够由某颗语法分析树生成的符号串的集合。
为一个给定的终结符号串构建一颗语法分析树的过程称为对该符号串进行语法分析。

4. 二义性（ambiguity）
对于同一个给定的终结符号串，文法可能会生成不只一颗语法分析树。这样的文法称为具有二义性（ambiguous）。
例如下面给出的文法规则就具有二义性：
string -> string + string | string - string | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
因为根据该文法的产生式，可以对表达式9-5+2生成两颗意义不同的语法分析树，依次表示(9-5)+2和9-(5+2)：

我们需要设计出没有二义性的文法，或者在使用二义性文法时通过附加的规则来消歧。

5. 运算符的结合性（associativity of operators）
当一个操作数左右两边都有运算符时，如9-5-2或9+5+2，必须有规则约定哪个运算符被应用与该操作数。
运算符"+"是左结合的，因为当操作数两侧都有"+"时，它属于其左边的运算符。在大多数程序语言中，加/减/乘/除这4个算术运算符都是左结合的。
但熟悉C语言的话，我们知道有些运算符是右结合的，如赋值运算符"="，也即a=b=c的处理顺序与a=(b=c)相同。
下图分别是9-5-2和a=b=c两个运算操作的语法分析树，可以看到前者的分析树向左树延伸，而后者的分析树向右树延伸，明显可以看到运算符结合性对语法分析树的影响。

6. 运算符的优先级
考虑表达式9+5*2。抛开数学常识，在计算机看来，它有两种可能的解释：(9+5)*2或9+(5*2)。而运算符结合性规则只适用于同一类运算符多次出现的情况，故此处无法通过结合性规则消歧。因此，当多种运算符同时出现时，需要有规则约定它们的优先级。
与数学中的规定相同，大多数程序语言中，"*"的优先级高于"+"，这样就消除了9+5*2的潜在歧义。
备注：笔记写到这里，结合C语言中“先看优先级，优先级相同时再看结合性”的语法约定，我才彻底明白在程序语言中规定运算符的结合性和优先级是编译器在语法分析时的需求。-_-

7. 部分习题练习
Exercise 2.2.1:  Consider the context-free grammar 
S -> SS+ | SS* | a 
a) Show how the string aa+a* can be generated by this grammar. 
b) Construct a parse tree for this string. 
c) What language does this grammar generate?  Justify your answer. 
解答如下：
a) aa+a*可由下面的链式推导生成
S -> SS* -> (SS+)S* -> ((a)S+)S* -> (aa+)S* -> aa+a*
b) 根据a)给出的链式推导规则，很容易得出生成aa+a*的语法分析树如下

【参考资料】
1. <Compilers Principles, Techniques, & Tools>即龙书第2.1-2.2节

============================ EOF ============================

【龙书笔记】编译器前端之语法分析涉及的基本概念

原文：http://blog.csdn.net/slvher/article/details/44541687