PPT《*》

* 《编译原理与技术》讲义 * 编译原理与技术 --文法和分析 * 《编译原理与技术》讲义 * 文法和分析 形式语言中若干基本概念语言文法(上下文无关文法)分析树与二义性形式语言分类乔姆斯基分类 * 《编译原理与技术》讲义 * 若干基本概念 语言语言L={ s | s 是∑上任一字符串},s称为语言L的一个句子.

字母表∑-符号/字符的非空有限集合e.g. 二进制数的∑={0,1},而十进制数的∑={0,1,…,9}∑*-表示∑上所有字符串的集合;

L?∑*字符串- ∑上若干字符组成的有穷序列 * 《编译原理与技术》讲义 * 若干基本概念 语言字符串e.g. ∑={0,1}上的0,1串(二进制数)如0111,10101;

∑={a,b}上的 a, b, aa , abab, …空串-?, ?∈ ∑*,串长-|s|={s中所含字符的个数},| ?|=0串的连接运算-任意串x,y,一般地,xy?yx,x?= ?x串的前缀- 任意串x,从其第一个字符(最左字符)起的字符序列是其前缀.?亦是.e.g. x = abc, 则?,a,ab,abc均是x的前缀 * 《编译原理与技术》讲义 * 若干基本概念 语言的运算 描述运算 语言L和语言M 连接(积) LM={ xy| x∈L 且y∈M } 合并(和) L∪M={x| x∈L 或x∈M } 闭包 L*=L0∪L1∪L2∪…= 正闭包 L+=L1∪L2∪L3∪…= * 《编译原理与技术》讲义 * 若干基本概念 语言e.g. L={a,b,…,z}, D={0,1,…,9}, B={ _ } L∪D = {…} LD={…} L*={…} L(L∪D)L∪ B)(L∪D∪B)*={…} D+={} * 《编译原理与技术》讲义 * 若干基本概念 文法文法G=(VT,VN,S,P)定义为一个四元组,其中:VT-终结符号集合;

VN-非终结符号集合,VT∩VN=? ;

S-文法开始符号,S∈VN ;

P-文法产生式集合,每一产生式形如???, 其中?,? ∈ (VT∪VN )*,?至少含有一个非 终结符, ? 称为相应产生式的左部,?则 为产生式的右部. * 《编译原理与技术》讲义 * 若干基本概念 文法是描述语言的语法结构的形式规则,其中,终结符号(集合)表示组成语言的基本成份,如标识符、常数,算符等;

非终结符号(集合)代表语法实体(范畴),如算术表达式、条件语句、过程等;

而开始符号作为一特殊的非终结符号则代表着语言中 最大 的语法实体-语言的目标(也称为 句子 ),如 程序 .产生式看作定义语法实体的一种书写规则,通过它,可以了解较 大 的语法实体如何由较 小 的语法实体(非终结符号)和/或语言基本成份(终结符号)来构成的. * 《编译原理与技术》讲义 * 若干基本概念 上下文无关文法(context-free grammar)同样定义为四元组(VT,VN,S,P),P中的产生式形式为:A??,?∈ (VT∪VN )*,而A ∈VN;

开始符号S须在产生式的左部出现至少一次. * 《编译原理与技术》讲义 * 若干基本概念 e.g.1 算术表达式(含+,*运算) 递归定义如下:1)变量是一个算术表达式;

