复习—编译原理第2章

1、10/15/20211计算机学院计算机学院编 译 原 理 Compiler PrinciplesCompiler Principles 10/15/20212n 把用一组数学符号和规则来描述语言的方式称为形式描述，把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言。而把所用的数学符号和规则称为形式语言。语言的三种表示方法语言的三种表示方法n 枚举枚举（句子有限）（句子有限）n 数学表示数学表示（句子无限）（句子无限） 制定有限条规则，用来产生所需描述语言中的句子全部，制定有限条规则，用来产生所需描述语言中的句子全部，这些规则即这些规则即文法。文法。n 建立

2、一种算法能对于任给的符号串，判别是否为给定语言的建立一种算法能对于任给的符号串，判别是否为给定语言的合法句子合法句子。10/15/20213仅出现在产生式右部的符号仅出现在产生式右部的符号 至少在产生式左部出现过一次的至少在产生式左部出现过一次的符号符号特殊的非终结符，表示了定义语言特殊的非终结符，表示了定义语言中最感兴趣的语法范畴。中最感兴趣的语法范畴。 G=VT，VN，S，P 10/15/20214句子 主语谓语 代词谓语 我谓语 10/15/20215l 文法的作用就是用有限条规则产生无限多句子。文法的作用就是用有限条规则产生无限多句子。l 某一文法产生的全部句子所组成的集合某一文法产生

3、的全部句子所组成的集合 该该。10/15/20216一个一个上下文无关文法上下文无关文法G定义为四元组定义为四元组(VN，VT，P，S )其中：其中：非终结符号非终结符号(或语法实体，或变量或语法实体，或变量)集；集；终结符号集；终结符号集；产生式产生式(也称规则也称规则)的集合；的集合； A 其中，其中， (VN VT )* ， A VN VN，VT和和P是是 非空有穷集。非空有穷集。 称作识别符号或开始符号的一个非终结符，它至少要在一称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。条产生式中作为左部出现。S VN VN和和VT不含公共的元素，即不含公共的元素，即V

4、N VT = 用用V表示表示VN VT ，称为文法，称为文法G的字母表或字汇表的字母表或字汇表10/15/20217l 直接推导直接推导“” 是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w= , v=,w= , 其中其中VV* *,V,V* * 则称则称v v到到w,w,记作记作 v v w w； 也称也称w w到到v v例：例：G G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S110/15/20218例：例：G： S0S1， S01 S 0S1 00S11 000S111 00001111*

5、S S 00S11 00S11S 00001111 推导长度为推导长度为4 若存在若存在v =w0 w1 . wn=w (n 1) 则记为则记为v w，称作，称作v推导出推导出w，或，或w归约到归约到v 特别的，若有特别的，若有v=w， 则记为则记为v w (n0) *l 推导的长度（长度为推导的长度（长度为n的推导）的推导）10/15/20219例：例：G： S0S1， S01S 0S1 00S11 000S111 00001111G的句型的句型 S，0S1，00S11，000S111，00001111G的句子的句子 00001111，01*l 句句 型型 有文法有文法GS，若，若S x，

6、xV*，则称，则称x是文法是文法G的句型。的句型。l 有文法有文法GS，若，若S x，且，且xVT*，则称，则称x是文法是文法G的句子。的句子。*10/15/202110语言中的每个句子可以由上下文无关文法的语言中的每个句子可以由上下文无关文法的产生。产生。例：例：G=（0，1，S，S，P） P: S0S1， S01 L(G)=0n1n|n1*L(G)=x|S x，S为文法的开始符号，且为文法的开始符号，且x VT*10/15/202111q G生成的每个串都在生成的每个串都在L(G)中，中，L(G)中的中的每个串确实能被每个串确实能被G生成。生成。q 文法所产生的语言文法所产生的语言L(G)

7、是是无限无限语言，原语言，原因是所定义的文法中含有因是所定义的文法中含有递归递归。10/15/202112l 递归、直接递归：递归、直接递归：如果文法中有形如如果文法中有形如AA的产生式，其的产生式，其中中，不同时为不同时为，则称文法为直接递归文法，则称文法为直接递归文法。A 称为递归和直接递归的非终结符号称为递归和直接递归的非终结符号*若存在若存在 A A，则称是递归的。，则称是递归的。l 左递归、右递归左递归、右递归 =， 左递归左递归 ，= 右递归右递归10/15/202113 例：语言例：语言L=anbbn| n 1，写出产生，写出产生L的文法。的文法。 GS: S aAb A aAb

8、|b10/15/202114l 若若L（G1）=L（G2），则称文法），则称文法G1和和G2是等价的。是等价的。如文法如文法G G1 1AA：A0R A0R 与与G G2 2SS：S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA110/15/20211510/15/202116GE：EE+T|T TT*F|F F(E)|a 对句型对句型T*a+T的的推导：推导： E E+T T*F+T T*a+T 10/15/202117l 自底向上分析方法自底向上分析方法 从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开开始符号始符号。

9、10/15/20211810/15/202119q 若一个文法存在某个若一个文法存在某个句子句子对应两棵不同的语法树，则称对应两棵不同的语法树，则称这个文法是这个文法是二义二义的。的。q 若一个文法存在某个若一个文法存在某个句子句子有两个不同的最左（右）推导，有两个不同的最左（右）推导，则称这个文法是则称这个文法是二义二义的。的。语法树语法树-句型推导句型推导的的直观表示直观表示 给定上下文无关文法给定上下文无关文法G=(VN,VT,P,S)，对于，对于G的任何句型的任何句型都能构造与之相关的语法树都能构造与之相关的语法树(推导树推导树)10/15/202120*S A且且 A ，则称，则称是

10、是句型句型相对于非终结符相对于非终结符A的的对于文法对于文法GS：n n 若有若有A ，则称，则称是是句型句型相对于非终结符相对于非终结符A 的的n 一个句型的一个句型的称为称为该句型该句型的的10/15/202121通过对产生式施加不同限制通过对产生式施加不同限制，Chomsky将文法分为四类：将文法分为四类：n0型文法：型文法：对任一产生式对任一产生式，有，有V+，V*;n1型文法：型文法：对任一产生式对任一产生式，有，有| (, V+)， 仅仅 S除外。除外。 或者形如或者形如A 产生式产生式, AVN ,V+, ,V*n2型文法：型文法：对任一产生式对任一产生式A，都有，都有AVN V

11、*;n3型文法：型文法：任一产生式均为任一产生式均为AB或或A (右线性右线性)， AB或或A（左线性）其中（左线性）其中AVN ，BVN ，aV VT T+ +10/15/202122四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系0型文法型文法1型文法型文法2型文法型文法3型文法型文法10/15/202123n 0型文法产生的语言称为型文法产生的语言称为0型语言型语言(递归可枚举语言递归可枚举语言)；n 1型文法或上下文有关文法（型文法或上下文有关文法（ CSG ）产生的语言称为）产生的语言称为1型语言型语言(上下文有关语言（上下文有关语言（CSL）)n 2型文法或上下文无关文法（型文法或上下文无关文法（ CFG ）产生的语言称为）产生的语言称为2型语言型语言(上下文无关语言（上下文无关语言（ CF L ）) 上下文无关文法有足够的能力描述程序设计语言的语法结构。上下文无关文法有