资源描述：
《第二章语言的基本知识》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章语言的基本知识学习本章的目的。2.1符号串2.2文法和语言的定义2.3分析树和二义性2.4形式语言概观1学习本章的目的构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那磨好用，但它推动语言理论的发展。22.1符号串2.1.1字母表2.1.2符号串 一.符号串的定义二.术语三.符号串的运算四.符号串集合的运算3字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如
2、:1.计算机语言：由符号“0”和“1”组成的字母表,∑={0，1}2.ASCII字符集；3.Pascal字母表为：∑={AZ,az,09,+,-,*,/,<,=,>,:,',',;，.，,(,),{,},[,]}2.1.1字母表4一.符号串的定义(1)ε是∑上的一个符号串。(2)若x是∑上的符号串，而a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作"字"。2.1.2符号串5设s是符号串前缀：移
3、走s的尾部的零个或多于零个符号后缀：删去s的头部的零个或多于零个符号子串:从s中删去一个前缀和一个后缀子序列:从s中删去零个或多于零个符号(这些符号不要求是连续的）逆转（用SR表示）：将S中的符号按相反次序写出而得到的符号串。长度：是该符号串中的符号的数目。例如
4、aab
5、=3,
6、ε
7、=0。二术语6：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a,子串:banana,anana,banan,anan,…,真前缀，真后
8、缀，真子串:x≠sx≠子序列: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
9、sLorsM}2.连接：LM＝｛st
10、sLa
11、ndtM}3.方幂：L0={ε}，L1＝L，L2＝LL,...,Ln＝Ln-1L4.语言L的Kleene闭包，记作L*，L*＝∪Li(i>=0)=L0∪L1∪L2∪L3∪…5．语言L的正闭包，记作L+（L+＝LL*）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是由所有的四个字母的符号串构的集合。4．L（L∪D)*是由所有的字母打
12、头的字母和数字组成的符号串所构成的集合.5．D+是由所有的长度大于等于1的数字串所构成的集合.例102.2文法和语言的定义2.2.1引子2.2.2文法和语言的定义一.文法和语言的定义二.推导三.语言四.最左推导和最右推导五。短语，直接短语，句柄11引子分析：Thegreywolfwilleatthegoat〈谓语〉〈主语〉〈冠词〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词〈句子〉动原冠词名词Thegreywolfwilleatthegoat12为了进行机械分析，：“句子由主语后跟随谓语组成”表示为：句子主
13、语谓语（1）主语冠词形容词名词（2）冠词the形容词grey谓语动词直接宾语（5）动词助动词动词原形（6）助动词will动词原形eat直接宾语冠词名词（9）名词wolf名词goat语法规则13：终结符号集，非终结符号集，语法规则，开始符号。终结符号集VT={the，grey,wolf,will,eat,goat}非终结符号集VN={句子，主语，谓语，冠词，形容词，名词，动词，直接宾语
14、，助动词，动词原形}语法规则集P={句子主语谓语，……}开始符号S=句子句子的语法有四部分14句子主语谓语冠词形容词名词谓语the形容词名词谓语thegrey名词谓语thegreywolf谓语thegreywolf动词直接宾语…...thegreywolfw
