编译原理C2-绪论与文法.ppt

《编译原理C2-绪论与文法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理——前后文无关文法和语言主要内容本章讨论与编译实现相关的形式语言理论基本概念，主要内容有：文法及语言的表示文法和语言的定义句型的分析文法的化简和改造文法和语言的Chomsky分类文法与语言一个程序设计语言的确切定义是构造编译程序的重要前提文法被用来精确而无歧义地描述语言的构成方式文法描述语言的时候不考虑语言的含义2.1文法及语言的表示1.程序设计语言的定义语言是一个记号系统汉语--符合汉语语法的句子的全体英语--符合英语语法的句子的全体程序设计语言--该语言的程序的全体程序设计语言由语法和语义定义：语法：定义每个程序构成的规则语义：定义每个程序的意义程序设计语言包括:语法和语义

2、语法(syntax)定义:是一组规则，用它可以形成和产生一个合适的程序描述工具:文法作用:定义什么样的符号序列是合法的，与符号的含义无关语义(semantics)分类:静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的动态语义：表明程序要做什么描述工具:指称语义,操作语义等作用:检查类型匹配，变量作用域等2.文法的直观概念如何来描述一种语言？文法是描述语言的语法（形式）结构的形式规则。如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，要找出语言的有穷表示。有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造识别方式（自动机）：用

3、一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。形式语言和编译理论中的最基本概念——符号串和符号串集合基本定义它们的运算1.符号和符号串字母表定义:元素的非空有穷集合例：∑={0‚1}Α={a‚b,c}元素也称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。符号串定义:由字母表中的符号组成的任何有穷序列例：0,00,10是字母表∑={0‚1}上的符号串a,ab,aaca是Α={a‚b‚c}上的符号串在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同不含任

4、何符号的符号串称为空串，用ε表示注意:{ε}并不等于空集合{}符号串长度:符号串中含有符号的个数如:

5、abc

6、=3

7、ε

8、=0子串设有非空符号串u=xvy,则称v为符号串u的子串。例如符号串x=a+b*(c+d),则ε,a,a+b*,与(c+d)等都是x的子符号串，且其长度分别为

9、a

10、=1,

11、a+b*

12、=4,

13、(c+d)

14、=5符号串的前缀和后缀如果z=xy是一个符号串，则x是z的前缀，而y是z的后缀。如果y非空，则x是z的真前缀；如果x非空，则y是z的真后缀。例如：字母表A={a,b,c}上的符号串x=abc,则x的前缀：ε,a,ab,abc,后缀:ε,c,bc,abc真前缀:ε,a,a

15、b,真后缀:ε,c,bc符号串的运算符号串的连接：设x、y是符号串,它们的连接是把y的符号写在x的符号之后得到的符号串xy例如x="ST"，y="abu"，则xy="STabu"显然εx=xε=x符号串的方幂：把符号串a自身连接n次得到的符号串an=aa…aa例如a1=aa2=aaa0=ε符号串集合：定义:若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的乘积：符号串集合A和B的乘积定义为:AB={xy

16、x∈A且y∈B}，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。若集合A=ab,cdeB=0,1则AB=ab0,ab1,c

17、de0,cde1显然{ε}A=A{ε}=A符号串集合的方幂:设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下:A0={ε}A1=A,A2=AAAK=AA......A(k个)集合的闭包闭包集合Σ的闭包Σ*定义如下：Σ*=Σ0∪Σ1∪Σ2∪Σ3∪…例：设有字母表Σ={0，1}则Σ*=Σ0∪Σ1∪Σ2∪…={ε,0,1,00,01,10,11,000,…}即Σ*表示Σ上所有有穷长的串的集合。正闭包Σ+=Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。+表示上的除ε外的所有用穷长串的集合Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*Σ字母表上的一个语言是上符合某种规则的一些符

18、号串的集合，是*的一个子集。例如：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}1.集合{ab,aabb,aaabbb,…,anbn,…}或{w

19、w∈Σ*且w=anbn,n≥1}为字母表上的一个语言。集合{a,aa,aaa,…}或{w

20、w∈Σ*且w=an,n≥1}为字母表上的一个语言。ε是一个语言。即是一个语言。小结1符号与字母表2符号串3符号串的运算4符号串集合5集合的闭包6字母表的闭包文法和语