第二章 | Rainnn の Blog

2.1 程序语言的定义

一个程序语言主要由语法和语义两个方面定义。

语法：用来形成和产生一个合式（符合某种范式）的程序的规则，包括词法规则和语法规则。

词法规则是单词符号的形成规则。单词符号一般包括：各种类型的常数、标识符、基本字、算符和界符等。

语法规则是语法单位的形成规则。语法单位包括表达式、语句、分程序、函数、过程和程序等等。

语义：定义每个程序在运行时做什么事情，没有公认的形式系统描述语义。

考语法多一些（语义没有明确定义）

2.2 高级语言的一般特性

2.2.1 强制式语言/过程式语言

FORTRAN, C, Pascal, Ada

2.2.2 应用式语言/函数式语言

LISP,ML

2.2.3 基于规则的语言

Prolog

2.2.4 面向对象语言

C++, Java

数据类型与操作（例：列出三种五种数据类型）

语句与控制结构

2.3 程序语言的语法描述

2.3.1 上下文无关文法

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

根据语法规则可推导出句子（语言）。

上下文无关文法：对每个语法结构的处理与其所在上下文无关。

可用来处理大多数程序语言。

形式化定义

G = (VT , VN , P , S )

：终结符集合：基本符号，也称为token

：非终结符集合：语法成分的符号

P ：产生式集合

产生式(production) 描述了将终结符和非终结符组合成串的方法

α→β

读作：α 定义为β

α∈(VT ∪ VN)+，且α中至少包含VN 中的一个元素：称为产生式的头 (head ) 或左部(left side)

β ∈(VT ∪ VN)* ：称为产生式的体(body)或右部(right side)

S ：开始符号

S ∈ VN 。开始符号(start symbol) 表示的是该文法中最大的语法成分

符号串集合的幂：有符号串集合A，定义：

符号串集合的闭包：设A是符号串集合，定义：

集合A的正闭包：

集合A的闭包：

产生式的简写

对一组有相同左部的α产生式 α→β1 , α→β2 , … , α→βn

可以简记为：α→β1 | β2 | … | βn

读作： α 定义为β1，或者β2， …，或者βn 。

β1，β2， …，βn 称为α 的候选式(Candidate)

符号约定

字母表中排在后面的大写字母（如X、 Y、Z）表示文法符号（即终结符或非终结符）

字母表中排在后面的小写字母（主要是u 、 v、 . . . 、z）表示终结符号串（包括空串）

小写希腊字母，如α、β 、 γ，表示文法符号串（包括空串）默认第一个产生式的左部就是开始符号

终结符 a, b, c 非终结符 A, B, C 文法符号 X, Y, Z

终结符号串 u, v, . . . , z 文法符号串 α, β, γ

推导 (Derivations)和归约 (Reductions)

语言的形式化定义

由文法G 的开始符号S 推导出的所有句子构成的集合称为文法G 生成的语言，记为L(G ) 。即

2.3.2 语义分析树与二义性

文法二义性：可通过不同的推导过程得到同一个句子。

二义性问题是不可判定的。

解决方法：

改写文法使其变为无二义性文法。

确定相应的编译方法。

2.3.3 形式语言分类

去年考了文法分类

乔姆斯基把文法分为四种类型：

0型文法 (Type-0 Grammar)

α → β

无限制文法(Unrestricted Grammar)/短语结构文法

(Phrase Structure Grammar, PSG)

∀α → β∈P， α中至少包含1 个非终结符

0型语言

由0型文法G 生成的语言L(G )

1型文法 (Type-1 Grammar)

α → β

上下文有关文法(Context-Sensitive Grammar , CSG )

∀α → β∈P，｜α｜ ≤ ｜β｜

产生式的一般形式： α1Aα2 → α1βα2 ( β≠ε )

上下文有关语言（ 1 型语言）

由上下文有关文法 (1 型文法) G生成的语言L(G )

CSG 中不包含ε-产生式

（1）式子左边可以有多个字符，但必须有一个终结符
（2）式子右边可以有多个字符，可以是终结符，也可以是非终结符，但必须是有限个字符

2型文法 (Type-2 Grammar)

α → β

上下文无关文法 (Context-Free Grammar, CFG )

∀α → β∈P， α ∈ （非终结符集合）

产生式的一般形式： A→β

上下文无关语言（ 2 型语言）

由上下文无关文法 (2 型文法) G生成的语言L(G )

（1）式子左边只能有一个字符，而且必须是非终结符
（2）式子右边可以有多个字符，可以是终结符，也可以是非终结符，但必须是有限个字符

3型文法 (Type-3 Grammar)

α → β

正则文法 (Regular Grammar, RG )

右线性(Right Linear)文法： A→wB 或 A→w

左线性(Left Linear) 文法： A→Bw 或 A→w

左线性文法和右线性文法都称为正则文法

（1）式子左边只能有一个字符，而且必须是非终结符
（2）式子右边最多有二个字符，而且如果有二个字符必须是一个终结符和一个非终结符
（如果只有一个字符，那么必须是终结符）
（3）式子右边的格式一定要一致，也就是说如果有一个是（终结符+非终结符）那么所有的式子都必须是（终结符+非终结符）；如果有一个是（非终结符+终结符），那么所有的式子都必须是（非终结符+终结符）