程序语言的语法描述
一、几个重要概念
字母表和符号串
(1)字母表 alphabet
字母表是元素的非空有穷集合。
【例如】 ∑ = {a,b,c}
∑是字母表，由 a,b,c 三个元素组成。
字母表中至少包含一个元素，字母表中的元素，可以是字母、数字或其他符号。
不同的语言有不同的字母表。
英文的字母表是26个字母、数字和标点符号的集合;C 语言的字母表是字母、数字和若干专用符号组成。
(2)符号(字符)symbol
字母表中的元素称为符号，或称为字符。
【例如】 ∑ = {a,b,c}
a,b,c 是字母表 ∑ 中的符号。
(3)符号串(字)string
符号的有穷序列称为字符串。
【例如】设有字母表 ∑ = {a,b,c}，
则有符号串 a,b,ab,ba,cba,abc,…
(a,b,ab,ba,cba,abc 等都是字母表∑上的符号串)
符号串总是建立在某个特定字母表上的且只能由字母表上的有穷多个符号组成。
符号串中符号的顺序是很重要的，如 ab 和 ba 是字母表∑上的两个不同的符号串。
不包含任何符号的符号串，称为空符号串，用 ε (epsilon)表示，即空符号串由 0 个符号组成，其长度 |ε| = 0
下面看看符号串的运算：
(1)符号串的连结 catenation
设 x 和 y 是符号串，则串 xy 称为它们的连结。即 xy 是将 y 符号串写在 x 符号串之后得到的符号串。
【例如】设 x = abc，y = 10a，
则 xy = abc10a
则 yx = 10aabc
特别，对任意一符号串 x 有：
εx = xε = x
(2)集合的乘积 product
设 A 和 B 是符号串的集合，则 A 和 B 的乘积定义为：
AB = {xy | x ∈ A, y ∈ B}
即集合 AB 中的符号串是由 A 和 B 的符号串连接而成的。
【例如】设 A = {a,b}, B = {c,d}
则 AB = {ac,ad,bc,bd}
因为对任意一符号串 x 有：
εx = xε = x
所以，对任意集合 A，有 {ε}A = A{ε} = A
这里要说一下 空集 Φ empty set
Φ 表示不含任何元素的空集 { }
Φ = { }
注意： ε是符号串，不是集合
{ ε} 表示由空符号串 ε 所组成的集合，但这样的集合不是空集Φ， 即Φ不包含空串。 ε ∈ Φ
(3)符号串的幂运算 power
(4)集合的幂运算
(5)集合A的正闭包A+与闭包A*
正闭包：Positive closure
闭包 ：Star closure(星闭包)
二、上下文无关文法
(1)形式语言
序列(字符串)的集合称为形式语言。
每个形式语言都是某个字母表上按某种规则构成的所有符号串的集合;任何一个字母表上符号串的集合均可定义一个形式语言。
【例如】
C 语言是具有基本符号字母表上的符号串的集合。每个 C 语言程序是基本符号的符号串。
形式语言的描述有两种方法：
第一种方法是当语言为有穷集合时，用枚举法来表示语言。
【例】设有字母表 A={a,b,c},则
L1 = {a,b,c}
L2 = {a,aa,ab,ac}
L3 = {c,cc}
均表示字母表 A 上的一个形式语言。
由于这三个语言均是有限符号串的集合，可以枚举出其全部句子来表示该语言。
第二种是 当语言为无穷集合时，需要设计文法来描述无穷集合的语言。
文法是一种形式规则
(2)文法的形式定义
1、规则
规则的作用是告诉如何用规则中的符号串生成语言中的序列。一组规则规定了一个语言的语法结构。
产生式中的符号
非终结符：非终结符号(也称语法变量)用来代表语法范畴。例如，“算术表达式”、“布尔表达式”、“賦值句”、“分程序”、“过程”等，它们都是现今程序语言常见的语法范畴。出现在产生式左部能派生出符号或符号串的那些符号，即每个非终结符表示一定符号串的集合。用大写字母表示或用尖括号把非终结符括起来。
终结符：是不属于非终结符的那些符号，它是组成语言的基本符号，是一个语言的不可再分的基本符号，只出现在产生式右部。通常用小写字母表示。
2、文法
VT 可以理解成一个符号的集合，就像英语的单词。
VN 可以理解成语法单位的集合 就像英语的语法单位，比如主语、谓语。
S是文法的开始符号。
每一条规则是一条产生式，所有的规则的集合记成P。
产生式(也称产生规则或简称规则)是定义语法范畴的一种书写规则。
3、语言的形式定义
(1)直接推导
(2)推导
4、广义推导
直接推导的长度为1，推导的长度大于等于1，广义推导的长度大于等于0
5、句型和句子
仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言。
6、语言
7、规范推导和规范归约
文法所定义的任一句型和句子，都可以根据文法推导出来，但同一个句型(句子)可以通过不同的推导序列推导出来，这是因为在推导过程中所选择非终结符的次序无关。
最左推导是指对于一个推导序列中的每一步直接推导 α=>β，都对 α 中的最左非终结符进行替换。
最右推导是指对于一个推导序列中的每一步直接推导 α=>β，都对 α 中的最右非终结符进行替换。
最右推导也称为规范推导，用规范推导推导出的句型称为规范句型。
每个句子都有规范推导，但对句型此结论并不成立。
归约是推导的逆过程，归约是与推导相对的概念，推导是把句型中的非终结符用规则的一个右部来替换的过程，而归约是句型中的某个子串用一个非终结符来替换的过程。
规范推导的逆过程，称为最左归约，也称为规范归约。
8、递归规则与文法的递归性
所谓递归规则，是指在规则的左部和右部具有相同的非终结符的规则。
如果文法中有规则 A→A… 称为规则左递归。
如果文法中有规则 A→…A 称为规则右递归。
如果文法中有规则 A→…A… 称为规则递归。
文法的递归性，是指对文法中任一非终结符，若能建立一个推导过程，在推导所得的符号串中又出现了该非终结符本身，则文法是递归的，否则是无递归性的。
文法中使用递归规则，使得能用有限的规则去定义无穷集合的语言。
下面的情况比较特殊：
文法中使用了递归规则，使得可用有限的规则去刻画无穷集合的语言。
若不用递归规则来定义文法，需要用无穷多条规则去表示无穷集合的语言。
当一个语言是无穷集合时，则定义该语言的文法一定是递归的。
程序设计语言都是无穷集合，因此描述它们的文法必定是递归的。
9、短语、直接短语和句柄
短语、直接短语和句柄 是后面章节的内容，这里不懂没关系。
首先看一下短语和直接短语。
短语是句型的一部分。
句柄
一个句型的最左直接短语称为该句型的句柄。
句柄特征：
(1)它是直接短语，即某规则右部
(2)它具有最左性。
注意：
短语、直接短语和句柄都是针对某一句型的，特指句型中的哪些符号串能构成短语和直接短语，离开具体的句型来谈短语、直接短语和句柄是无意义的。
三、语法树与文法的二义性
1、推导树的生成
(1)语法树的生成
语法树的构造是从文法的开始符号出发，构造一个推导的过程，因为文法的每一个句型(句子)都存在一个推导，所以文法的每个句型(句子)都有一棵对应的语法树。
举个例子：
方法一：
以识别符号作为根结点，从它开始对每一步直接推导向下画一分支，分支结点的标记是直接推导中被替换的非终结符的名字，按此方法逐步向下，画出每一步直接推导对应的分支直到对该语法树再无分支可画时，构造过程结束。
方法二：
语法树中从左到右的末端结点构成了有该语法树所表示的那个推导推出的符号串。
句型 (i+i)*i-i 的最左、最右推导得到的语法树完全相同，
也就是说，一棵语法树表示一个句型的种种可能的(但未必是所有的)不同推导过程。
(2)子树
语法树的子树是由某一个结点连同所有分支组成的部分。
(3)简单子树
语法树的简单子树是指只有单层分支的子树。
(4)子树与短语的关系
根据子树的概念，句型的短语、直接短语和句柄的直观解释如下：
短语：子树的末端结点形成的符号串是相对于子树根的短语。
直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语。
句柄：最左简单子树的末端结点形成的符号串是句柄。
【例】对文法G[E]，用语法树求句型(T+i)*i-F 的短语、直接短语和句柄。
2、文法的二义性
对应文法 G 中任一句型的推导序列，总能构造一棵语法树。
文法 G[E]：E→ E + E | E﹡E | (E) | i
该文法的一个句子 i*i+i 有两个不同的最左推导，对应两棵不同的语法树。
如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。也就是说，若一个文法存在某个句子，它有两个不同的最左推导或有两个不同的最右推导，则称这个文法是二义的。
二义性的文法将给编译程序的执行带来问题。对于二义性文法的句子，当编译程序对它的结构进行语法分析时，就会产生两种甚至多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。
解决方法之一：利用文法的等价性来消除文法的二义性。
3、文法二义性的消除
(1) 不改变文法中原有的语法规则，仅加进一些语法的非形式规定。
【例】文法 G：E → E + E | E﹡E | (E) |i
不改变已有的四条规则，仅加进运算符的优先顺序和结合规则，即 * 优先+，+、* 服从左结合。
这样，对于文法 G[E] 中的句子 i*i+i 只有唯一的一棵语法树，从而避免了文法的二义性。
(2) 构造一个等价的无二义性文法;即排除二义性的规则，改写原有的文法。
例如，文法 G：E → E + E | E﹡E | (E) |i
想要让一个规则结合性弱;就让它出现在推导序列前面(语法树的上层);
想要让一个规则结合性强;就让它出现在推导序列后面(语法树的下层);
具体做法：引入非终结符
语言的二义性是指不存在一个无二义的文法 G，使得L(G)就是语言本身。
注意：文法的二义性和语言的二义性是两个不同的概念。可能有两个不同文法的 G 和 G’，其中一个是二义的而另一个是无二义的，但是有 L(G) = L(G’)。
对于一个程序语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。
二义性问题是不可判定的。即不存在一个算法，能在有限步骤内确切的判定一个文法是否为二义的。
4、文法和语言的分类
Chomsky 于 1956 年建立形式语言的理论，形式语言的理论发展得很快。
对计算机科学有着深刻的影响; 特别是对如下方面有重大的作用：程序语言的设计；编译方法；计算复杂性。
Chomsky把文法分成四种类型， 即 0型、1型、2型和3型。 这几类文法的差别在于对产生式的形式施加的限制从 0型到 3型依次增强，但它们表达语言的能力则依次减弱。
0 型文法(无限制文法，短语文法)
由定义可见，α 和 β 均是文法的终结符和非终结符组成的符号串，且 β 可能为空，而 α 不能为空，即允许 |α|>|β|。
由于 0 型文法没有加任何限制条件，故又称为无限制文法，相应的语言称为无限制语言。
非终结符 A 永远消不掉，不能终结。
1 型文法(上下文有关文法)
在推导过程中，连续 n 个 a 一直是最前面，不能生成连续 n 个 b 和紧跟 n 个 c，但是可以生成相互间隔的 n 个 B 和 c。
使用规则 cB→Bc 可以将所有穿插的 c 中的B 向前移。
然后使用规则 bB→bb 消除掉所有的 B。
aaabbbccc 的推导过程。
最左推导：
规则 cB→cc和 bB→bc 是把 B 换成 c。
规则 cA→Ac 是把穿插的 c 中的 A 向前移。
最终使用规则 bA→bb 消除掉所有的 A，换成 b。
2 型文法(上下文无关文法)
由定义可见，利用规则将 A 替换成 β 时，与 A 的上下文环境无关，即无需考虑 A 在上下文中出现的情况。
故又称为上下文无关文法，相应的语言称为上下文无关语言。
通常定义程序设计语言的文法是上下文无关文法，因此，上下文无关文法及相应语言是我们主要的研究对象。
有 a 就有 B
有 b 就有 A
或： S → aB | bA A → a | aS | Sa B → b | bS | Sb
3 型文法(正规文法)
右线形文法和左线形文法都称为 3 型文法或正规文法， 3型文法描述的语言称为 3 型语言或正规语言。
通常定义程序设计语言词法规则的文法是正规文法。
通过几个特殊的例子来体会语言与文法的关系。
有关文法的使用限制和变换。
作为程序语言的上下文无关文法，对它们限制以下几点：
第二点限制的解释
(2’)
每个非终结符 P 必须都有用处。这一方面意味着，必须存在含 P 的句型;也就是从开始符号 S 出发，存在推导 S > αPβ.。
以后所讨论的文法均假定满足上述两个条件。这种文法称为化简了的文法。
若程序设计语言的文法含有多余规则，其中必定有错误存在，因此检查文法中是否含有多余规则是很重要的。
以上就是有关程序语言的语法描述的相关介绍，无论是初入程序还是程序的专家，都可以通过学步园进行更深入的了解程序语言的知识。