编译原理第二章

《编译原理第二章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1学习本章的目的掌握源语言语法的形式描述。构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述，根据这种描述，构造出相应的分析加工程序。语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那么好用，但它推动语言理论的发展。22.1.1字母表2.1.2符号串一、符号串的定义二、术语三、符号串的运算四、符号串集合的运算2.1符号串32.1.1字母表字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如:1.计算机语言：由符号“0”和“1”组成的字母表,∑={0，1}。2

2、.ASCII字符集；3.Pascal字母表为：∑={AZ,az,09,+,-,*,/,<,=,>,:,,,；，.，,(,),{,},[,]}4一、符号串的定义已知字母表∑,(1)ε是∑上的一个符号串；(2)若x是∑上的符号串，而a是∑的元素,则xa是∑上的符号串。(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作"字"。2.1.2符号串5二、术语设s是符号串前缀：移走s的尾部的零个或多于零个符号。后缀：移走s的头部的零个或多于零个

3、符号。子串:从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,…,真前缀，真后缀，真子串:x≠sx≠子序列:baa(这些符号不要求是连续的）逆

8、转（用SR表示）：ananab长度：banana=67三、符号串的运算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=bababa,…...8四、符号串集合(语言）的运算设L和M是两个符号串集合，则:1.合并：L∪M＝｛s

9、sLorsM}2.连接：LM＝｛st

10、sLandtM}3.方幂：L0={ε}，L1＝L

11、，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)*是由所有的字母打头的字母和数字组成的符号串所构成的集合。5．D+是由所有的长度大于等于1的数字串

12、所构成的集合。102.2文法和语言的定义2.2.1引子2.2.2文法和语言的定义一、文法和语言的定义二、推导三、语言四、最左推导和最右推导五、短语，直接短语，句柄112.2.1引子分析：Thegreywolfwilleatthegoat〈谓语〉〈主语〉〈冠词〉〈形容词〉〈名词〉〈动词〉〈直接宾语〉助动词〈句子〉动原冠词名词Thegreywolfwilleatthegoat12为了进行机械分析，“句子由主语后跟随谓语组成”表示为：句子主语谓语（1）主语冠词形容词名词（2）冠词the

13、形容词grey谓语动词直接宾语（5）动词助动词动词原形（6）助动词will动词原形eat直接宾语冠词名词（9）名词wolf名词goat13句子的语法有四部分：终结符号集，非终结符号集，开始符号，语法规则。终结符号集VT={the，grey,wolf,will,eat,goat}非终结符号集VN={句子，主语，谓语，冠词，形容词，名词，动词，直接宾语，助动词，动词原形}开始符号S=句子语法规则集P={句子

14、主语谓语,……}14句子主语谓语冠词形容词名词谓语the形容词名词谓语thegrey名词谓语thegreywolf谓语thegreywolf动词直接宾语…...thegreywolfwilleatthegoat句子根据规则推导出来15句子th