程序语言的设计
1. （程序设计）语言的定义
语言=语法（规则）+语义（规则）
语法：构造程序及其成分（单词、语法单位）的规则集合
语义：定义语言的单词符号和语法单位的作用和意义的规则组合
可以从生成（文法）和识别（语法图）的角度描述语法
1.1 文法描述语法规则：生成角度
<标识符>→<字母>
<标识符>→<标识符><字母>
<标识符>→<标识符><数字>
<字母>→A|…|Z|a|…|z
<数字>→0|…|9<表达式>→<标识符>
<表达式>→(<表达式>)
<表达式>→<表达式><运算符><表达式>
<运算符>→+|-|*|/注意：这里没有考虑运算符的优先级
1.2 语法图描述语法规则：识别角度
识别原则：
- 终结符框:标识的终结符与被识别的终结符刚好符合
- 非终结符框:由该非终结符的语法图识别
- 分支:若遇到分支，则任选一分支识别；
- 回溯:若一个分支识别不成功，则选另一分支识别
- 若一个终结符序列是合法的：
那么,必须从语法图的入口边通过语法图而到达出口边，
且在通过的过程中,恰恰能识别该终结符序列。 - 语言：语法图能识别的所有终结符序列的集合。称为语言。
语法图的构造
1.3 高级语言语法规则描述方法
FORTRAN采用自然语言描述语法；
ALGOL 60首次用BNF对语法进行形式描述,为语言定义做出了重要贡献；
Pascal首次采用语法图来定义语言，给出了较为直观的语法结构。1.4 语法描述方法等价
文法和语法图是语言语法的等价表示
文法从产生的观点来定义语言的语法，通用性好。
语法图以识别的观点定义语言的语法，更直观和清晰。1.5 语法的作用
①表达语言设计者的意图和设计目标；
②指导语言的使用者编写正确的程序；（先使用语义规则后使用语法规则）
③指导语言的实现者识别所有语法单位。（先使用语法规则后使用语义规则）本章语义使用自然语言描述、下篇语义以操作语义学的方法描述
2. 文法
定义：文法是描述语言语法结构的形式规则
优点：通用、准确、易于理解、描述能力强
文法G是一个四元式，G=（V
T，VN，S ，P ）V
T是有限字符的集合，元素称为字母或者终结符V
N是有限字符的集合，元素称为变量或非终结符S∈V，称为文法的开始符号
P是产生式α->β的集合
α∈(V
TU VN)^+^ ，至少包含一个非终结符，α∈V^^ VNV^^β∈(V
TU VN)^*^α->ε，称为空串产生式或者ε产生式
2.1 候选式
2.2 文法的分类
0型文法（PSG）
α->β
1型文法（上下文有关文法CSG）
|α|<=|β| （S->ε例外）
标准形式：
yAz->yωz
其中：
A∈V
N;y,z∈(V
TU VN)^*^ ;ω∈(V
TU VN)^+^ ;（S->ε例外）
2型文法（上下文无关文法CFG）
A->β
3型文法（正则文法RG，或右线性文法RLG）
A->u或A->wB
其中u∈V
T^*^ ，w∈VT^+^
3. 文法产生的语言
3.1 推导与归约
直接推导
wαv=>wβv，即由产生式右边替换产生式左边
任意步推导
y=>^*^ z
多步推导
y=>^+^ z
eg：已知文法G（E）
E->E+E|E*E|(E)|i
i+i*i的（其中一种）最左推导过程
E=>E+E=>i+E=>i+E*E=>i+i*E=>i+i*i
E=>E*E=>E+E*E=>i+E*E=>i+i*E=>i+i*i
i+i*i的最右推导（规范推导）
E=>E+E=>E+E*E=>E+E*i=>E+i*i=>i+i*i
E=>E*E=>E*i=>E+E*i=>E+i*i=>i+i*i
3.2 句型和句子
文法G=（V
T,VN,S,P）S=>^*^ w
若w∈V^*^ ，则w为文法G的一个句型
若w∈V
T^*^ ，则w是一个句子（只含终结符的句型就是一个句子）
所有句子的集合称为文法G产生的语言记为L（G）
即L（G）={α|S=>^+^ α且α∈V
T^*^ }
3.3 文法的重要特性
有限规则描述无穷语言
3.4 文法等价
两个文法G和G^’^ ，如果有L（G）=L（G^’^ ），则称G和G^’^ 等价
4. 推导树（语法树）
定义：推导树是一颗有序的标记树，每个结点的标记是文法G的非终结符或终结符或空串ε。其中标记为A的内部结点从左到右有子结点x1、x2、……xn，则A->x1……xn是一个产生式。
4.1 推导树的边缘
定义：推导树所有叶节点从左到右的连接
4.2 文法的二义性
定义：一个句子有两颗不同的推导树
4.3 短语、直接短语、句柄
详见第八章
5. 语言的设计
eg：
表达式的设计：
- 逻辑表达式
- 关系表达式
- 算术表达式
