语言的定义

语言 = 语法 + 语义

语法

语法是用以构造程序及其成分（语法单位）的规则的集合。

术语

字母表：语言允许使用的字符的集合，其元素称为字符（终结符）。

符号：由字符组成的字符串。

字汇表：由符号组成的集合，其元素称为字，如关键字表。

词法规则：规定什么样的字符序列可以构成语言的有效符号（单词符号）。

语法规则：确定一个符号序列是否为一个句子，并提供句子的结构，即确定什么样的符号序列是合法的。

语义

语义是用以规定语法正确的语法单位的作用和意义的规则的集合。

程序设计语言是用来描述计算机所执行的算法的形式表示

定义语言的两种观点

生成（文法）

文法：在形式语言中，上述例子可写成文法。

标识符：

表达式（算术）

识别（语法图）

语法图的构造：

语法描述方法等价

文法和语法图是语言语法的等价表示，采用生成的方法还是采用识别的方法来定义语言由语言的设计者确定。

• 文法从产生的观点来定义语言的语法，更通用、准确；
• 语法图从识别的观点来定义语言的语法，更直观、清晰。

语法描述的用途

• 表达语言设计者的意图和设计目标；
• 指导语言的使用者编写正确的程序；
• 指导语言的实现者编写语法检查程序来识别所有的语法单位。

抽象机GAM

以一个抽象机的行为来描述语言的各个结构的作用和意义。

以GAM 的操作行为来定义语言的语义，是基于已经 “理解 ”GAM 的语义；
因此，一旦用 GAM 的操作行为来定义语言结构的作用时，就知道了语言的意义 。
为了成功地运用这个方法，GAM自身的语义应该尽可能的简单，以便于把问题集中于语言的语义上，而不是抽象机自身的复杂性上。

组成

抽象机GAM由存储器、控制器、处理器、指令指针ip组成，存储器分为代码区（段）和数据区（段）。

ip的内容是代码区单元的地址，该单元的内容是一条指令。

工作流程

文法

文法理论

引例：如何导出“我是大学生”？

规则：

有了一组规则以后， 不断地用→的右边代替左边，就可以导出句子：

文法的定义

文法是描述语言的语法结构的形式规则，必须准确，易于理解，且描述能力强。

文法G定义成一个四元式：G=(V_T ,V_N ,S,P)

其中，V_T 是终结符的有限集合，V_N 是非终结符的有限集合，S是开始符号，S∈V_N；P是产生式的非空有限集。

产生式

产生式是一对有序偶对（α，β），记为：α::=β或α→β
其中，α和β是由终结符、非终结符组成的串，且α至少应含有一个非终结符。

产生式的简化：

• 用英文大写字母表示非终结符；
• 小写字母表示终结符；
• 希腊小写字母表示串。

文法的表示

描述文法，直接给出产生式集合即可。

文法的分类

0型文法

0型文法又称短语文法，它的能力相当于图灵机（计算机的一种简单的理论模型）。

0型文法的产生式形如：α→β
其中，α和β是由终结符、非终结符组成的串，且α至少应含有一个非终结符。

1型文法

1型文法又称上下文有关文法。

上下文有关就是对非终结符进行替换时必须考虑上下文。

2型文法

2型文法又称上下文无关文法。上下文无关就是对非终结符进行替换时可以不考虑上下文。由于这种文法对程序已基本可以描述，因此，上下文无关文法常简称为文法。

2型文法的产生式形如：A→α

3型文法

3型文法又称正则文法、右线性文法。

3型文法的产生式形如：A→α 或 A→αB
其中，A、B ∈ V_N ，α ∈ V_T*。

文法产生的语言

推导与归约

符号

推导过程

最右推导过程是规范的推导过程。

最左推导过程

最右推导过程

句型和句子

句子是只含终结符的句型

文法产生的语言

文法G=(V_T ,V_N ,S,P)产生的所有句子的集合，称为由文法G产生的语言，记为L(G)，即：




文法的重要特征：有限规则描述无穷语言。

文法等价

两个文法G和G’，如果有L(G)=L(G’)，则称G和G’等价。

语法树（推导树）

以图的方式表示推导过程

• 语法树是一颗有序的标记树，每个节点的标记是文法G的终结符或非终结符；
• 标记为A的内部结点从左到右有子节点X₁，X₂，…，X_n，则A→X₁…X_n是一个产生式；
  
• 语法树的构造过程是从文法的开始符号出发，构造一个推导的过程；
• 因为文法的每一个句型（句子）都存在一个推导，所以文法的每个句型（句子）都存在一棵对应的语法树；

边缘

推导树的边缘是一棵推导树所有叶节点的从左到右的连接。

文法的二义性

一个句子有两棵不同的推导树。

子树与简单子树

语法树的子树是由某一结点连同所有分枝组成的部分。

语法树的简单子树是指只有单层分枝的子树（只有父子两代）。