资源描述：
《《形式语言基础》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文法的基本运算文法有两种基本运算：推导，归约。星推导():αβⅠ．直
