资源描述:
《《形式语言基础》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、编译原理如何让计算机认识、理解和执行高级程序设计语言?2007年2月【内容提要】第2章形式语言基础2.1语言是符号串集合2.2文法是定义语言的规则集2.3怎样用文法定义语言2.4各种语法成分定义与求解…形式语言是真实语言(程序设计语言、自然语言…)的一种数学模型;很适合于计算机处理。形式语言的基本观点是:语言是符号串之集合!2.1语言是符号串集合形式语言可定义为:字母表上的符号,按一定的规则组成的所有符号串之集合;其中的每个符号串称为句子。【例2.1】L1={00,01,10,11};【例2.2】L2={abnc,bn
2、n≥0};句型1a
3、bnc:有句子:ac,abc,abbc,abbbc,…句型2bn:有句子:,b,bb,bbb,…【注】符号串的方幂运算:b0=(空符号串),b1=b,b2=bb,b3=bbb,…有限语言无限语言仅有四个句子:00,01,10,112.1.1字母表字母表是语言的基本符号集,是语言的第一要素;其内容随着语言的研究范畴不同而不同。【例2.3】机器语言字符集:∑1={0,1};【例2.4】高级语言字符集:∑2={a,b,…,+,-,…,(,),…};【例2.5】汉语字符集:∑3={啊,…,吃…,饭,…,我,…};【例2.6】汉语单词集:∑4=
4、{毕业,…,吃…,打击,…,新华社,…};…【注】字母表是符号的有限集;而由字母表中符号通过规则组成的句子的集合(语言),则可能是无限集。规则集是语言中句子的组成的规律和法则,它可以通过某种运算,把该语言中的句子产生出来;故而,规则集又称为产生式集。⑴S,A—定义的对象(S句子,最大的定义对象,又称为开始符号;A为句型aAc的一个短语),⑵a,b,c--为字母表∑中的符号;ε-空符号串。⑶->,
5、--为描述符号(->定义为;
6、或者是)【例2.7】L={abnc,bn
7、n≥0},字母表:∑={a,b,c};展开:L={ac,abc,abbc
8、,…;,b,bb,…}S->aAc
9、AA->bA
10、规则集:其中:2.1.2规则集①S=>aAc=>aεc=ac②S=>aAc=>abAc=>abεc=abc③S=>aAc=>abAc=>abbAc=>abbc…一个句子!又一个句子!∴Sabnc,n≥0=>+再一个句子!句子的产生过程:从开始符号出发,对符号串中的定义对象,用其规则右部替换之(称为推导);产生的新符号串仍如此进行,直到新符号串中不再出现定义的对象为止,则最终的符号串就是一个句子。用规则产生句子的过程:同理Sbn,n≥0=>+2.1.3怎样利用规则产生句子S->aAc
11、A
12、A->bA
13、G(S):A->或者A->
14、2.2文法是定义语言的规则集2.2.1文法的形式定义VN:非终结符集(定义的对象集,如:语法成分等);VT:终结符集(字母表);Z:开始符号(研究范畴中,最大的定义对象);P:规则集(又称产生式集):G(Z)=(VN,VT,Z,P)※上下文无关文法可定义为四元组:每一种形式语言,都能由相应的有限规则集来描述;称为该语言的文法(grammar)。【注】描述符号:->(定义为),
15、(或者是)文法符号:Z,A∈VN,,∈(VN+VT)*规则形式闭包--由VN+VT中符号组成的全部符号串集合。※
16、文法应用示例:G(N):N->dN
17、d【例2.8】无符号整数文法:【无符号整数】由数字0—9组成的任意符号串。其中:d(泛指0—9的任意数字),【标识符】指字母开头的字母、数字序列。I->ℓAA->ℓA
18、dA
19、【例2.9】标识符文法:则则G(I):其中:ℓ(泛指a—z的任一字母)d(泛指0—9的任一数字),注上述两个文法的四元组,请自行确认之。其中VN={E(算术表达式),T(项),F(因式)};VT={i(变量或常数),+,-,*,/,(,)};Z=E;P:【例2.10】简单算术表达式文法E->T
20、E+T
21、E-TT->F
22、T*F
23、T/
24、FF->i
25、(E)令G(Z)=(VN,VT,Z,P)【注】此文法定义了算术表达式的层次嵌套结构:(表达式)表达式项因式项项因式因式i+-+-…+-*/*/*/…※利用文法求解算术表达式示例:⒉证明i*(i+i-i)是一个算术表达式:∵∴=>+Ei*(i+i-i)=>T=>T*F=>T*(E)=>T*(E-T)=>T*(E+T-T)=>F*(E+T-T)=>i*(E+T-T)=>…观察推导过程,可以看到:一旦产生式选择错了,会导致失败!=>i*(i+i-i)我们从两个方面讨论该文法的应用:⒈随意产生出一个算术表达式:E=>E+T=>T+T=
26、>F+T=>i+T=>i+F=>i+iG(E):E->T
27、E+T
28、E-TT->F
29、T*F
30、T/FF->i
31、(E)E2.2.2文法的基本运算文法有两种基本运算:推导,归约。星推导():αβⅠ.直