第2章 形式语言及基础知识.pptVIP

第2章 形式语言的基础知识 内容提要 形式语言 文法和语言 分析树 2.1 形式语言 符号和字符串 符号：抽象实体，不加以形式定义。就像几何学中的“点”。或者叫原子概念，凭直觉去体会。 字母表：有限个符号的集合。字母表一般用?记。例如,英语的字母表?={a,b,…,z,A,B,…,Z}；汉语的字母表由汉字构成。 字符串：字母表中符号的有穷序列。 字符串的长度：组成该字符串的符号的个数。字符串?的长度记作|?|。 例如字符串banana的长度为6。空字符串记作?，由0个符号组成，故|?|=0。 字符串的前缀：该字符串领头的若干符号。 字符串的后缀：该字符串结尾的若干符号。 例如，字符串abc具有前缀?，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是字符串，把x自身连接n次得到字符串z，即z=xxx…x，称为字符串x的n次方幂，记作z=xn。我们规定x0=?。 例如，设x=AB，则x0=?，x1=AB，x2=ABAB，x3=ABABAB。对于，n0，有xn=xxn-1=xn-1x。 字符串集合的连接：两个字符串集合A和B的连接AB={xy|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闭包：一个固定的字母表?上所有的字符串的集合称为集合?的Kleene闭包，记作?*。根据定义，我们有?*=?0??1??2?…??n…。 正闭包：?+=?1??2??3?…??n…称为?的正闭包。显然有 ?*=?0??+ ?+=??*=?*? 形式语言 语言：给定字母表上的任意一个字符串集合，即?*的子集（?*本身也是自己的子集，所以?*也是语言）。空集?和由空字符串组成的集合{?}都是语言。 2.2 文法和语言 文法是程序语言的生成系统，而自动机则是程序语言的识别系统。用文法可以精确地定义一个语言，并依据该文法构造出识别这个语言的自动机。因此，文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法描述。 2.2.1 基本概念 定义 文法 文法表示成四元组G=(VT, VN, S, P)，其中： (1)VT为终结符号(terminal)集，是一个非空有限集，它的每个元素称为终结符号； (2)VN为非终结符(non-terminal)集，也是一个非空有限集，其每个元素称为非终结符号。 要求VT?VN=?； (3)S为一文法开始符号，也称作识别符号，是一个特殊的非终结符号，即S?VN； (4)P是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(?, ?)，通常写作 ??? 读作“?是?”或“?定义为?”。在此，?为产生式的左部，而?为产生式的右部，?、?是由终结符和非终结符组成的符号串， ??(VT?VN)+且至少有一个非终结符，而??(VT?VN)*。 终结符和非终结符的集合用符号V表示，即V=VT?VN。 终结符代表了语法的最小元素。 非终结符号也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符是一个类、一个集合。 例如，在程序语言中，可以把变量、常数、“+”、“*”等看作是终结符，而像“算术表达式”这个非终结符则代表着一定算术表达式组成的类，如i*(i+i)、i+i+i等；也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。 产生式是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。 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}， V