举报文档 收藏
/30
帮帮创意 > 其他文档 > 第二章语言的基本知识.ppt

第二章语言的基本知识.ppt

第二章语言的基本知识.ppt
内容要点:
第二章语言的基本知识,第二章 ???语言的基本知识u学习本章的目的。u2.1??符号串u2.2??文法和语言的定义u2.3??分析树和二义性u2.4 形式语言 概观1学习本章的目的u构造编译程序的算法是从研究源程序及目标程序产生的,首先找到源语言的形式描述,根据这种描述,构造出相应的分析加工程序。u语言分语法,语义和语用。程序语言语法的形式描述是很好用的,语义的形式描述不那磨好用,但它推动语言理论的发展。2 2.1???符号串u2.1.1? 字母表u2.1?.2 符号串一 . 符号串的定义u 二 . 术语u 三 . 符号串的运算u 四 . 符号串集合的运算3 字母表是符号的非空有穷集合。任何程序语言都有自己的字母表,例如 :1.计算机语言:由符号 “0” 和 “1” 组成的字 母表 ,∑={0 , 1} 2. ASCII字符集;3. Pascal字母表为: ∑={A?Z, a?z, 0?9, +, -, *, /, , :, '','', ; , ., ??,??(,??),?{,??},??[,??]???} 2.1.1??字母表4一 . 符号串的定义(1) ε 是 ∑ 上的一个符号串。(2) 若 x是 ∑ 上的符号串,而 a是 ∑ 的元素 ,则 xa是 ∑ 上的符号串。(3) y是 ∑ 上的符号串 ,当且仅当它由 (1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串 ,也称作"字 "。2.1.2??符号串5 设 s是 符号串前缀:移走 s的尾部的零个或多于零个符号后缀:删去 s的头部的零个或多于零个符号子串 : 从 s中删去一个前缀和一个后缀子序列 : 从 s中删去零个或多于零个符号 (这些符号不要求是连续的)逆转(用 SR表示):将 S中的符号按相反次序写出而得到的符号串。长度:是该符号串中的符号的数目。例如|aab|=3,|ε|=0 。二 ?术语6 : 符号串 s=banana前缀: ?,b,ba,ban,bana,banan,banana后缀: banana,anana,nana,ana,na,a, ?子串 : banana,anana,banan,anan,…, ?真 前缀, 真 后缀, 真 子串 : x≠s ?x ≠ ?子序列 : baa(这些符号不要求是连续的)逆转(用 SR表示): ananab长度: ?banana?=6例71.连接:设 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=bababa,…...三 .符号串的运算8 设 L和 M是两个 符号串集合,则1.合并: L∪M ={ s|s?L or s?M}2.连接: LM={ st|s?L and t?M}3.方幂: L0={ε} , L1= L,L2= LL, ..., Ln= Ln-1L 4. 语言 L的 Kleene闭包,记作 L*,L*= ∪L i(i>=0) =L0∪L 1∪L 2∪L 3 ∪…5.语言 L的正闭包,记作 L+( L+= L?L*)L+= ∪ Li(i?>=1)?=L1∪ L2∪ L3∪ L4∪ …四 . 符号串集合 (语言)的运算9????如: L={A~Z,a~z}??D={0~9}1. L∪ D={A~Z,a~z?,0~9}??2. LD是由所有用一个字母后跟一个数字 组成的符号串所构成的集合。3. L4是由所有

发表评论

暂无评论,赶快抢占沙发吧。

su****1

咨询 关注

扫描手机访问

反馈 足迹 顶部