第三章文法和语言.ppt

《第三章文法和语言.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章文法和语言学习目标:掌握：自上而下与自下而上的分析方法理解：文法的形式定义，推导，归约，句型，句子，语言，上下文无关文法，规范句型，语法树，短语，直接短语，句柄了解：文法的类型，文法实用中的限制，文法的二义性3.1语言和文法的直观概念3.2符号和符号串3.3文法和语言的形式定义3.4文法的类型3.5上下文无关文法及其语法树3.6句型的分析3.7有关文法实用中的一些说明3.1语言和文法的直观概念程序设计语言的定义语言是一个记号系统。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法

2、的句子的全体程序设计语言--所有该语言的程序的全体研究程序设计语言包括：每个程序构成的规律每个程序的含义程序设计语言包括:语法和语义语法(syntax)定义:是一组规则，用它可以形成和产生一个合适的程序描述工具:文法作用:定义什么样的符号序列是合法的，与符号的含义无关。语义(semantics)分类:静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的动态语义：表明程序要做什么描述工具:指称语义,操作语义等作用:检查类型匹配，变量作用域等文法的直观概念如何来描述一种语言？如果语言是有穷的（只

3、含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，要找出语言的有穷表示。有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。文法：是语言语法的描述工具，实现用有穷的规则把语言的无穷句子集描述出来。例:“我是大学生”是汉语的一个句子用EBNF来表示汉语句子的构成规则：〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词

4、〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉由规则推导句子方法:用一条规则∷=的右端符号串代替::=的左端.表示:用“=>”表示推导,含义是,使用一条规则,代替=>左边的某个符号,产生=>右端的符号串.例如:句子“我是大学生”的推导过程如下：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生文法的作用严格定义句

5、子的结构，是判断句子结构合法与否的依据用有穷的规则把无穷的句子集合描述出来3.2符号和符号串字母表定义:元素的非空有穷集合例：∑={0‚1}Α={a‚b,c}元素也称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。符号串定义:由字母表中的符号组成的任何有穷序列例：0,00,10是字母表∑={0‚1}上的符号串a,ab,aaca是Α={a‚b‚c}上的符号串在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同不含任何符号的符号串称为空串，用ε表示注意:

6、{ε}并不等于空集合{}符号串长度:符号串中含有符号的个数如:

7、abc

8、=3

9、ε

10、=0符号串的运算符号串的连接：设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=

11、{xy

12、x∈A且y∈B}，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。若集合A=ab,cdeB=0,1则AB=ab0,ab1,cde0,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,

13、1,00,01,10,11,000,…}即Σ*表示Σ上所有有穷长的串的集合。正闭包Σ+=Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。+表示上的除ε外的所有用穷长串的集合Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*Σ字母表上的一个语言是上的一些符号串的集合即是*的一个子集例如：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}集合{ab,aabb,aaabbb,…,anbn,…}或{w

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

15、