2)若E1和E2是算术表达式,则E1 + E2, E1 * E2和(E1)也 是算术表达式. * 《编译原理与技术》讲义 * 若干基本概念 文法e.g.1 文法G1=({i,E},E,P),其中产生式集合(左递归形式) P:E?E+EE?E*EE?(E)E?i * 《编译原理与技术》讲义 * 若干基本概念 文法 e.g. 1文法G1=({i,E},E,P),其中产生式集合 P:E?E+E P: E?E+EE?E*E | E*EE?(E)E)E? i | i 相同左部的产生式 * 《编译原理与技术》讲义 * 若干基本概念 文法e.g.2 文法G2=({i,E,T,F},E,P),P: E?E + T | T T?T * F | F F?( E ) | i * 《编译原理与技术》讲义 * 若干基本概念 文法G2,P: E?E + T | T T?T * F | F F?( E ) | i 文法G1,P:E?E+E | E*E | (E) | i 文法G1和G2描述了相同的语言-算术表达式 * 《编译原理与技术》讲义 * 若干基本概念 文法产生的语言 e.g.3 i + i是算术表达式,那么文法G1是如何 描述 它的?文法G2呢? * 《编译原理与技术》讲义 * 若干基本概念 文法产生的语言 e.g.3 G1的描述: E ? E + E ? i + E ? i + iG2的描述:E ? E + T ? T + T ? F + T ? i + T ? i + F ? i + i * 《编译原理与技术》讲义 * 若干基本概念 文法产生的语言 e.g.3 G1的 描述 方式:从文法的开始符号E出发,反复用产生式的右部对其左部的非终结符进行替换和展开,直至i+i出现为止.所用产生式的顺序为: 1) E?E+E 2) E ?i 3) E ?i * 《编译原理与技术》讲义 * 若干基本概念 文法产生的语言 e.g.3 G2的 描述 方式:所用产生式的顺序为: 1) E?E+T5) T ?F 2) E ?T 6) F ?i 3) T ?F 4) F ?i * 《编译原理与技术》讲义 * 若干基本概念 文法产生的语言我们称上述 描述 为从开始符号E到i+i的 推导 过程. ? 表示一步 推导 .一般地, ?A?直接推导出???,即?A? ? ??? 仅当A?? ∈ P, ?,?,? ∈ (VT∪VN )*.推导序列- ? ?, ? ? * 《编译原理与技术》讲义 * 若干基本概念 文法产生的语言?是句型,如果S ? , ? ∈ (VT∪VN )*.?是句子,如果S ? ,且? ∈ VT*. 文法G产生的语言L(G),定义为,L(G)={文法G产生的所有句子} * 《编译原理与技术》讲义 * 若干基本概念 文法产生的语言e.g.4 文法G3产生的语言是什么?P:S? b A A? a A | aS?bA?baS?bA?baA?baaS?bA?baA?baaA?…?baa…aL(G3) = { 以b开头后跟一个或多个a的串} * 《编译原理与技术》讲义 * 若干基本概念 e.g.5 文法产生的语言 L(G4)={ambn|m,n?1} L(G5) = {anbn|n ?1} G4: S? A B A? a A | a B? b B | b G5: S? a S b | ab * 《编译原理与技术》讲义 * e.g.5 文法产生的语言 文法G4对句子aaabb的推导:S ? A B S? A B? a A B A? a A ? a a A B A? a A? a a a B A? a ? a a a b B B? b B ? a a a b b B? b * 《编译原理与技术》讲义 * e.g.5 文法产生的语言 文法G5对句子aaaabbbb的推导:S ? a S b S? a S b? a a S b b S? a S b? a a a S b b b S? a S b? a a a a b b b b S? a b * 《编译原理与技术》讲义 * 最左推导 最右推导 E?E + E E?E + E ?i + E ?E + i ?i + i ?i + i 句型推导时,总是选择最左出现的非终结符进行替换 总是选择最右出现的非终结符进行替换,也称为规范推导 * 《编译原理与技术》讲义 * 若干基本概念 规范推导(最右推导)和规范归约(最左归约)G1的句子i+i*i的规范推导过程: E 开始符号 ? E + E E? E + E ? E + E * E E? E * E ? E + E * i E? i ? E + i * i E? i ? i + i + i E? i 推导方向 * 《编译原理与技术》讲义 * 若干基本概念 规范推导(最右推导)和规范归约(最左归约)G1的句子i+i*i的规范归约过程:i + i + i E? iE + i * i E? iE + E * i E? iE + E * E E? E * E E + EE? E + EE (只有)开始符号 归约方向 * 《编译原理与技术》讲义 * 最右推导 最左归约 如果右句型 可以 归约 到右句型 ,仅当存在最右推导序列 从开始符号S出发,进行最右推导,用相应产生式右部文法符号串替换展开其左部非终结符号.目标为句子(右句型). 从句子(右句型)出发,用最左归约,用相应产生式的左部非终结符号替换产生式右部(句柄).目标为开始符号S. * 《编译原理与技术》讲义 * 最右推导 最左归约 推导中,关键是选择产生式 归约中,关键是确定句柄.而句柄与某产生式的右部相同且有某最右推导序列中的某一步对应;