第二章编译基础§2.0概述§2.0概述形式化方法：是用一整套带有严格规定的符号体系来描述问题的方法。2.符号（字符）：字母表中元素。3.符号串：用字母表中的符号组成的任何有穷序列，也称字。例如：a,ab,bba,acab,…注意：①符号串中符号的顺序是很重要的。②不包含任何符号的符号串称空串，记为ε。|ε|=0③一个字母表上全部符号的集合是无穷的。4.符号串的前缀、后缀以及子串：设x是一符号串，例如：x=abc符号串的前缀：从x的尾部删除若干个（>=0）符号后所余下的部分。例如：ε，a，ab，abc符号串的后缀：从x的头部删除若干个（>=0）符号后所余下的部分。例如：ε，c，bc，abc子串：从x中删除前缀和后缀之后所余下的部分。例如：ε，a，b，ab，bc，abc二.符号串的运算1．符号串的连接：设x，y是符号串，则串xy称为它们的连接。例如：设x=myy=computerxy=mycomputeryx=computermy注意：对任意xXε=εX=X2．集合的和与乘积：设A，B是符号串的集合，则：A∪B={ω|ω∈A或ω∈B}AB={xy|x∈A且y∈B}例如：设A={a,b}B={c,d}则：A∪B={a,b,c,d}AB={ac,ad,bc,bd}注意：Φ∪A=A∪Φ=AΦA=AΦ=Φ{ε}A=A{ε}=AΦ={}≠{ε}3.符号串的幂运算：若x是符号串，则x0=ε,x1=x,x2=xx,…例如：设x=abc则：x0=ε,x1=abc,x2=abcabc,…4.集合的幂运算：若A是符号串的集合，则A0={ε},A1=A,A2=AA,…例如：设A={a,b}则：A0={ε},A1={a,b},A2={aa,ab,ba,bb},…5.集合的A＋(正闭包)和A*（自反传递闭包）:设A为任一集合，则：A＋=A1∪A2∪A3∪…∪An∪…（A上所有符号串所组成的集合）A*=A0∪A＋={ε}∪A＋例如：设A={a,b,c}A＋={a,b,c,aa,ab,ac,ba,bb,bc,…}A*={ε,a,b,c,aa,ab,ac,ba,bb,bc,…}§2.2文法和语言的形式定义2．用文法描述语言例如：设有字母表∑={0，1}∑+={0，1，00，01，11，10，000，100，…}用A表示∑+，A→0（定义为，生成，导出）用产生式表示∑+：A→0A→1A→A0A→A13．用自动机识别语言：构造一种装置来识别语言，它可以判断某符号串是否是该语言的句子。例如：1100→→是（接收）11ab→→不是（不接收）三．文法的形式定义3．文法的形式定义：是规则的非空有穷集合，通常定义为四元组：G[S]=（Vn，Vt，P，S）其中：Vn：规则中非终结符的集合。Vn={A}Vt：规则中终结符的集合。Vt={0，1}P：文法规则式的集合。P:A→0A→1A→A0A→A1S：文法的开始符号（识别符号）由它开始识别我们所定义的语言。S=A例1例2例3例4例5继续例1．设有字母表∑={a，b}，请为语言L={a2n,b2n|n>=1}设计一个文法。首先分析语言中串的结构特征：L={aa,bb,aaaa,bbbb,…}（偶数个a或偶数个b组成）G[S]=（Vn，Vt，P，S）其中：Vn={A,B,D}Vt={a，b}P:A→aa|aaB|bb|bbDB→aa|aaBD→bb|bbDS=A易错：A→aa|aaA|bb|bbA会出现句子aabb扩大了语言范围问题：描述是否唯一？（回答不唯一）P1:A→B|DB→aa|aaBD→bb|bbD等价文法：P2:A→B|DB→aa|aBaD→bb|bDb返回例2．已知语言L={w|w是0和1的个数都为偶数的0，1串}。分析句子结构特征：0011001100000101①S→0A|1B(A,B奇数个0,1)②A→0B→1③推出无穷串：A→0SB→1S④产生0101串：C→0B|1AA→1CB→0C文法：G[L]=（{A,B,C,S},{0,1},P，S）P:S→0A|1BA→0S|1C|0