文法和语言的形式化定义在线视频

这节课给大家介绍

文法和语言的形式定义

如何实现语言的形式化描述

我们需要瞄准语言的结构

用组成规则进行描述

我们先来看文法的概念

文法G 我们可以定义为四元组

包含四部分

Vn VT P S

其中的Vn

我们称之为非终结符集

它是语法实体或变量的集合

VT是终结符集

Vn 和VT的交集为空

这里我们令V为Vn 和VT的并集

V称之为文法的字母表或者是词汇表

P是产生式或者叫规则的集合

规则的描述形式是这样子的

其中α β是字母表中的符号

α是V的正闭包

β是V的闭包

α不可以为空

β可以为空

S是识别符号

或者开始符号

是一个非终结符

至少出现在一条规则中　　

我们上一节课讲过的汉语句子

我们可以用文法来描述

大家看这种描述形式

四元组（Vn，VT，P，S）

终结符集VT

非终结符集Vn

那开始符号S={〈句子〉}了

规则和产生式集合列出了

对句子的所有定义的规则

再来看一个文法G

非终结符集中只含有一个元素S

终结符集中由两个元素0和1组成

产生式集中有两条产生式

开始符号是S

一般我们约定

第一条产生式的左部

是识别符号也就是开始符号

用尖括号括起来的是非终结符

不用尖括号括起来的是终结符

或者可以用大写字母表示非终结符

小写字母表示终结符

这里是一个标识符的文法

大家看

Vn={标识符，字母，数字}

VT={a,b,c,…，x,y,z,0,1,…，9}

S是开始符号

它只包含有〈标识符〉

大家看这里是规则集合

这里的规则我们也可以简写

规则左边相同的我们可以写在一起

右边用或符号就可以了

比如说〈字母〉→a|b|c|…|z

〈数字〉→0|1|2|3|4|5|6|7|8|9

一般文法有四种描述形式

大家看这里

第一种是常规的书写方式

列出了四元组的每一部分

第二种不用列出四元组

这里约定第一条规则的左部

是文法的识别符号

按照约定可以从规则中

读出终结符和非终结符

第三种是将开始符号或者是识别符号

标注在G的后面

第四种 更加简化

将有相同左部的统一写在一起

右部用或符号分隔

有了文法

如何产生语言的句子呢

我们来看推导的定义

如果α->β是文法 G的规则

是文法G中的规则或者是一个产生式

γ和δ是字母表或者是词汇表V*中的任意符号

有两个符号串

v和w

v=γαδ

那么w=γβδ

那么我们就说v应用规则

α->β

我们直接可以产生w

或者说

w是v的直接推导

我们可以记作这种形式

大家来看标识符文法

那么对于<标识符>

我们直接可以推导出 来

<标识符><字母>

句型abc<数字>

我们可以运用规则<数字>::=5

直接推导出来abc5

再来看多步推导的定义

如果存在直接推导的序列就是

v=w0=> w1 =>w2… =>  wn=w

wn就是w

这个时候n＞0

那么我们就称

v推导出来w

它的推导的长度为n

也就是进行了多步推导

从v能够得到w

那么我们可以使用推导符号

上面加一个加号

来表示多步推导

这里就是这种表示形式

如果v经过多步推导到w

如果存在v=w

那么我们就可以使用推导符号

上面加一个乘号来表示

我们记做这种形式

来看这个文法

它有一个句型V

是0S1

还有一个句型是w

w=00001111

那么我们可以说从V

可以经过多步推导到w

我们可以记做这种形式

再来看标识符文法中

那标识符文法中有一个句型V

是〈标识符〉〈数字〉

还有一个句型W=ab1

那么我们可以从V经过若干步

依次运用规则

可以推导出来w

在这个过程中

运用了多条规则进行推导

我们可以把它记做这种形式

或者是这种形式

再来看句子的定义

假设有一个文法G

如果符号串x是从识别符号推导出来的

那么我们可以称

x是文法G[S]的一个句型

如果x中只有终结符

那么这个x就是文法G[S]的句子

比如说这里这个文法

0S1 是句型

000111就是句子

语言是句子的集合

文法G所产生的语言

我们可以把它定义为

从文法开始符号推导出的

所有句子的集合

我们用 L(G)表示

很明确的

L(G)中的句子满足两个条件

第一个 符号串x可以从识别符号推出

也就是x是句型

第二个条件 就是x仅由终结符组成

那么x就是文法G的句子

比如这个文法

语言集合L(G)

那就是0的n次方

链接1的n次方

如果有两个文法

G1和G2

它们产生的语言集合是相等的

那么我们就可以称

这两个文法是等价的

这节课就讲到这里

谢谢大家