第2章形式语言的基础知识ppt课件.ppt

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

1、第2章形式语言的基础知识内容提要形式语言文法和语言分析树2.1形式语言符号和字符串符号：抽象实体，不加以形式定义。就像几何学中的“点”。或者叫原子概念，凭直觉去体会。字母表：有限个符号的集合。字母表一般用记。例如,英语的字母表={a,b,…,z,A,B,…,Z}；汉语的字母表由汉字构成。字符串：字母表中符号的有穷序列。字符串的长度：组成该字符串的符号的个数。字符串的长度记作

2、

3、。例如字符串banana的长度为6。空字符串记作，由0个符号组成，故

4、

5、=0。字符串的前缀：该字符串领头的若干符号。字符串的后缀：该字符串结尾的若干符号。例如，字符串abc

6、具有前缀，a，ab和abc；其后缀有，c，bc，abc。若字符串的前缀（或后缀）不是字符串本身，则称之为真前缀（或真后缀）。字符串的子串：去掉字符串的一个前缀和后缀后得到的字符串。例如，nan是banana的一个子串。字符串的子序列：从字符串中删除0个或多个符号后得到的串（这些被删除的符号可以不相邻）。例如，baaa是banana的子序列。字符串的运算字符串的连接：如果x和y是字符串，那么x和y的连接xy是把y接到x后面所形成的字符串。例如，如果x=dog，y=house，则xy=doghouse。由的定义，显然有==。字符串的方幂：设x是字

7、符串，把x自身连接n次得到字符串z，即z=xxx…x，称为字符串x的n次方幂，记作z=xn。我们规定x0=。例如，设x=AB，则x0=，x1=AB，x2=ABAB，x3=ABABAB。对于，n>0，有xn=xxn-1=xn-1x。字符串集合的连接：两个字符串集合A和B的连接AB={xy

8、xA，yB}，即AB是满足x属于A，y属于B的所有字符串xy所组成的集合。例如，若A={a,b}，B={c,d}，则AB={ac,ad,bc,bd}。另外，我们有{}A=A{}=A。对任意字符串集合A，An=AAA…A，即n个A相连。A0定义为{}。Kleene

9、闭包：一个固定的字母表上所有的字符串的集合称为集合的Kleene闭包，记作*。根据定义，我们有*=012…n…。正闭包：+=123…n…称为的正闭包。显然有*=0++=*=*形式语言语言：给定字母表上的任意一个字符串集合，即*的子集（*本身也是自己的子集，所以*也是语言）。空集和由空字符串组成的集合{}都是语言。2.2文法和语言文法是程序语言的生成系统，而自动机则是程序语言的识别系统。用文法可以精确地定义一个语言，并依据该文法构造出识别这个语言的自动机。因此，文法对程序语言和编译程序的构

10、造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述。2.2.1基本概念定义文法文法表示成四元组G=(VT,VN,S,P)，其中：(1)VT为终结符号(terminal)集，是一个非空有限集，它的每个元素称为终结符号；(2)VN为非终结符(non-terminal)集，也是一个非空有限集，其每个元素称为非终结符号。要求VTVN=；(3)S为一文法开始符号，也称作识别符号，是一个特殊的非终结符号，即SVN；(4)P是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(,)，通常写作

11、读作“是”或“定义为”。在此，为产生式的左部，而为产生式的右部，、是由终结符和非终结符组成的符号串，(VTVN)+且至少有一个非终结符，而(VTVN)*。终结符和非终结符的集合用符号V表示，即V=VTVN。终结符代表了语法的最小元素。非终结符号也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符是一个类、一个集合。例如，在程序语言中，可以把变量、常数、“+”、“*”等看作是终结符，而像“算术表达式”这个非终结符则代表着一定算术表达式组成的类，如i*(i+i)、i+i+i等；也即每个非终结符代

12、表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。产生式是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。P1，P2，…，Pn可将这些有相同左部的产生式合并为一个，即缩写成P1∣2∣…∣n其中，每个i(i=1,2,…,n)称为P的一个候选式，直竖“∣”读为“或”，它与“”一样是用来描述文法的元语言符号(即不属于的字符)。例2.1文法G=(VN,VT,P,S)，其中VN={S}，VT={0,1}，P={S0S1,S01}。例2.2文法G=(VN,VT,P,S)，其中VN={<标识符>,<字母>,<数字>}

13、，VT={a,,z,0,,9}，P={<标识符>