资源描述：
《第2章-1-文法的形式定义ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章前后文无关文法和语言本章主要内容2.1语言及文法概述2.2文法(Grammar)和语言的形式定义2.3句型分析2.4文法的分类2.5文法的构造2.1语言概述什么是语言自然语言(NaturalLanguage)是人与人的通讯工具语义(Semantics):环境、背景知识、语气、二义性——难以形式化计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(Semantics)——易于形式化：严格语言是用来交换信息的工具——功能性描述2.1语言概述语言的描述方法——现状自然语言：自然、方便-非形式化数学语言（符号）：
2、严格、准确-形式化形式化描述高度的抽象，严格的理论基础和方便的计算机表示。2.1语言概述语言——形式化的内容提取单词(Token)：满足一定规则字符(Character)串句子(Sentence)：满足一定规则单词序列语言(Language)：满足一定条件的句子集合语言是字和组合字的规则——结构性描述例：一译开天第课今始编节上今天开始上第一节编译课2.1语言概述程序设计语言——形式化的内容提取程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合程序(Program)：满足语法规则的语句序列语句(Sentence)：满足语法规则的单词序列单词
3、(Token)：满足词法规则的字符串例变量=表达式if条件then语句while条件do语句call过程名(参数表)2.1语言概述描述形式——文法语法——语句语句的组成规则描述方法：BNF范式、语法(描述)图词法——单词单词的组成规则描述方法：BNF范式、正规式2.2文法和语言的基本定义2.2.1基本概念和术语字母表（Alphabet）是一个非空有穷集合，字母表中的元素称为该字母表的一个字母（Letter），也叫字符（Character）例以下是不同的字母表⑴{a，b，c，d}⑵{a，b，c，……，z}⑶{0，1}相当于高级语言的字符集2.2.1基本概念和术语字母表上
4、符号串(String)的定义(1)ε是∑上的一个符号串，叫做空串。(2)若x是∑上的符号串，而a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作“字”(Word)。2.2.1基本概念和术语定义1设∑1、∑2是两个字母表，∑1与∑2的乘积(Product)∑1∑2={ab
5、a∈∑1，b∈∑2}例:∑1={0,1},∑2={a,b},∑1∑2={0a,0b,1a,1b}定义2设∑是一个字母表，∑的n次幂(Power)递归地定义为：⑴∑0={ε}⑵∑n=∑n-1
6、∑n≥1例：∑13={000,001,010,011,100,101,110,111}2.2.1基本概念和术语定义3设∑是一个字母表，∑的正闭包(PositiveClosure)：∑+=∑∪∑2∪∑3∪∑4∪……∑的克林闭包(KleeneClosure)：∑*=∑0∪∑+=∑0∪∑∪∑2∪∑3∪……2.2.1基本概念和术语例{0,1}+={0，1，00，01，11，000，001，010，011，100，……}{a，b，c，d}+={a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，……，aaa，aab，aac，aad，aba，abb，abc……}2.2
7、.1基本概念和术语例{0,1}*={ε，0，1，00，01，11，000，001，010，011，100，…}{a，b，c，d}*={ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc，…}2.2.1基本概念和术语定义5设∑是一个字母表，L∑*，L称为字母表∑上的一个语言（Language），x∈L，x叫做L的一个句子。例：字母表{0，1}上的语言{0，1}{00，11}{0，1，00，11}{0，1，00，11，01，10}{00，11}*{01，10}*2.2.1基本概念和术语设s是
8、符号串：01290273前缀：移走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串：从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）长度：是该符号串中的符号的数目。例如
9、aab
10、=3,
11、ε
12、=0。2.2.1基本概念和术语符号串的连接和幂1.连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.幂：x0=;x1=x;x2=xx;……;xn=xn-1x;例如,x=ba,x1=ba,x2=baba,x3=baba
