编译原理(清华)第三章文法和语言

本文格式为Word版，下载可任意编辑——编译原理(清华)第三章文法和语言

编译原理(清华)

第三章

文法和语言

学习目标:把握：自上而下与自下而上的分析方法理解：文法的形式定义，推导，归约，句型，句子，语言，上下文无关文法，规范句型，语法树，短语，直接短语，句柄了解：文法的类型，文法使用中的限制，文法的二义性

编译原理(清华)

3.13.23.33.43.53.63.7

语言和文法的直观概念符号和符号串文法和语言的形式定义文法的类型上下文无关文法及其语法树句型的分析有关文法实用中的一些说明

编译原理(清华)

3.1语言和文法的直观概念1.程序设计语言的定义语言是一个记号系统。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体研究程序设计语言包括：每个程序构成的规律每个程序的含义

编译原理(清华)

程序设计语言包括:语法和语义语法(syntax)定义:是一组规则，用它可以形成和产生一个适合的程序描述工具:文法作用:定义什么样的符号序列是合法的，与符号的含义无关。

编译原理(清华)

语义(semantics)分类:静态语义：一系列限定规则，确定哪些贴合语法的程序是适合的动态语义：说明程序要做什么描述工具:指称语义,操作语义等作用:检查类型匹配，变量作用域等

编译原理(清华)

2.文法的直观概念如何来描述一种语言？假使语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示假使语言是无穷的，要找出语言的有穷表示。有两个途经：1.生成方式(文法):语言中的每个句子可以用严格定义的规则来构造2.识别方式(自动机):用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会中止并回复“是〞,若不属于，要么能中止并回答“不是〞,要么永远继续下去。

编译原理(清华)

文法：是语言语法的描述工具，实现用有穷的规则把语言的无穷句子集描述出来。

编译原理(清华)

例:“我是大学生〞是汉语的一个句子用EBNF来表示汉语句子的构成规则：〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉|〈名词〉〈代词〉∷=我|你|他〈名词〉∷=王明|大学生|工人|英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是|学习〈直接宾语〉∷=〈代词〉|〈名词〉

编译原理(清华)

由规则推导句子方法:用一条规则∷=的右端符号串代替::=的左端.表示:用“=〞表示推导,含义是,使用一条规则,代替=左边的某个符号,产生=右端的符号串.

编译原理(清华)

例如:句子“我是大学生〞的推导过程如下：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生

编译原理(清华)

文法的作用严格定义句子的结构，是判断句子结构合法与否的依据用有穷的规则把无穷的句子集合描述出来

编译原理(清华)

3.2符号和符号串1.字母表–定义:元素的非空有穷集合–例：∑={01}Α={ab,c}–元素也称为符号，字母表也称符号集。–程序语言的字母表由字母数字和若干专用符号组成。

编译原理(清华)

2.符号串–定义:由字母表中的符号组成的任何有穷序列–例：0,00,10是字母表∑={01}上的符号串a,ab,aaca是Α={ab,c}上的符号串–在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同–不含任何符号的符号串称为空串，用ε表示注意:{ε}并不等于空集合{}–符号串长度:符号串中含有符号的个数如:|abc|=3|ε|=0

编译原理(清华)

–符号串的头尾：假使z=xy,那么x是z的头，y是z的尾；假使x是非空的，那么y是z的固有尾，假使y是非空的，那么x是z的固有头–例：z=abcz的头包括：ε,a,ab,abcz的固有头包括：ε,a,abz的尾包括：ε,c,bc,abcz的固有尾包括：ε,c,bc

编译原理(清华)

3.符号串的运算符号串的连接：设x、y是符号串,它们的连接是把y的符号写在x的符号之后得到的符号串xy例如x=ST,y=abu,则xy=STabu显然εx=xε=x

符号串的方幂：把符号串a自身连接n次得到的符号串an=aa…aa例如a1=aa2=aaa0=ε

编译原理(清华)

4.符号串集合：–定义:若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。–符号串集合的乘积：符号串集合A和B的乘积定义为:AB={xy|x∈A且y∈B},即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。若集合A=ab,cdeB=0,1则AB=ab0,ab1,cde0,cde1显然{ε}A=A{ε}=A

编译原理(清华)

–符号串集合的方幂:设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下:A0={ε}A1=A,A2=AAAK=AAA(k个)

编译原理(清华)

5.集合的闭包–闭包集合Σ的闭包Σ*定义如下：Σ*=Σ0∪Σ1∪Σ2∪Σ3∪…例：设有字母表Σ={0,1}则Σ*=Σ0∪Σ1∪Σ2∪…={ε,0,1,00,01,10,11,0