第2章形式语言的基础知识

第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}，VT={0,1}，P={S0S1,S01}。例2.2文法G=(VN,VT,P,S)，其中VN={标识符,字母,数字}，VT={a,,z,0,,9}，P={标识符字母标识符标识符字母标识符标识符数字字母a||z数字0||9}S=标识符习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成G[S]，其中S是开始符号定义直接推导&直接规约设文法G=(VT,VN,S,P)且、(VTVN)*，如果存在产生式A((VTVN)*)，则称A可直接推导出，或者说是A的直接推导，记做A其中“”表示直接推导出，是应用产生规则进行推导的记号。反过来，则称可直接规约到A，或者说A是的直接规约。注意“”与“”不同，“”是产生式中的定义记号。直接推导是对文法符号串A中的非终结符A用相应的产生式A的右部来替换，从而得到。例如，对例2.1和例2.2的文法G，可以给出一些直接推导的例子：0S10011,S0S1,0S100S11标识符标识符字母标识符字母数字字母字母数字S0S1,S01标识符字母标识符标识符字母标识符标识符数字字母a||z数字0||9定义推导&规约的传递闭包如果存在一个自1至n的直接推导序列：123…n(n1)，则我们称1可推导出n，或称n规约到1，记为1+n，它表示从1出发经过一步或若干步可推导出n。定义推导&规约的自反传递闭包如果有1+n或1=n，则记1*n，表示从1出发，经过0步或若干步可推导出n。例如，对例2.1的文法，0S100+001100，当然也可以是0S100*001100。对2.2的文法，标识符+x1，当然也可以是标识符*x1。S0S1,S01标识符字母标识符标识符字母标识符标识符数字字母a||z数字0||9定义句型&句子设G[S]是一文法，S是它的开始符号，如果S*，(VTVN)*，则称是文法G[S]的一个句型；如果VT*，则称是文法G[S]的一个句子。例如，S，0S1，000111都是例2.1的文法G的句型，其中000111是G的句子。标识符字母，字母数字，a1等都是例2.2的文法G的句型，其中a1是G的句子。S0S1,S01标识符字母标识符标识符字母标识符标识符数字字母a||z数字0||9定义文法的语言文法G[S]产生的句子的全体称为由文法G[S]产生的语言，记为L(G)，即有L(G)={∣S*且VT*}。例如，例2.1的文法产生的语言的句子具有0n1n的形式。定义文法等价若L(G1)=L(G2)，则称文法G1和G2是等价的。例如，文法G[A]:A0R，A01，RA1。和例2.1的文法等价。S0S1,S012.1.2Chomsky谱系语言学家NoamChomsky于1956年首先建立了形式语言的描述，定义了四类文法及相应的形式语言，并分别与相应的识别系统相联系，它对程序语言的设计、编译方法、计算复杂性等方面都产生了重大影响。Chomsky把文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。0型文法与0型语言(对应图灵机)如果文法G的每一个产生式具有下列形式：其中，V*VNV*，即至少含有一个非终结符；V*；则称文法G为0型文法或短语结构文法，记为PSG(PhraseStructureGrammar)。0型文法相应的语言称为0型语言或称递归可枚举集，它的识别系统是图灵(Turing)机。1型文法与1型语言(对应线性界限自动机)文法G的产生式在0型文法的基础上增加了字符长度上满足||||的限制，则称文法G为1型文法或上下文有关文法，记为CSG(Context-SensitiveGrammar)。1型文法相应的语言称为1型语言或上下文有关语言，它的识别系统是线性界限自动机。1型文法的另一种定义方法是文法G的每一个产生式具有下列形式：A其中，AV*，AVN，V+；显然它满足前述定义的长度限制，但它更明确地表达了上下文有关的特性，即A必须在、的上下文环境中才能被所替换。自然语言的语法应属于上下文有关文法。2型文法与2型语言(对应下推自动机)文法G的每一个产生式具有下列形式：A其中，AVN，V*，则称文法G为2型文法或上下文无关文法，记为CFG(Context-FreeGrammar)。2型文法相应的语言称为2型语言或上下文无关语言，它的识别系统是下推自动机。程序设计语言的语法是上下文无关的。3型文法与3型语言(对应有限自动机)文法G的每个产生式具有下列形式：A或AB其中，A、BVN，VT*，则文法G称为右线性文法。若每个产生式具有下列形式：A或AB则文法G称为左线性文法。右线性和左线性文法都称为3型文法、正规文法，记为RG(RegularGrammar)。3型文法相应的语言为3型语言或正规语言，它的识别系统是有限自动机。例2.1和例2.2中的文法都是上下文无关的。例2.3设G=(VN,VT,P,S)，VN={S,B,E}，VT={a,b,e}，P={SaSBE,SaBE,EBBE,aBab,bBbb,bEbe,eEee}文法G是上下文有关的，L(G)={anbnen|n1}S0S1,S01标识符字母标识符标识符字母标识符标识符数字字母a||z数字0||9SaSBE(SaSBE)aaBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE(bBbb)aabbeE(bEbe)aabbee(eEee)SaSBEaaSBEBEaaaBEBEBE四类文法的联系与区别联系：从0型文法到3型文法逐渐增加限制。1~3型文法都属于0型文法，2、3型文法均属于1型文法，3型文法属于2型文法。区别：(1)1型文法中不允许有形如“A”的产生式存在，而2、3型文法则允许形如“A”的产生式存在；(2)0、1型文法的产生式左部存在含有终结符号的符号串或两个以上的非终结符，而2型和3型文法的产生式左部只允许是单个的非终结符号。文法的应用在编译方法中，通常用3型文法来描述高级程序语言的词法部分，然后用有限自动机FA来识别高级语言的单词；利用2型文法来描述高级语言的语法部分，然后用下推自动机PDA(Push-DownAutomata)来识别高级语言的各种语法成分。贯穿词法分析和语法分析始终如一的思想是：语言的描述和语言的识别是表示一个语言的两个不同的侧面，二者缺一不可。用正规文法和上下文无关文法描述语言时的识别方法(即自动机)不同。通