第二章 形式语言与自动机理论基础(形式语言)

《第二章 形式语言与自动机理论基础(形式语言)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章形式语言与自动机理论基础2.1预备知识2.2文法的讨论2.3文法和语言的定义2.4分析树和二义性2.5形式语言概观语言、语法、语义语言是由单词按照一定的语法规则组成的句子集合（符号串集合），表达一定的意义语法是语言的形式，语义是语言的内容语言的分析就是句子的分析2.1预备知识2.1.1字母表2.1.2符号串一、符号串的定义二、术语三、符号串的运算四、符号串集合的运算字母表是符号的非空有穷集合；例：={a，b，c}任何程序语言都有自己的字母表。2.1.1字母表1.计算机语言：由符号“0”和“1”组成的字母表:∑=

2、{0，1}2.Pascal语言字母表：∑={AZ,az,09,+,-,*,/,<,=,>,:,‘,”,;，.，,(,),{,},[,]}3.C语言字母表：∑={AZ,az,09,+,-,*,/,<,=,>,_,&,^,~,,:,‘,”,;，.，?,(,),{,},[,],空格,!,#,%}一.符号串的定义由字母表∑中的符号所组成的的任何有穷序列被称之为该字母表上的符号串。空符号串：无任何符号的符号串，记作ε2.1.2符号串符号串的形式定义：(1)字母表∑上字符是∑上的符号串。(2)若x是∑上的符号串，而

3、a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。二术语（设s是符号串banana）前缀：移走s的尾部的零个或多于零个符号所得符号串,b,ba,ban,bana,banan,banana后缀：删去s的头部的零个或多于零个符号所得符号串banana,anana,nana,ana,na,a,子串:从s中删去一个前缀和一个后缀所得符号串banana,anana,banan真前缀、真后缀和真子串：不是s和ε的前缀、后缀和子串子序列:从s中删去零个或多于零个符号(不要求是连续）而

4、得到的符号串。如baaa长度：是符号串中符号的个数。例如

5、aab

6、=3,

7、ε

8、=0语言：确定字母表上字符串的任何集合例如：不含任何元素的空集合Ø，即{}只含有空符号串的集合{ε}符合Pascal语法的程序组成的集合（Pascal语言）符合英文语法的句子组成的集合1.连接：设x和y是符号串，它们的连接xy是把符号串y写在符号串x的之后得到的符号串。例如x=ba,y=nana,xy=banana.x=x=ba2.方幂：x0=x1=xx2=xx…xn=xn-1x例如x=bax1=bax2=babax3=bababa

9、,…三.符号串的运算（语言L和M）1.合并：L∪M＝｛s

10、sLorsM}属于L或属于M的符号串s所组成的集合2.连接：LM＝｛st

11、sLandtM}s属于L和t属于M的所有符号串st组成的集合{ε}L=L{ε}=L3.方幂：L0={ε}L1＝L…Ln＝L（n-1）L(n>0)四.语言(符号串集合）的运算4.语言L的正闭包，记作L+L+＝L1∪L2∪L3∪L4∪…5.语言L的Kleene闭包(自反闭包)，记作L*L*＝L0∪L＋＝L0∪L1∪L2∪L3∪…例：A={x,y}A＋＝？A*＝？{x,y,xx,xy,y

12、x,yy,xxx,xxy,xyx,xyy,……}A1A2A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}A0A1A2A3例:（语言L={AZ,az}D={09}）1．L∪D={AZ,az,09}2．LD所有一字母后跟一数字组成的符号串构成的集合3．L4所有的四个字母的符号串构成的集合4．L（L∪D)*所有字母打头的字母和数字符号串构成的集合5．D+所有长度大于等于1的数字串构成的集合2.2文法的讨论例：有一英文句子：“Thegreywolfwilleatthegoat.”。这

13、是一个在语法、语义上都正确的句子。如何用语法单位如<句子>、<主语>等推导出该句子？<句子><名词><谓语><动词><直接短语><冠词><形容词><主语><助动词><动词原形><冠词><名词>ThegreywolfwilleatthegoatBNF范式表示法：如果用符号“”(或“::=”)表示“定义为”，用符号“

14、”表示“或”，<>表示语法成分句子主语谓语（1）主语冠词形容词名词（2）冠词the（3）形容词grey（4）谓语动词直接宾语（5）动词助动词

15、动词原形（6）助动词will（7）动词原形eat（8）直接宾语冠词名词（9）名词wolf（10）名词goat（11）名词wolf

16、goat由规则推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的