编译原理笔记02-程序设计语言及其文法

基本概念

字母表

字母表Σ是一个有穷符号集合

符号：字母、数字、标点符号、……

【例】字母表

二进制字母表：{0，1}
ASCII字符集
Unicode字符集

字母表上的运算

字母表Σ相乘：{0，1} {a，b} = {0a，0b，1a，1b}
字母表Σ次幂：{0，1} ³ = {0，1} {0，1} {0，1} = {000，001，010，011，100，101，110，111}
字母表Σ闭包：{a，b，c，d} ⁺ = {a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc，……}
字母表Σ克林闭包：{a，b，c，d} ^* = {ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc，……}(闭包基础上多了个空串)

ε，表示空串

串

字母表Σ克林闭包中的每一个元素都称为是字母表Σ上的一个串
串s的长度，记作|s|，指串中符号的个数

串上的运算

连接：x和y的连接就是把y附加到x后面形成的串，记作xy
- 【例】若x=dog，y=house，则xy=doghouse
- 空串ε是连接运算的单位元，可看作1。对于任意串，εs=sε=s
- 设x，y，z是三个字符串，如果x=yz，则称y是x的前缀，z是x的后缀
幂：串s的n次幂就是将n个s连接起来
- 【例】若s=ba，则s¹=ba，s²=baba，s³=bababa，……

文法的定义

什么是文法

图中第一个规则表示：一个句子应该由一个名词短语连接动词短语构成。
图中第二个规则表示：一个名词短语应该由一个形容词连接名词短语构成。

从上面自然语言的例子中可以提取出文法的一些组成要素。

尖括号括起来的部分称为语法成分
未用尖括号括起来的部分称为语言的基本符号

因为该文法是用来描述句子的构成规则的，所以该文法的基本符号是单词；如果一个文法是用来描述单词的构成规则的，那么该文法的基本符号就是字母。

简而言之，文法就是一套语言规则。

文法的形式化定义

文法用大写字母G表示，把一个文法G定义为一个四元组

G=(V_T，V_N，P，S)

V_T：终结符集合
- 终结符(terminal symbol)是文法所定义的语言的基本符号，有时也称为token
- 【例】上例中文法用来描述句子的构成规则，，所以该文法的基本符号是单词。V_T={apple，boy，eat，little}
V_N：非终结符集合
- 非终结符(non terminal)是用来表示语法成分的符号，有时也称为"语法变量"。因为可以用由它们推导出其他语法成分，所以叫做非终结符。
- 【例】上例中文法的V_N={<句子>，<名词短语>，<动词短语>，<名词>，……}
- V_T∩V_N=Φ，即V_T和V_N不相交；V_T∪V_N=文法符号集，即V_T并上V_N构成文法符号集
P：产生式集合
- 产生式(production)描述了将终结符和非终结符组合成串的方法
- 产生式的一般形式：α→β，读作α定义为β
- α∈(V_T∪V_N)⁺，且α中至少包含V_N中的一个元素：称为产生式的头或左部
- β∈(V_T∪V_N)^*：称为产生式的体或右部
- 【例】上例中文法的每一个规则都是一个产生式
S：开始符合
- S∈V_N。开始符号(start symbol)表示的是该文法中最大的语法成分
- 【例】上例中文法的开始符号S是句子。S=<句子>

【例】算术表达式的文法

文法可简写为只写产生式

产生式的简写

对一组有相同左部的α产生式：$α→β1，α→β2，……，α→βn$
可以简记为：$α→β1|β2|……|βn$
读作：α 定义为 β1，或者 β2，……，或者 βn
β1，β1，……，β1 称为 α 的候选式(Candidate)

【例】产生式E的简写

符号约定

为了避免总是要声明哪些是终结符，哪些是非终结符的麻烦。我们对符号的使用做一些约定。

符号	约定	例如
终结符	字母表中排在前面的小写字母；运算符；标点符号；数字；粗体字符串	a，b，c；+，*；括号、逗号；id、if
非终结符	字母表中排在前面的大写字母；字母S，通常表示开始符号；小写、斜体的名字；代表程序构造的大写字母	A，B，C；expr、stmt；E(表达式)、T(项)和F(因子)
文法符号	字母表中排在后面的大写字母	X，Y，Z
终结字符串	字母表中排在后面的小写字母	u，v，……，z
文法符号串	小写希腊字母	α，β，γ

