编译原理 教学课件 作者 李冬梅 施海虎 第2章 形式语言的基本知识.ppt

《编译原理 教学课件 作者 李冬梅 施海虎 第2章 形式语言的基本知识.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第2章　形式语言的基本知识本章是编译原理课程的理论基础，要求掌握形式语言的基本术语和概念。掌握文法和语言的定义，文法的二义性与递归性的判断方法及句型的分析方法。熟练使用文法定义程序设计语言的单词和语法成分。对形式语言的理论有一个初步认识。教学目标Tuesday,September07,20212.1字母表和符号串的基本概念2.2文法和语言的形式定义2.3句型的分析2.4文法和语言的分类2.5PL/0编译程序概述教学内容Tuesday,September07,2021字母表：符号的非空有限集例：={0，1}2.1　字母表和符号串符

2、号：字母表中的元素例：0，1符号串：由字母表中的符号组成的任何有穷序列例：0,1,01,10,011，..空符号串：无任何符号的符号串，用ε表示C语言的字母表A＝{a,b,…,0,1,…,9,+,－,×,_/,(,),=…if,else,for...}不对如={if,else,for,while}符号就是字符，对吗？Tuesday,September07,2021符号串的前缀和后缀:从符号串s的尾部删去若干个(包括0个)符号之后所余下的部分称为s的前缀ε，0，01及011都是符号串011的前缀ε，1，11及011都是符号串011

3、的后缀符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。例：={a，b，c}A={a,aa,ac}Tuesday,September07,2021符号串的运算符号串x和y的连接:是把y的符号写在x的符号之后得到的符号串xy例如x=00，y=11，则xy=0011对于任意一个符号串s，有εs=sε=s符号串的连接运算Tuesday,September07,2021符号串自身连接n次得到的符号串sn定义为ss…ss，包括n个s，称为符号串的幂运算s0=ε，s1=s，s2=ss，……设s=01，则

4、s0=εs1=01s2=0101……符号串的幂运算Tuesday,September07,2021设A、B为符号串集合，则A和B的乘积定义为：AB＝{xy

5、x∈A,y∈B}例如，A＝{a,b}，B={c,d}则AB=符号串集合的乘积{ac,ad,bc,bd}Tuesday,September07,2021有符号串集合A，定义A0={ε},A1=A,A2=AA,A3=AAA,……An＝An-1A=AAn-1，n>0例如，A＝{0,1}，则A0=A1=A2=A3=符号串集合的幂运算{ε}{0,1}{00,01,10,11}{000,0

6、01,010,011,100,101,110,111}Tuesday,September07,2021设A是符号串集合，定义A＋＝A1∪A2∪A3∪……∪An∪……称为集合A的正闭包。A*＝A0∪A＋称为集合A的闭包。例：A={x,y}A＋＝？A*＝？{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}A1A2A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}A0A1A2A3符号串集合的闭包运算Tuesday,September07,2021Σ的闭包*表示上的一切符号串（包括ε

7、）组成的集合Σ的正闭包+表示上的除ε外的所有符号串组成的集合例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}Tuesday,September07,2021若A为某语言的字母表A＝{a,b,…,0,1,…,9,+,－,×,_/,(,),=…if,else,for...}B为单词集B={if,else,for,……,<标识符>,<常量>,……}则BA*。语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序C为什么对符号

8、、符号串、符号串集合以及它们的运算感兴趣？Tuesday,September07,2021语言是由句子组成的集合，是由一组符号所构成的集合字母表上的一个语言是上的一些符号串的集合字母表上的每个语言是*的一个子集集合{a,aa,aaa,…}或表示为{w

9、w∈Σ*且w=an,n≥1}为字母表上的一个语言例如：字母表Σ={a,b},Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}集合{ab,aabb,aaabbb,…,anbn,…}或表示为{w

10、w∈Σ*且w=anbn,n≥1}为字母表上的一个语言Tuesda

11、y,September07,20212.2　文法和语言的形式定义文法是对语言结构的定义与描述。（或称为“语法”）。<赋值语句>::=<标识符>“=”<表达式><表达式>::=<表达式>“+”<表达式>

12、<表达式>“*”<表达式><表达式>::=“(