第三章 高级程序设计语言的语法描述

1 文法

文法： 描述语言的语法结构的形式规则。

例：He gave me a book.
<句子> → <主语><谓语><间接宾语><直接宾语>
<主语> → <代词>
<谓语> → <动词>
<间接宾语> → <代词>
<直接宾语> → <冠词> <名词>
<代词> → He
<代词> → me
<名词> → book
<冠词> → a
<动词> → gave

2 语法描述的几个基本概念

字母表：一个有穷字符集，记为∑
字母表中每个元素称为字符
∑上的字(也叫字符串) 是指由∑中的字符所构成的一个有穷序列
不包含任何字符的序列称为空字，记为ε
用∑*表示∑上的所有字的全体，包含空字ε
∑*的子集U和V的连接（积）定义为UV＝{ αβ | α∈U & β∈V }
V自身的n次积记为Vn=V V … V
V0={ε}
V*是V的闭包： V=V0∪V1∪V2∪V3∪…
V+是V的正规闭包：V＋＝V V

3 上下文无关文法

上下文无关文法G是一个四元组G=(VT，VN，S，P)，其中
VT：终结符(Terminal)集合(非空)
VN：非终结符(Noterminal)集合(非空)，且VT ∩ VN=Ø
S：文法的开始符号，S∈VN
P：产生式集合(有限)，每个产生式形式为
P→α， P∈VN， α ∈ (VT ∪ VN)*
开始符S至少必须在某个产生式的左部出现一次

例，定义只含+，*的算术表达式的文法
G=< {i，+，*，(，)}，{E}，E， P >， 其中，P由下列产生式组成：
E → i
E → E+E
E → E*E
E → (E)

4 最左推导、最右推导、语法树

最左推导：任何一步α⇒β都是对α中的最左非终结符进行替换
最右推导：任何一步α⇒β都是对α中的最右非终结符进行替换
用一张图表示一个句型的推导,称为语法树

5 二义性(ambiguity)

文法的二义性：如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的
G(E)： E → i|E+E|E*E|(E) 是二义文法
语言的二义性：一个语言是二义的，如果对它不存在无二义的文法

6 不论是程序设计语言还是自然语言，都可能有二义性，也称为歧义。请你针对某个程序语言或者自然语言，例举其中的二义性的例子。

英语是一种二义性的语言，介词短语较易引起歧义。如“Tom saw Sam at the boat.”既可理解为Sam在船上，也可理解为Tom在船上。

但中文却不存在这样的歧义，“Tom看到Sam在船上”就是指Sam在船上。如果是Tom在船上就会表示为“Tom在船上看到Sam”。原因是中文附加了一些语法规则，会将介词短语的指代方指向前面的语法成分。因此可以通过增加规则消除二义性。因此在常见的高级程序语言中，较少见到二义性的例子。