m6pifChapt3.pptVIP免费

国防科技大学计算机系602教研室复习：程序语言的语法描述几个概念:考虑一个有穷字母表∑字符集其中每一个元素称为一个字符∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε国防科技大学计算机系602教研室复习：程序语言的语法描述∑*的子集U和V的连接（积）定义为UV＝{|U&V}V自身的n次积记为Vn=VV…V规定V0={}，令V*=V0∪V1∪V2∪V3∪…称V*是V的闭包;记V＋＝VV*，称V+是V的正规闭包。国防科技大学计算机系602教研室复习：程序语言的语法描述上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTVN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VTVN)*开始符S至少必须在某个产生式的左部出现一次。国防科技大学计算机系602教研室复习：程序语言的语法描述定义：称A直接推出，即A仅当A是一个产生式，且，(VTVN)*。如果12n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。国防科技大学计算机系602教研室通常，用表示：从1出发，经过一步或若干步，可以推出n。n1n*1用表示：从1出发，经过0步或若干步，可以推出n。*所以：即或*S},|{)(*TVSGL定义：假定G是一个文法，S是它的开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。国防科技大学计算机系602教研室复习：程序语言的语法描述最左推导：任何一步都是对中的最左非终结符进行替换。最右推导：任何一步都是对中的最右非终结符进行替换。国防科技大学计算机系602教研室复习：程序语言的语法描述用一张图表示一个句型的推导,称为语法树。E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E(E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i)国防科技大学计算机系602教研室复习：程序语言的语法描述定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。国防科技大学计算机...