第3章文法和语言（一）

2024-05-06 03:08

文章标签 语言文法

本文主要是介绍第3章文法和语言（一），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、语言

语言是由句子组成的集合，是由一组记号所构成的集合。
汉语--所有符合汉语语法的句子的全体
英语--所有符合英语语法的句子的全体
程序设计语言--所有该语言的程序的全体

二、文法

概念：

一种语言描述工具，用来定义句子的结构，用有限的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。

〈句子〉::=〈主语〉〈谓语〉
〈主语〉::=〈代词〉|〈名词〉
〈代词〉::= 你 | 我 | 他
〈名词〉::= 王明 | 大学生 | 工人 | 英语
〈谓语〉::=〈动词〉〈直接宾语〉
〈动词〉::= 是 | 学习
〈直接宾语〉::=〈代词〉|〈名词〉

“我是大学生”是否是该语言的句子？

答：是，推导过程如下所示：

〈句子〉 =>〈主语〉〈谓语〉
  =>〈代词〉〈谓语〉
=> 我〈谓语〉
=> 我〈动词〉〈直接宾语〉
  => 我是〈直接宾语〉
  => 我是〈名词〉
  => 我是大学生

三、符号和符号串

任何一种语言可看成是某个符号集上定义的，按一定规则构成的一切基本符号串组成的集合。
字母表∑：元素的非空有穷集合。（符号集）
符号：字母表中的元素。
例如：
汉语的字母表中包括汉字、数字及标点符号等。
C语言的字母表是由字母、数字、若干专用符号及IF、FOR之类的保留字组成。
符号串：由字母表Σ中的符号组成的任何有穷序列称为该字母表上的符号串。

形式定义:
1.空符号串ε(没有符号的符号串)是Σ上的符号串
2.若x是Σ上的符号串,a是的元素,则xa是Σ上的符号串
3.y是Σ上的符号串,当且仅当它可以由1和2导出。

例如： Σ={a,b} ε,a,b,aa,ab,aabba,…,都是上的符号串

例： Σ={0,1} ε,0,1,00,01,11,1001110等都是上的符号串.

例： Σ={a,b,c}上的符号串有：
ε,a,b,c,ab,ba,aaca,acaa等.

注意：
符号串中的符号排列是有顺序的。
常用大写字母表示符号串，如 x=aaca

如果 z = xy 是一符号串，那么：
1、x 是 z 的头，y 是 z 的尾；
2、如果 x 非空，那么 y 是固有尾；如果 y 非空，那么 x 是固有头。

例：
设 z = abc, 那么
z 的头是： ε,a ,ab , abc（除 abc 外都是固有头）
z 的尾是： ε,c ,bc , abc（除 abc 外都是固有尾）

4、符号串的运算
符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 ε的长度为0
符号串的连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy
例 x=ST,y=abu 则 xy=STabu |x|=2,|y|=3,|xy|=5
εx = xε= x

方幂：符号串x自身连接n次得到的符号串 xx…xx(n个x)定义为 xn
x0=ε, x1=x, x2=xx, x3=xxx
x=AB, 则 x0=ε, x1=AB, x2=ABAB, x3=ABABAB
对于 n>0, xn = xxn-1 = xn-1x

5、符号串集合
若集合A中一切元素都是某字母表Σ上的符号串，则称A为字母表Σ上的符号串集合。
两个符号串集合A和B的乘积定义为 AB={xy|x∈A且y∈B}
若集合A={a,b}, B={c,d}
则 AB={ac,ad,bc,b}
{ε}A=A{ε}=A(∵εx=xε=x)
使用Σ*表示Σ上的所有有穷长的串（包括ε）的集合。Σ*称为Σ的闭包。
从Σ*中除去ε得到的集合记为Σ+ 。 Σ+称为Σ的正闭包。

Σ* = Σ0 ∪ Σ1 ∪ Σ2 … ∪ Σn …
Σ+ = Σ1 ∪ Σ2 … ∪ Σn …
Σ* = Σ0 ∪ Σ+
Σ+ = ΣΣ* = Σ*Σ
Σ+ = Σ* -{ε}

例：设Σ={0,1}，则
Σ* ={ε, 0, 1, 00, 01, 10, 11, 000, 001, 010,…}
例：设Σ={a,b}，则
Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}
Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}

这篇关于第3章文法和语言（一）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！