除非特别说明，否则第一个产生式的左部就是开始符号。即文法中第一个产生式的左部是该文法最大的语法成分。

语言的定义

推导与归约

给定文法G=(V_T , V_N , P , S )，如果 α→β ∈ P，那么可以将符号串 γαδ 中的 α 替换为 β。
也就是说，将 γαδ 重写(rewrite)为 γβδ，记作 γαδ ⇒ γβδ。
此时，称文法中的符号串 γαδ 直接推导(directly derive)出 γβδ

简而言之，就是用产生式的右部替换产生式的左部

【例】推导与归约

从图中可以看到，从<句子>可以推导出little boy eats apple，逆过程就叫归约。
推导就是用产生式的右部替换产生式的左部
规约就是用产生式的左部替换产生式的右部

有了文法（语言规则），如何判定某一词串是否是该语言的句子？

句子的推导——从生成语言的角度
句子的归约——从识别语言的角度

语言的形式化定义

由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言，记为L(G)。即，L(G)= {w | S ⇒* w, w∈ V_T* }
文法解决了无穷语言的有穷表示问题。

文法的分类

根据对文法中产生式的不同要求，可将文法分为四种类型

0型文法(无限制文法/短语结构文法)

$$α→β$$

无限制文法/短语结构文法(Phrase Structure Grammar, PSG )
- $∀α→β∈P，α中至少包含一个非终结符$
0型语言
- 由0型文法G生成的语言L(G)

1型文法(上下文有关文法)

$$α→β$$

上下文有关文法(Context-Sensitive Grammar , CSG )
- $∀α→β∈P，|α|≤|β|$，即产生式左部的符号个数不能多于右部的符号个数
- 产生式的一般形式：$α1Aα2→α1βα2 (β≠ε)$，即非终结符A只有当它的上下文是α1α2的的时候，才能替换为β。因此是上下文有关文法。
- 可以看出，CSG中产生式右部不能是空串。即CSG中不包含ε-产生式(空产生式)
上下文有关语言(1型语言)
- 由上下文有关文法(1型文法)G生成的语言L(G)

2型文法(上下文无关文法)

$$α→β$$

上下文无关文法(Context-Free Grammar, CFG )
- $∀α→β∈P，α∈V_N$，即产生式左部必须是非终结符
- 产生式的一般形式：$A→β$，前文提到过符号约定非终结符为A。即将A替换为β不需要考虑它的上下文。
上下文无关语言(2型语言)
- 由上下文无关文法(2型文法)G生成的语言L(G)

3型文法(正则文法)

$$α→β$$

正则文法 (Regular Grammar, RG )
- 右线型文法：A→wB或A→w，在2型文法基础上，对产生式右部进行限制，要么是一个终结符号串w，要么是一个终结符号串w右边有一个非终结符B
- 左线型文法：A→Bw或A→w，在2型文法基础上，对产生式右部进行限制，要么是一个终结符号串w，要么是一个终结符号串w左边有一个非终结符B
- 可以观察出，正则文法的产生式左部只能有一个非终结符
正则语言(3型语言)
- 由正则语言(3型文法)G生成的语言L(G)
正则文法能描述程序设计语言的多数单词

四种文法之间的关系

逐级限制
- 0型文法：α中至少包含一个非终结符
- 1型文法(CSG)：|α|≤|β|
- 2型文法(CFG)：α ∈ V_N
- 3型文法(RG)：A→wB 或 A→w (A→Bw 或A→w)
逐级包含

CFG的分析树

根节点的标号为文法开始符号
内部结点表示对一个产生式A→β 的应用，该结点的标号是此产生式左部A 。该结点的子结点的标号从左到右构成了产生式的右部β
叶结点的标号既可以是非终结符，也可以是终结符。从左到右排列叶节点得到的符号串称为是这棵树的产出( yield )或边缘(frontier)