语言概述
语言是由句子组成的集合，是由一组符号所构成 的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体 每个句子构成的规律 研究语言 每个句子的含义 每个句子和使用者的关系
研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法 Syntax 语义 Semantics 语用 Pragmatics
例子：X=AB,A→a,B→b ABaBab + 即：AB ab
* 3、星推导:x y(当且仅当x=y或x
y)。 例子：ABAB 0步 ABaB 1步 + AB ab 2步 * 即：AB ab
+
4、句型：称x为句型，若有Z x，其 中Z是文法的开始符。凡是由初始符推 出的任意符号集合叫句型。 * 例子：Z→AB,A→a,ZaB * 5、句子: 称x为句子，若有Z x，且 x中不包含非终极符的句型。不包含非 终极符的句型叫句子。
如果不考虑语义和语用，即只从语法这 一侧面来看语言，这种意义下的语言称作形 式语言。形式语言抽象地定义为一个数学系 统。“形式”是指这样的事实：语言的所有 规则只以什麽符号串能出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结 构及其特性的研究。是程序设计语言语法分 析研究的基础。
例子:整数(1)单个数字是整数 (2)整数再接上数字仍是整数 用BNF范式表示:
*
例子：G[S]:S→0S1 S→01 解: S0S1 00S11 000111 所以有:S={01,0011,000111…} L(G)={0n1n|n≥1}
6、语言:所有句子的集合称为语言。 设是G给定文法，Z是开始符，则语言 L(G)可描述如下：
* L(G)=｛x|Z x,x∈VT*｝
例子：判定字符串a4y是<标识符> <标识符><标识符><字母> <标识符>y <标识符><数字>y <标识符>4y <字母>4y a4y
2、语法图 作用：直观、形象的描述语法规则。 例子：标识符的语法图表示
标识符
字母 字母
数字
例子：无符号数的语法图表示 2.45E+12 无符号数 无符号整数 E
9、正闭包：设A为符号串集，则用A 表 示A的正闭包，其具体定义如下： A+=A1∪A2∪A3∪… 例如：A={a},A+={a,aa,aaa,……} 10、星闭包：设A为一集合，则定义A 的星闭包为A* ，其具体定义如下 A*=A0∪A+ 例如：A={a},A*={ε,a,aa,aaa,……}
7、乘积：设A和B是符号串集，则用AB 表示A和B的乘积。 A={a,b},B={c,d},则AB={ac,ad,bc,bd} 8、方幂：设A为符号串集，则定义 A0={ε} A1=A An=An-1 A 例如：A={a,b} 则有： A0={ε} A1={a,b} A2={aa,ab,ba,bb}
+
3.3
文法与语言的形式定义
一、引言 例子： y:=a+b*x 语法：赋值语句由变量加“:=”加表 达式构成。 语义：右边表达式求值与左变量结 合赋值。 用途：表达式的值的保存和计算。
形式化方法：用一整套带有严格规定 的符号体系来描述问题的理论和方法。 表示文法需要一种工具，其中最常用 的工具是所谓的巴克斯范式(BNF)。 例子: A={an|n≥1} 其BNF表示有： (1) A→a|aA (2) A→a|Aa
语法 -- 表示构成语言句子的各个记号之间 的组合规律
语义 -- 表示各个记号的特定含义。（各个 记号和记号所表示的对象之间的关系） 语用 --表示在各个记号所出现的行为中， 它们的来源、使用和影响。
每种语言具有两个可识别的特性，即语言 的形式和该形式相关联的意义。 语言的实例若在语法上是正确的，其相关 联的意义可以从两个观点来看，其一是该句子 的创立者所想要表示的意义，另一是接收者所 检验到的意义。这两个意义并非总是一样的， 前者称为语言的语义，后者是其语用意义。幽 默、双关语和谜语就是利用这两方面意义间的 差异。
文法的写法 1 G：S→aAb A→ab A→aAb A→ε 2 G[S]： A→ab S→aSb 3 G[S]： A→ab |aAb |ε
A→aAb
A→ε
S→aSb
二、文法和语言形式定义 1、规则式，产生式 例子： B→b|Bb A→a|A 2、文法G[Z]：规则的非空有穷集合。 Z：识别符号，开始符号。V：字母表， 符号集合。 例子：G[S]={S→0，S，1} V＝{S，0，1}
例2: G3[S]: S→A|S-A A→a|b|c G4[S]: S→A|A-S A→a|b|c 推导过程如下： SS-A
S-A-A
S S A
b
A c
S
A a
A-A-A a-b-c
推导过程如下： SA-S A-A-S
S A
a
A
b
S S
A c
A-A-A a-b-c
a-b-c和a-b-c
3型文法(正则文法): 产生式为：A→a,A→bB,其中A,B∈VN, #a,b∈VT是符号串。 例子: G[Z]:Z→a Z→aA A→b|bB B→b 所以:G[Z]是3型文法
文法的类型 例：1型（上下文有关）文法 文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD
<1><整数>→<数字> <数字>→0|1|2|…|9 <2><整数>→<整数><数字> <整数>→<数字>|<整数><数字>
所以合起来有：
<整数>→<数字>|<整数><数字> <数字>→0|1|2|…|9
标识符:以字母开头以后由字母和数 字组成的符号串。
例子：<标识符>的巴科斯范式 <标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a|b|…|z <数字>→0|1|…|9
G3与G4等价，但G3与G4的语义不同。
文法的等价
若L（G1）=L（G2），则称文法G1和G2是等 价的。
如文法G1[A]：A→0R 与G2[S]：S→0S1 等价 A→01 S→01 R→A1
3.4
文法的类型
定义3.4 0型文法(短语结构文法): 产生式为：α→β，其中α和β是符号串。 1型文法(上下文有关文法)： 产生式为：αAβ→αuβ，其中A∈VN，u 为非空串。 2型文法(上下文无关文法): A→βVT，P，S） VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号
例 文法G=（VN，VT，P，S） VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…, <字母>→z <数字>→0,…, <数字>→9 } S=<标识符>
例子： <句子><主语><谓语> <代词><谓语> 我<谓语> 我<动词><直接宾语> 我是<直接宾语> 我是<名词> 我是大学生
“我是大学生”的构成符合上述规则， 而“我大学生是”不符合上述规则，我们 说它不是句子。这些规则成为我们判别句 子结构合法与否的依据，换句话说，这些 规则看成是一种元语言，用它描述汉语。 这里仅仅涉及汉语句子的结构描述。其中 一种描述元语言称为文法。
BNF范式和语法图 1、巴科斯范式:EBNF <句子>→<主语><谓语> <主语>→<代词>|<名词> <代词>→你|我|他 <名词>→王明|大学生|工人 <谓语>→<动词><宾语> <动词>→是|学习 <宾语>→<代词>|<名词> 带<>的叫非终止符,不带<>的叫终止符。 <逻辑值>→True|False
无符号整数
数字
3.2 符号和符号串
1、字母表:它是非空有穷集。 例如：∑={a,b,c}或∑={1,2,3} 2、符号：字母表中的元素称为符号。 3、符号串：符号的有穷序列，符号串 也称为字。用ε来表示空符号串。 例如：a,ab,abc,dsfsd
4、长度：符号串的长度是指该串所包 含的符号个数。用|x|表示符号串x的 长度。 例如：|a|=1，|abn|=3 5、连结：设x和y为符号串，则称xy 为他们的连结。 例如：x=aa,y=bb,则xy=aabb 6、空集：不含任何元素的集合,记为。
A={a2n|n≥1} 其BNF表示有： (1) A→aa|aaA (2) A→aa|Aaa
例子： A={abna|n≥1} 其BNF表示有多 种如下： (1) A→aBa B→b|Bb (2) A→aBa B→b|bB (3) A→aB B→ba|bB
如何来描述一种语言？