Chapter_02.md

第2章 文法和语言的基本知识

2.1 概 述

语法，语义，语用：

名称	作用	针对赋值语句 s = 2*3.14*r*(r+h) 非形式化描述
语法	对语言结构的定义	赋值语句由** 变量 赋值号 表达式** 构成
语义	描述了语言的含义	计算右部表达式的值，将结果送入左部变量
语用	从使用角度描述语言	赋值语句可用于计算和保存表达之的值

2.2 字母表和符号串的基本概念

2.2.1 字母表和符号串

基本概念：

名称	概念
字母表	元素的非空有穷集合。 例如: ∑ = {a, b, c} 其中 ∑ 是字母表，它由 a,b,c 3个元素组成。
符号(字符)	字母表中的元素称为符号，或者字符。
字符串(字)	符号的有穷序列称为符号串。 特点： 有穷， 顺序不同的字符串不同，不包含任何符号的串称为空串。 **空串用 ε 表示，即空符号串由0个元素组成，其长度

2.2.2 符号串运算

名称	释义
符号串的连接	设x和y是符号串，则串xy称为它们的连接。
集合的乘积	设A和B是符号串的集合，则A和B的乘积定义为 AB = { xy | x ∈ A， y∈ B }
符号串的幂运算	x0 = ε x1 = x x2 = xx ... xn = x xn-1(n > 0)
集合的幂运算	A0 = {ε} A1 = A A2 = AA ... An = A An-1(n > 0)
集合A的 正闭包A+ 与闭包A*	设A是符号串的集合，则: A+ = A1 ∪ A2 ∪ A3 ∪... A* = A0 ∪ A1 ∪ A2 ∪... = {ε} ∪ A+

2.3 文法和语言的形式定义

2.3.1 形式语言

形式语言 : 序列的集合，不考虑语义。

对形式语言描述的两种方法:

1.当语言为有穷集合时: 用枚举法。

2.当语言为无穷集合时: 节点递归函数和数学归纳法思想。

2.3.2 文法的形式定义

1.规则

规则也称产生式，它是一个符号与一个符号串的有序对(A, β) 通常写作：

A → β (或 A ::= β)

字符	含义
A	规则左部，它是一个符号。
β	规则右部，它是一个符号串。
→ 和 ::=	表示“定义为” 或 “生成”，即左部符号用右部的符号串定义 或 左部符号生成右部符号串。