第一章编译概述ppt课件.ppt

第一章编译概述ppt课件.ppt

ID:58730223

大小:330.00 KB

页数:61页

时间:2020-10-04

第一章编译概述ppt课件.ppt_第1页
第一章编译概述ppt课件.ppt_第2页
第一章编译概述ppt课件.ppt_第3页
第一章编译概述ppt课件.ppt_第4页
第一章编译概述ppt课件.ppt_第5页
资源描述:

《第一章编译概述ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、Chapter2 GrammarandLanguage串和语言(StringsandLanguages)文法和语言的定义(DefinitionsofGrammarandLanguage)文法和语言的分类(ClassificationofGrammarandLanguage)分析树与句型(ParseTreeandSententialform)9/14/202112.1串和语言字母表(alphabet):字母表是符号(symbols)的非空有穷集合,用∑表示符号:可以相互区别的记号(元素)不同的语言有不同的字母表汉语——汉字英语——26

2、个英文字母9/14/202122.1串和语言符号串(String):符号串是由字母表中的符号所组成的有穷序列在语言理论中,符号串又称为:句子(sentence)、字(word)例如:Σ={a,b}a,b,aa,ab,aabba…都是Σ上的符号串ε是任何Σ上的符号串9/14/202132.1串和语言符号串的长度符号串中包含符号的个数符号串s的长度记为

3、s

4、例,对于字母表{a,b,c},aab是其上的一个符号串,

5、aab

6、=3注意:空符号串ε,

7、ε

8、=09/14/202142.1串和语言符号串的前缀(prefix)、后缀(suffix)

9、、子串(substring)后缀:删去符号串s头部的零个或多于零个符号得到的符号串例如:nana是符号串banana的一个后缀前缀:移走符号串s尾部的零个或多于零个符号得到的符号串例如:b是符号串banana的一个前缀9/14/202152.1串和语言符号串的真(proper)前缀、真后缀和真子串——非空子串:从s中删去一个前缀和一个后缀得到的符号串例如:ana是符号串banana的一个子串*对于每个符号串s,s和ε两者都是符号串s的前缀,后缀和子串9/14/202162.1串和语言语言(Language):某个字母表上的符号串的集

10、合例:汉语——所有符合汉语语法的句子构成的集合PASCAL语言——所有合法的PASCAL程序构成的集合注意:空集{}、和{ε}的不同9/14/202172.1串和语言符号串的运算:连接(concatenation):符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd注:εα=αε=α方幂(exponentiation):符号串自身连接n次得到的符号串αn定义为αα…ααn个αα1=α,α2=αα,注:α0=ε9/14/202182.1串和语言语言的运算(operationsonla

11、nguages):语言是符号串的集合,集合的运算有并、交、差等并运算—等同于集合的并运算9/14/202192.1串和语言连接(乘积)两个符号串集合A和B的乘积定义为:AB={xy

12、xA且yB}例如:集合A={ab,cde}B={0,1}则AB={ab1,ab0,cde0,cde1}{ε}L=L{ε}=LLL…L=LnL0={ε}9/14/2021102.1串和语言*闭包(Kleeneclosure)L*=L0∪L1∪L2∪L3∪…+闭包(Positiveclosure)L+=L1∪L2∪L3∪…L*=L+∪ε9/14/

13、2021112.1串和语言注:后面通常是考虑字母表∑的*闭包和+闭包例:Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}9/14/2021122.1串和语言综合性的例子:P93example3.2L={A,B,C,…,Z,a,b,c,…,z}D={0,1,…,9}把L和D两个字母表看作长度为1的符号串集合,即语言1.L∪D2.LD3.L44.L*5.L(L∪D)*6.D+9/14/2021132.2文法和语言的定义如何来描述一种语言?如果语言是

14、有穷的(只含有有穷多个句子),可以将句子逐一列出来表示如果语言是无穷的,找出语言的有穷表示。9/14/2021142.2文法和语言的定义语言的有穷表示有两个途经:生成方式(文法):语言中的每个句子可以用严格定义的规则来构造。识别方式(自动机):用一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要么能停止并回答“不是”,(要么永远继续下去。)文法即是以生成方式描述语言的:语言中的每个句子可以用严格定义的规则来构造.9/14/2021152.2文法和语言的定义文法G定义为四元组(VT,VN,S,

15、P):VT:终结符(terminals)集,其中的元素一般用小写字母或数字表示(a,b,c…0,1..),代表语言中不可再分的基本符号,如汉语中的汉字、PASCAL语言中的基本字VN:非终结符(nonterminals)集,其中的元素

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。