[编译原理第2章文法和语言.ppt

I will greet this lecture with love in my heart. 主讲人：韩士元 Email: shiyuanhan@126.com Tel: +86 基本概念 字母表、符号、符号串、闭包等 文法的定义 文法的分类 Chromsky 对文法的分类 文法和语言 推导、归约、句型、句子、语言 语法分析树和二义性 第二章 文法和语言 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 2.1 文法和语言的定义 例句：int i = 0; 包含字母i, n, t, =, 0, ; , 所有字母形成字母表； 符号串，如int 定义2.1 字母表：字母表∑是符号元素的非空有限集合。 定义2.2 符号（字符）：字母表中的元素。 定义2.3 符号串（字符串）：字母表中的符号所组成的任何有穷序列。 如字母表∑={a,b}，则a,b是字母表∑中的元素，a,b,aa,ab,…都是符号串。 空符号串：不含任何符号的符号串，用ε表示。 字母表，符号，符号串 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 2.1 文法和语言的定义 定义2.4 符号串x和y的连接：指x和y的符号按先后顺序排列在一起组成的新的符号串，用xy表示。 例：若∑={a,b}, x=ab, y=ba, 则xy=abba, yx=baab。 注意：（1）xy≠yx； （2）εx=xε=x。 定义2.5 符号串的长度：指符号串中符号的个数。 例：|ab|=2, |aabb|=4, |ε|=0。 字符串连接、字符串长度 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 2.1 文法和语言的定义 定义2.6 符号串的前缀和后缀：分别指符号串的左部和右部任意字符串。 例：ab的前缀有ε、a、ab；后缀有ε、b、ab。 定义2.7 符号串集合的乘积：设A、B是字母表∑上的符号串集合，则定义A与B的乘积：AB={xy|x∈A，y∈B}。 例：设∑={a，b，c，d}，令A={aa,bb}，B={cc,dd}, 则 AB={aacc, aadd, bbcc,bbdd}, BA={ccaa,ccbb,ddaa,ddbb}。显然AB≠BA 定义空集合：Φ={ε}，有{ε}A=A{ε}=A。 前缀、后缀、乘积 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 2.1 文法和语言的定义 定义2.8 符号串的方幂：设x是符号串，则：x0=ε, x1=x, x2=xx, …, xn=x…x(n个) 定义2.9 符号串集合A的方幂：A0={ε}, A1=A, A2=AA, …, An=A…A(n个A) A的正闭包：A+=A1∪A2∪… A的闭包：A*=A0∪A1∪A2∪… 显然：A*= A0∪A+, A+=AA* 问题：A = {0,1}, 则A+表示的集合意义？ 方幂、正闭包、闭包 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 2.1 文法和语言的定义 什么是文法 文法是定义或描述语法结构的一组形式规则，是规则的非空有穷集合 规则又称为重写规则，产生式或生成式，每个产生式为α?β或 α::=β， α是某字母表A的正闭包A+的一个符号称为规则的左部； β是A*中的一个符号，称为规则的右部。 α与β的区别？ 文法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 2.1 文法和语言的定义 什么是文法 文法是定义或描述语法结构一组形式规则，是