第2章文法和语言ppt课件.ppt

《第2章文法和语言ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章文法和语言的基本知识形式语言的理论是编译的重要理论基础。有关形式语言的概念包括：字母表和符号串文法和语言的形式定义短语、直接短语和句柄语法树和文法的二义性文法和语言的分类第二章文法和语言的基本知识2.1概述2.2字母表和符号串2.3法和语言的形式定义2.4短语、直接短语和句柄2.5语法树与文法的二义性2.6文法和语言的分类2.7自上而下的分析方法2.8有关文法实用中的一些说明2.1概述语言是一个记号系统汉语--符合汉语语法的句子的全体英语--符合英语语法的句子的全体程序设计语言--该语言的程序的

2、全体2.1概述对程序设计语言非形式化的描述：语法：定义每个程序构成的规则语义：定义每个程序的意义语用：每个程序(语句)的用途例s=2*3.1416*r*(h+r)的非形式化的描述：语法——赋值语句有一个变量、一个赋值号后跟表达式构成语义——计算=右部的值，送入左部变量语用——赋值语句用来计算和保存表达式的值2.1概述非形式化描述——不清晰不准确形式化描述——用一整套带有严格规定的符号体系来描述问题的方法用形式语言描述各种程序设计语言程序设计语言包括:语法和语义语法(syntax)定义:是一组规则，用它

3、可以形成和产生一个合适的程序描述工具:文法作用:定义什么样的符号序列是合法的，与符号的含义无关。形式语言的基本形式例:“我是大学生”是汉语的一个句子用EBNF来表示汉语句子的构成规则：〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉例如:句子“我是大学生”的推导过程如下：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语

4、〉我是〈直接宾语〉我是〈名词〉我是大学生2.2字母表和符号串1、字母表和符号定义:元素的非空有穷集合例：∑={0‚1}∑={a‚b,c}元素也称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。2、符号串定义:由字母表中的符号组成的任何有穷序列例：字母表∑={0‚1}上的符号串：0,00,10等Α={a‚b,c}上的符号串：a,ab,aaca等2、符号串在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如ab和ba不同不含任何符号的符号串称为空串，用ε表示注意:{ε}

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

6、abc

7、=3

8、ε

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

10、xy

11、x∈A且y∈B}，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。若集合A=ab,cdeB=0,1则AB=ab0,ab1,cde0,cde1显然{ε}A=A{ε}=？4、符号串集合符号串集合的方幂:设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下:A0={ε}A1=A,A2=AAAk=AA......A(k个)=AAk-1=Ak-1A例：A={0,1}5、集合的闭包闭包集合A的闭包A*(正闭包A+)定义如下：A+=A1∪A2∪A3∪…An∪…

12、A*=A0∪A1∪A2∪A3∪…An∪…例：设有字母表Σ={0,1}Σ+=Σ1∪Σ2∪…={0,1,00,01,10,11,000,…}即Σ+表示Σ上01构成的所有符号串的集合。Σ*=Σ0∪Σ1∪Σ2∪…={ε,0,1,00,01,10,11,000,…}字母表上的一个语言是上符合某种规则的一些符号串的集合，是*的一个子集。例如：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}1.集合{ab,aabb,aaabbb,…,anbn,…}或{w

13、w∈Σ*且w=anbn,

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

15、w∈Σ*且w=an,n≥1}为字母表上的一个语言。ε是一个语言。即是一个语言。5、集合的闭包重点回顾解释程序(interpreter)与编译程序编译程序是将源程序翻译成目标程序后再执行该目标程序解释程序则是逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产生目标程序。编译的基本过程源程序词法分析程序语法分析程序语义分析程序中间代码生成程序代码优化程序目标代码生成