编译程序是将高级语言书写的源程序翻译成低级语言程序.ppt

第2章　文法和语言 QU： 1、A＝B＊ 2、A＝B＊C 在C语言中的，以上两个符号串是否是合法的、正确的？ 2.1　引言 形式化方法：指用一整套带有严格规定的符号体系来描述问题的方法。 2.2　符号串 一、字母表和符号串 二、符号串的运算 一、字母表和符号串 1、字母表（Σ） Def：是元素的非空有穷集合。 Note1： Σ中至少有一个元素；　　2： Σ中可以是字母、数字或其它符号。 Ex1：C语言的字母表　 ΣC＝｛保留字，字母，数字，专用符号，……｝　C语言＝ ΣC　?　一组规则 Ex2：汉语的字母表　 Σ汉＝｛汉字，数字，标点符号，……} 2、符号与符号串 符号（字符）：一个符号是字母表中的元素。 符号串：是符号的有穷序列。 EX1： Σ＝{a, b, c}，则a, b, c, ab, ba都是Σ上的符号串。 Note1：符号串的顺序很重要，如：ab≠ba; 2：不含任何符号的符号串称为空串，用　　　ε 表示。 符号串长度：｜a｜＝1，｜ab｜＝2，｜ ε｜＝0 二、符号串的运算 1、连接 设X和Y是符号串，则串XY称为它们的连接。 EX：X＝ABC，Y＝CDF　　XY=ABCCDF YX=CDFABC Note： ε与X的连接或X与ε的连接＝X 2、集合的乘积 设A、B是符号串的集合，则定义A与B的乘积为： AB＝{xy | x?A, y ? B} EX: A={a, b}, B={c, d}，则AB ={ac,bc,ad,bd} A{?}={?}A=A {?} ?{ }, { }= ? 3、符号串的幂运算 设X是符号串，则X0＝ ? 　　注： X0 ≠1X1＝XX2＝XXXn＝ XX……X 4、集合的幂运算 设A是符号串的集合，则定义： A0＝{?} A1＝A A2＝AA An＝AA……A＝An-1A 5、集合的闭包（A+和A＊） 设A是任意一个集合，则定义： A+＝A1 ∪ A2 ∪ A3… A*＝A0 ∪ A+ 　＝A0 ∪ A1 ∪ A2…… 2.3　文法与语言的形式意义 形式语言 形式语言的描述 文法的形式定义 语言的形式定义 最左、最右推导 归约 递归 一、形式语言 句子?主语谓语间接宾语直接宾语 主语?代词 谓语?动词 间接宾语?代词 直接宾语?冠词名词 代词?He 代词?me 冠词?a 动词?gave 名词?book 句子 ? 主语谓语间接宾语直接宾语 ? 代词谓语间接宾语直接宾语 ? He谓语间接宾语直接宾语 ? He动词间接宾语直接宾语 ? Hegave间接宾语直接宾语 ? Hegave代词直接宾语 ? Hegaveme直接宾语 ? Hegave me冠词名词 ? Hegave mea名词 ? Hegave meabook 二、形式语言的描述 方式一：当语言为有穷集合时，用枚举法表示。 EX：设字母表A＝｛a, b, c｝ L1＝｛a, b, c｝ L2＝｛aa, ab ,a ,ac｝ L3＝｛c, cc,ccc｝ 方式二：当语言为无穷集合时，用文法表示。 EX(续上例）： 设用A表示∑，用式子A?0表示0∈A（读作：“A产生0”）。 符号：“?”定义为“产生”、“生成”、“导出”等。 反复用 A?0 A?1 A?A0 A?A1 以上四条规则式，则可以生成无穷的集合。 三、文法的形式定义 1、规则（产生）式 一个规则式是一个符号与一个符号串的有序偶（对），形如:（A，?）、A? ? 或 A ::＝ ? ，用以描述语言中的句子是怎样产生的。 一组规则可以描述一个语言的语法结构。 非终结符，一般在左边，它能派生出符号、符号串。用大写字母表示,如上述中的A。与之对应地，终结符用小写表示，由它不能派生出任何符号，是一个不可再分的基本单位，即字母表（∑）中的一个元素。 2、文法的形式定义 一个文法是规则的非空有穷集合。常用一个四元组表示，定义为 　G＝（VT，VN，S，P） 其中： VT：所有终结符的集合 VN：所有非终结符的集合 S：开始符 P：规则式的集合 EX: 一个文法G＝（VT，VN，S，P）,其中： VT＝｛0,　1｝　　　　　　所有终结符的集合 VN＝｛A　｝　　　　　 　 所有非终结符的集合 S＝A　　　　　　　　　　 开始符 P＝｛A?0｜1｜A0｜A1｝　规则式的集合 Qu: 给定一个语言L，如何求文法G？ 四、语言的形式定义 1、直接推导 设X，Y是符号串，如果使用一次规则式可以从X推导出Y，则Y为X的直接推导。记为：X?Y 2、+推导　(正推导） 设X，Y是符号串，若使用一次或多次规则可以从X推导出Y，则Y为X的＋推导。 　记为：X ? Y 3、*推导　(广义推导） 设X，Y是符号