语法分析

前儿章讨论过了用符号代替正则表达式的简化机制，这种机制在使用时是很方便的：

digits=[0-9] +
sum=(digits“+") *digits

这些正则表达式定义了28+301+9的和。又如：

digits=[0-9] +
Sum=expr“+"expr
expr="("sum") " | digits

所定义的表达形式如下所示：

(109+23)
61
(1+(250+3))

其中的括号是匹配的。

但这些匹配括号对于有限自动机来说是不可识别的(因为一个只有N个状态的自动机不能记忆长于N的嵌套括号) ， 所以sum和expr不是正则表达式。 那么， 词法分析器如何实现像digits这样的正则表达式呢?

解决办法就是在翻译成有限自动机以前，在所有正则表达式出现digits的地方都简单地用右边的式子( [0-9]+ ) 代替。

但这在sum-expr语言中是不可行的， 比如：

expr="("expr"+"expr") " | digits

再用expr的右侧表达式替换expr，如下所示：

expr="("("("expr"+"expr") " | digits) "+"expr") " | digits

现在右边出现expr的次数并没有比以前少， 反而增加了。

因此，简化的概念并没有增强正则表达式的描述能力(因为没有定义附加的语言)，除非简化形式是递归的(或者是相互递归的， 如sum和expr) 。

这种递归附加功能正是在语法分析中所需要的。一旦使用了递归简化形式，就不再需要进行迭代.除非是表达式的首部，因为定义：

expr=ab(c|d)e

可以用附加定义重写：

aux=c d
expr=a b aux e

实际上，为了避免使用交替符号，对于同一符号，这里使用了一些辅助扩充：

aux=c
aux=d
expr=a b aux e

不必使用Kleene闭包， 因为可以将：

expr=(abc) *

重写为：

expr=(abc) expr
expr=epolison

剩余的就是非常简单的表示法，叫做上下文无关文法。

正如正则表达式可以用静态声明的方式定义词法结构一样，文法也可以用声明的方式定义语法结构，但需要比有限自动机更强大的方式来分析文法描述的语言。

实际上，虽然正则表达式完全可以实现，甚至可以更好地完成这项工作，但常常使用文法来描述词法记号结构。

上下文无关文法

前两章中曾经介绍过，语言就是一个字符串集，每个字符串是一个字母表中的确定字符序列。

对于语法分析，字符串就是源程序，符号就是词法记号，字母表就是词法分析器返回的记号类型集。

一个上下文无关文法描述了一个语言。一个文法有如下形式的产生式集：

symbol→symbol symbol...symbol

有0个或多于0个的记号在产生式的右边。这些符号要么是终结符，即描述语言中字符串在字母表中的记号；要么是非终结符，即出现在产生式左边的记号。产生式的左边不会出现终结符的记号。最后，还需要使用一个非终结符作为文法的开始符号。

文法 3.1 是一个直线编程的文法示例。开始符号是 S (当开始符号未明确给出时，习惯上认为第一个产生式左边的非终结符为开始符号)。

此例中终结符为：

id print num+：=；

非终结符为：S，E 和 L，该文法语言的一个句子为：

id：=num； id：=id+(id：=num+num， id)

文法 3.1 直线程序的语法

S-> S:S
S-> id := E
S-> print(L)

E-> id
E-> num
E-> E+E
E-> (S, E)
L-> E
L-> L, E

这里，(词法分析前的)源程序可能是：

a：=7；
b：=+(d：=5+6，d)

(终结符的) 记号类型为id， num，=，等等，名字(a，b，c，d)和数字(7，5，6)对应着一些有语义价值的记号

推导

为了说明句子在某一文法语言中，可以进行如下推导：从开始符号出发，对于任一个非终结符，用其产生式的右侧部分进行替换并重复进行这一操作。

如推导3.2所示。

  • 推导3.2
S'
S；S'
S'；id：=E
id：=E'；id：=E
id：=num； id：=E'
id：=num； id：=E+E'
id：=num； id：=E'+(S， E)
id：=num：id：=id+(S'，E)
id：=num； id：=id+(id：=E'， E)
id：=num； id：=id+(id：=E+E， E')
id：=num； id：=id+(id：=E'+E， id)
id：=num； id：=id+(id：=num+E'， id)
id：=num； id：=id+(id：=num+num， id)

对于同一个句子有很多种不同的推导方式。

最左推导不断地对最左边的非终结符号进行替换；最右推导不断地对最右边的非终结符进行替换。

推导3.2既不是最左推导，也不是最右推导。

句中的一个最左推导如下所示：

S'
S': S
id：=E'：S
id：=num； S'
id：=num； id：=E'
id：=num； id：=E'+E

分析树

分析树就是将推导式中的每个符号同其派生符号连接而成的，如图3.3所示。

两个不同的推导可能生成同一棵分析树

image

二义性文法

若一个文法可以用两棵不同的分析树派生出同一个句子，那么该文法就是二义性的。

文法3.1就是二义性的，因为句子 id := id+id+id 有两棵分析树(参见图3.4)。

image

文法3.5也是二义性文法。图3.6为句子1-2-3生成了两棵分析树，图3.7为1+2*3生成了两棵分析树。

显然，若使用分析树来解释表达式的含义，那么生成句子1-2-3的两棵分析树表达了不同的内容：(1-2)-3=-4和1-(2-3)=2。

同样地，(1+2)x3与1+(2x3)也包含了不同的含义实际上，编译器是使用分析树来导出含义的。

  • 文法3.5
E→id
E→num
E→E*E
E→E/E
E→E+E
E→E-E
E→(E)

image

因此，二义性文法对于编译器来说是不确定的文法。

通常，我们总是希望得到非二义性文法。

非二义性文法

不过，可以将二义性文法转换成非二义性文法。

下面考虑如何生成文法3.5中同样语言的非二义性文法。

首先，设*的优先级高于+，然后，设每个操作符是左结合的，那么就得到了(1-2)-3，而不是1-(2~3)。

引人一些新的非终结符号可以得到文法3.8。

  • 文法3.8
E→E+T
T→T*F 
F→id
E→E-T
T→T/F 
F→num
E→T 
T→F 
F→(E)

符号E，T和F分别代表表达式、项和因子。习惯上，因子用月于乘法，项用于加法。

该文法接收与二义性文法同样的字符集，但是现在每个句 子都对应一个确定的分析树。

文法3.8不会生成如图3.9所示的分析树(参见习题3.7)。

image

若要将*号放于左边，产生式可以写为T→F*T。

消除二义性的通常做法是转换文法，虽然这些文法只是在文法上存在二义性，但是它们在编程时也会出现二义性、因为语义上的二义性可能导致编写程序和理解程序上的问题。

文件结束符

分析器不仅要读人像+.-、num这样的终结符，还要读人全文结束符。

通常使用 $ 符号代表全文的结束设S为文法的开始符号。

为了说明 $ 必须出现在完整的一段S文法之后，需要引人一个新的开始符号 S’ 以及一个新的产生式 S’→S$。

在文法 3.8 中，E是开始符号，修改后的文法参见文法3.10.

  • 文法3.10
S→E$

E→E+T
E→E-T
E→T

T→T*F
T→T/F
T→F

F→id
F→num
F→(E)

参考资料

《现代编译原理 java》