编译原理课程总复习.ppt

1、编译原理课程总复习,贾棋 ,前端：依赖于源语言，独立于目标机器。,前端 后端,后端：依赖于目标机器，独立于源语言。,第二章 词法分析器,词法分析器工作原理：,词法记号的描述与识别,正规式的例子 = a, b a | ba, b (a | b) (a | b ) aa, ab, ba, bb aa | ab | ba | bbaa, ab, ba, bb a*由字母a构成的所有串集 (a | b)*由a和b构成的所有串集 复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：01001101000010000010111001,正规定义

2、的例子 Pascal语言的标识符集合 letter A | B | | Z | a | b | | z digit 0 | 1 | | 9 id letter(letter|digit)*,正规定义的例子 Pascal无符号数集合，例1946,11.28,63.6E8,1.99E6 digit 0 | 1 | | 9 digits digit digit* optional_fraction .digits| optional_exponent (E ( + | | ) digits ) | numdigits optional_fraction optional_exponent 简化表示

3、num digit+ (.digit+)? (E(+|)? digit+)?,简化规则： r+=rr* r?=r| a-z=a|b|c|z abc=a|b|c,状态转换图,转换图 关系算符的转换图,relop | | =,有 限 自 动 机,有 限 自 动 机,不确定的有限自动机（简称NFA） 一个数学模型，它包括: 状态集合S； 输入符号集合； 转换函数move : S () P(S)； 状态s0是开始状态； F S是接受状态集合。,识别语言 (a|b)*ab 的NFA,缺点：1、输入字符包括 2、一个状态对于某个字符，可能有多条输出边,有 限 自 动 机,确定的有限自动机（简称DFA) 一

4、个数学模型，包括：,状态集合S； 输入字母表； 转换函数move : S S； 唯一的初态 s S； 终态集合F S；,识别语言 (a|b)*ab 的DFA,优点：1、输入字符不包括 2、一个状态对于某个字符，只可能存在唯一条输出边,NFA到DFA的转换子集构造法,状态,NFA到DFA的转换子集构造法,状态,A = 0, 1, 2, 4, 7 DFA中第一个状态由NFA 中的开始状态求闭包得到,NFA到DFA的转换子集构造法,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8,NFA到DFA的转换子集构造法,状态,A = 0, 1, 2, 4, 7 B =

5、 1, 2, 3, 4, 6, 7, 8,NFA到DFA的转换子集构造法,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,NFA到DFA的转换子集构造法,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,NFA到DFA的转换子集构造法,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7,NFA到DFA的转换子集构造法,状态,A = 0, 1, 2, 4

6、, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,NFA到DFA的转换子集构造法,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,NFA到DFA的转换子集构造法,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,NFA到DFA的转换子集构造法

7、,状态,A = 0, 1, 2, 4, 7 B = 1, 2, 3, 4, 6, 7, 8 C = 1, 2, 4, 5, 6, 7 D = 1, 2, 4, 5, 6, 7, 9,只要含有NFA中终结状态就标志为DFA的终结状态,NFA到DFA的转换,状态,DFA的化简,死状态 左图无须加死状态，右图加入死状态E。,DFA的化简,可区别的状态 A和B是可区别的状态 A和C是不可区别的状态,DFA的化简,方法 1. A, B, C, D move(A, B, C, a = B move(A, B, C, b = C, D 2. A, C, B, D move(A, C, a = B move(

8、A, C, b = C,初始划分为接受状态子集和非接收状态子集,划分完毕之后如果有死状态，将其删掉，从开始状态不可及的状态也删除,DFA的化简,方法 1. A, B, C, D move(A, B, C, a = B move(A, B, C, b = C, D 2. A, C, B, D move(A, C, a = B move(A, C, b = C,将下图的DFA极小化。,1、加入死状态 2、合并不可区分状态,先把状态集分成非接受状态集0, 1, 2, 3, 5和接受状态集4这两个子集。 1集合4不能再分解，我们看集合0, 1, 2, 3, 5。 move (0, 1, 2, 3, 5

9、, a) = 1, 2, 5 move (0, 1, 2, 3, 5, b) = 3, 4, 5 由于b 转换的结果3, 4, 5不是最初划分的某个集合的子集，因此0, 1, 2, 3, 5需要再分，由于状态1和状态2的b转换都到状态4。因此状态集合的进一步划分是： 1, 2，0, 3, 5和4 2由于move (1, 2, a) = 2, 5 move (1, 2, b) = 4 move (0, 3, 5, a) = 1, 5 move (0, 3, 5, b) = 3, 5 显然1, 2和0, 3, 5需要再分，分别分成：1和2以及0, 3和5 3由于move (0, 3, a) = 1

10、 move (0, 3, b) = 3 因此不需要再分。这样状态0和状态3合并成一个状态，我们取0为代表，再删去死状态5，就得到该题的结果。,正确做法！,最初的划分是0, 1, 2, 3和4。 1状态集合的进一步划分是： 1, 2，0, 3和4 2忽略了死状态的影响，会认为它们都不需要再分,错误做法！,1、直接合并不可区分状态,从正规式到有限自动机,正规式,计算机实现,状态转换图,有限自动机,不确定有限自动机,确定有限自动机,等价,？,从正规式到有限自动机,从正规式到有限自动机,从正规式到有限自动机,从正规式到有限自动机,从正规式到有限自动机,从正规式到有限自动机,从正规式到有限自动机,从正规

11、式到有限自动机,(a|b)*ab的两个NFA的比较,从语言到确定的有限自动机,例：识别 =0,1上能被5整除的二进制数,方法： 1、列出全部可能的状态 2、从各个状态出发，构造边及输入字符记号,例：识别 =0,1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,例：识别 =0,

12、1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,例：识别 =0,1上能被能5整除的二进制数,从语言到确定的有 限 自 动 机,构造DFA,接受 0和1的个数都是偶数的字符串,从语言到确定的有 限 自 动 机,小结,正规式,计算机实现,状态转换图,不确定有限自动机,确定有限自

13、动机,等价,用正规式语法结构来指导构造过程,子集构造法,合并不可区别状态,最简确定有限自动机,等价,语言,确定有限自动机,状态列举法,第三章 语法分析器,主要内容 上下文无关文法 自上而下分析和自下而上分析,上下文无关文法与正规式比较,上下文无关文法 E E A E | (E ) | E | id A + | *,正规式定义 letter A-Za-z digit 0-9 id letter(letter|digit)*,上下文无关文法是一个四元组 最左推到、最右推导 二义性,语言和文法,消除左递归 文法左递归A+Aa 直接左递归AAa |b 串的特点 ba . . . a 消除直接左递归 A

14、 b A A a A | ,语言和文法,非直接左递归 S Aa | b A Sd | 先变换成直接左递归 S Aa | b A Aad | bd | 再消除左递归 S Aa | b A bd A | A A adA | ,语言和文法,提左因子 有左因子的文法 A 1 | 2 提左因子 A A A 1 | 2,正规式,上下文无关文法,功能有限,四元组定义,推导,分析树,图形化表示,最左推导,最右推导,二义性,消除二义性,左递归,消除左递归,左因子,消除左因子,A 1 | 2,A+Aa,FIRST集、FOLLOW集,FIRST ( )=a | * a, a VT 特别是， * 时，规定 FIRST

15、 ( ) FOLLOW (A) = a | S * Aa，aVT 如果A是某个句型的最右符号，那么$属于FOLLOW(A),FIRST集合计算方法 若Xa.， 则将终结符加入FIRST(X)中 若X，则将加入FIRST(X)中 若XY，且Y属于非终结符，则将FIRST(Y)加入到FIRST(X)中 若XY1Y2.YK,且Y1,Y2,.Yi-1都是非终结符，且Y1,Y2,.Yi-1的FIRST集合中均包含，则将FIRST(Yj)的所有非元素加入到FIRST(X)中，（j=1,2,.i）.特别地，若Y1YK均有产生式，则将加到FIRST(X)中。,FIRST集合及FOLLOW集合的计算方法,FOL

16、LOW集合计算方法 对文法开始符号S,置$于FOLLOW(S)中。 若有AB，则将FIRST() 加入FOLLOW(B)中。 （此处 可以为空） 若A B 或A B ,且 * （即 属于FIRST()）,则将 FOLLOW(A)加入FOLLOW(B)中（此处 可以为空）。,FIRST集合及FOLLOW集合的计算方法,FIRST集合及FOLLOW集合的计算方法,例 E TE E + TE | T FT T * FT | F (E) | id,FIRST集合及FOLLOW集合的计算方法,例 E TE E + TE | T FT T * FT | F (E) | id FIRST(E) = FIRS

17、T(T) = FIRST(F) = ( , id ,FIRST集合及FOLLOW集合的计算方法,例 E TE E + TE | T FT T * FT | F (E) | id FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, ,FIRST集合及FOLLOW集合的计算方法,例 E TE E + TE | T FT T * FT | F (E) | id FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, FRIST(T ) = *, ,FIRST集合及FOLLOW集合的计算方法

18、,例 E TE E + TE | T FT T * FT | F (E) | id FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, FRIST(T ) = *, FOLLOW(E) = FOLLOW(E ) = ), $,FIRST集合及FOLLOW集合的计算方法,例 E TE E + TE | T FT T * FT | F (E) | id FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, FRIST(T ) = *, FOLLOW(E) = FOLLOW(E ) =

19、), $ FOLLOW(T) = FOLLOW (T ) = +, ), $,FIRST集合及FOLLOW集合的计算方法,例 E TE E + TE | T FT T * FT | F (E) | id FIRST(E) = FIRST(T) = FIRST(F) = ( , id FIRST(E ) = +, FRIST(T ) = *, FOLLOW(E) = FOLLOW(E ) = ), $ FOLLOW(T) = FOLLOW (T ) = +, ), $ FOLLOW(F) = +, *, ), $,自上而下分析,LL(1)文法 任何两个产生式A | 都满足下列条件： FIRST(

20、 ) FIRST( ) = 若 * ，那么FIRST() FOLLOW(A) = ,LL(1)文法有一些明显的性质 没有公共左因子 不是二义的 不含左递归,自上而下分析,非递归的预测分析,自上而下分析,自上而下分析,预测分析器接受输入id * id + id的动作,自上而下分析,预测分析器接受输入id * id + id的动作,自上而下分析,预测分析器接受输入id * id + id的动作,自上而下分析,预测分析器接受输入id * id + id的动作,自上而下分析,构造预测分析表 （1）对文法的每个产生式A ，执行(2)和(3)。 （2）对FIRST()的每个终结符a，把A 加入MA, a。

21、 （3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$）, 把A 加入MA, b。 （4）M的其它没有定义的条目都是error。,自上而下分析,自下而上,上下文无关文法,自上而下,自下而上,LL(1)文法,2个函数,递归下降预测分析,非递归的预测分析,最左推导,最右推导,！,自下而上分析,句柄 句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步。 S aABe A Abc | b B d S rm aABe rm aAde rm aAbcde rm abbcde 活前缀不会超过句柄的最右端。,句柄与某个产生式的右部符

22、号串相同 句柄是句型的一个子串 把句柄归约成非终结符代表了最右推导逆过程的一步,从文法构造的识别活前缀的DFA的一些特点 概念：有效项目 如果S*rm Aw rm 12w，那么我们说项目A12对活前缀1是有效的。 一个项目可能对好几个活前缀都是有效的。 S*rm AAw rm A12w rm 1212w 对任何活前缀1，从项目A12有效这个事实可以知道 如果2 ，应该移进 如果2 = ，应该用产生式A1归约,LR分析器,LR分析算法,LR分析器,例 E E + T | T T T * F | F F (E ) | id,LR分析器,LR分析器,LR分析器,40/75,LR分析器,LR分析器,L

23、R分析器,LR分析器,构造SLR分析表,LR(0)项目（简称项目） 在右部的某个地方加点的产生式 例：AXYZ对应有四个项目 A XYZ A XYZ A XYZ A XYZ 例：A只有一个项目和它对应 A ,点的左边代表历史信息，右边代表展望信息。直观地讲，项目表示在分析过程的某一阶段，已经看到了产生式的多大部分，以及希望看到的部分。,从DFA构造SLR分析表,状态i从Ii构造，它的action函数如下确定： 如果Aa在Ii中，并且goto(Ii, a ) = Ij，那么置actioni, a为sj。 如果A在Ii中，那么对FOLLOW(A)中的所有a，置actioni, a为rj,j是产生式

24、 A的编号。 如果SS在Ii中，那么置action i, $ 为接受acc。 如果出现动作冲突，那么该文法就不是SLR(1)的。 使用下面规则构造状态i的goto函数： 对所有的非终结符A，如果goto(Ii, A) = Ij, 那么gotoi, A = j。,构造规范的LR分析表,基于LR(1)项目来构造识别G活前缀的DFA。 2、构造LR(1)项目集规范族 I0: S .S, $ S .BB, $ B .bB, b/a B .a, b/a,闭包函数closure(I) 1、I的每个项目均加入closure(I) 2、如果AB, a在 closure(I)中，且B是产生式，那么如果项目B,b

25、 还不在closure(I)中的话，那么把它加入(其中b属于FIRST(a)。,S S S BB B bB B a,构造规范的LR分析表,S V = E S E V * E V id E V,构造LR分析表的一般流程,构造拓广文法 构造DFA 若是SLR直接构造即可 若是LR需要求取搜索符 若是LALR需要在LR的基础上进行合并 根据DFA构造分析表,判断文法属于哪类文法,证明文法 SA a | bAc | dc | bda A d 是LALR(1)文法，但不是SLR(1)文法。 方法一：通过构造分析表来回答，如果表中不存在冲突则说明属于某文法，否则不属于该文法。 方法二：当文法很简单时，可通

26、过直观分析。先说明该文法不是SLR(1)文法。从产生式很容易看出FoLLow(A) a，c。若输入句子是dc，在d进栈后，面临的是c，这时出现移进一归约冲突。因为项目Sd.c要求移进，而项目A d.要求归约(这两个项目出现在同一项目集中)，因为c在FOLLOW(A)中。 而上面的移进一归约冲突在规范LR(1)情况下不存在，因为只有在面临a时才进行d到A的归约。该文法还有另一个移进归约冲突，在bd进栈后，面临c的情况，其冲突的原因和上面的类似。该冲突在规范LR(1)情况下也不存在。这样，该文法是LR(1)文法。 显然该文法的规范LR(1)项目集的集合中没有同心项目集，因此该文法也是LALR(1)

27、文法。,第四章 语法制导的定义,简单台式计算器的语法制导定义,本章要点,语义规则的两种描述方法：语法制导的定义和翻译方案。 设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点。 S属性的自下而上计算（边分析边计算）。 L属性的自上而下计算（边分析边计算）。 L属性的自下而上计算（边分析边计算）。,语法制导的定义,语法制导定义的形式 每个文法符号有一组属性 每个文法产生式A 有一组形式为b := f(c1, c2, , ck )的语义规则，其中f 是函数，b和c1, c2, , ck 是该产生式文法符号的属性 综合属性：如果b是A的属性，c1 , c2 , , ck 是产生式右部文法符号

28、的属性或A的其它属性。 继承属性：如果b是产生式右部某个文法符号X的属性。 以上两种情况下，都说b依赖于属性c1 , c2 , , ck 。,属性值由分析树中它的子结点属性值来计算,属性值由结点的兄弟结点及父结点的属性值来计算。,句子real id1，id2，id3的带注释的分析树的依赖图,id1,L,id2,L,id3,L,real,T,D,4 type,5 in,6 - addtype(id.entry, L.in),7 in,8 addtype,9 in,10 addtype,1 entry,2 entry,3 entry,产 生 式 语 义 规 则 DTL L.in := T.type

29、 Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),S属性定义的自下而上计算,将LR分析器增加一个域来保存综合属性值。,若产生式A XYZ的语义规则是 A.a := f (X.x, Y.y, Z.z)， 那么归约后：,top,S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操

30、作代码,S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,L属性定义的自上而下计算,L属性定义 如果每个产生式A X1 X2 Xn 的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性，1 j n, 但它仅依赖： 该产生式中Xj左边符号X1, X2, , Xj-1的属性； A的继承属性。 S属性定义属于L属性定义。,L属性定义的自上而下计算,L属性定义的例子：变量类型声明的语法制导定义,语义规则的执行时刻很重要,翻译方案,语义动作（语义规则）插入到产生式右部的任何 地方，以表达动作的执行时刻。 AB.C L属性定义的翻译方案的三条限制： 产生式右部符号的继承属性必须在

31、先于这个符号的 动作中计算 一个动作不能引用该动作右边符号的综合属性 左部非终结符的综合属性只能在它所引用的所有属 性都计算完后才能计算,建立翻译模式,如果既有综合属性又有继承属性，在建立翻译模式时就必须保证： 1. 产生式右边的符号的继承属性必须在先于这个符号的动作中计算出来。 2. 一个动作不能引用这个动作右边的符号的综合属性。 3. 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。 SA1A2A1.in:=1; A2.in:=2 Aaprint(A.in),L属性的自下而上计算,L属性自下而上计算需要解决的问题：,

32、AX Y Z.i = X.x Z,一个状态（文法符号）对应一个综合属性，该属性的值一般在处理完该文法符号之后得到。那么在Z还没有开始处理前，继承属性Z.i 就没有对应的val条目供其使用！,在栈上消除继承属性,L属性的自下而上计算,特殊情况一：删除翻译方案中嵌入的动作 E T R R + T print (+)R1 | T print ()R1 | T num print (num.val) 在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M 的右端。 E T R R + T M R1 | T N R1 | T num print (num.val)

33、 M print (+) N print (),L属性的自下而上计算,特殊情况二：分析栈上的继承属性 属性位置能预测 例 int p, q, r D T L.in := T.type L T int T. type := integer T real T. type := real L L1.in := L.in L1, id addtype (id.entry, L.in ) L id addtype (id.entry, L.in ),L属性的自下而上计算,属性的位置不能预测 S aACC.i := A.s S bABCC.i := A.s C cC.s := g(C.i) 增加标记非终结

34、符 S aACC.i := A.s S bABMCM.i := A.s; C.i := M.s C cC.s := g(C.i) M M.s := M.i,L属性的自下而上计算,一般情况：模拟继承属性的计算 继承属性是某个综合属性的一个函数 S aACC.i := f (A.s) C cC.s := g(C.i),L属性的自下而上计算,模拟继承属性的计算 继承属性是某个综合属性的一个函数 S aACC.i := f (A.s) C cC.s := g(C.i) 增加标记非终结符，把f(A.s)的计算移到对标记 非终结符归约时进行。 S aANCN.i := A.s; C.i := N.s N

35、N.s := f (N.i) C cC.s := g(C.i),这样，每次需要使用继承属性的时候，刚好都在本文法符号的正下方,例 题 1,为文法 S ( L ) | a L L , S | S 写一个语法制导定义，它输出括号的对数。 S Sprint (S. num) S ( L )S. num := L.num + 1 S aS. num := 0 L L1 , SL. num := L1. num + S. num L SL. num := S.num,在写语法制导定义之前，首先分析清楚需要为文法符号定义一些什么属性，然后看这些属性的值是否可以由文法符号本身所推出的串决定。若是，则应该只用

36、综合属性就能解决。,例 题 2,为文法 S ( L ) | a L L , S | S 写一个翻译方案，它输出每个a的嵌套深度。例如，对于( a , ( a , a) )，输出的结果是1 2 2。 S S. depth := 0 S S L. depth := S. depth + 1 ( L ) S a print (S. depth) L L1. depth := L. depth L1 , S. depth := L. depth S L S. depth := L. depth S,外层括号数目,例 题 3,为文法 S ( L ) | a L L , S | S 写一个翻译方案，它输出

37、括号嵌套的最大深度。例如，对于( a , ( a , a) )，输出的结果是2。 S S print(S.max) S ( L ) S.max:=L.max+1 S a S.max=0 L L1 , S L.max:=max(L1.max, S.max) L S L.max:=S.max,例 题 4,为文法 S ( L ) | a L L , S | S 写一个翻译方案，它打印出每个a在句子中是第几个字符。例如，当句子是( a , ( a , ( a , a ) , (a) ) )时，打印的结果是2 5 8 10 14。 S S. in := 0 S S (L. in := S. in + 1

38、 L ) S. num:= L.num+ 2 S a S. num := 1; print (S. in+1) L L1. in := L. in L1 , S. in := L1. in + L1.num+1 S L.num := L1.num + S.num +1 L S. in := L. in S L. num := S.num ,例 题 5,给出对表达式求导数的语法制导定义(习题4.5),例 题 6(4.12),P D D D;D | id:T | proc id; D; S (1)一共声明多少个id P D print(D.sum) D D1;D2 D.sum= D1.sum+D2

39、.sum D id:TD.sum= 1 D proc id; D1; SD.sum=D1.sum+1,例 题 6(4.12),P D D D;D | id:T | proc id; D; S (2)变量id的嵌套深度 P D.depth= 1D D D1.depth= D.depthD1; D2.depth= D.depthD2 D id:T print(, D.depth) D proc id; D1.depth= D.depth+1D1; S,例 题 6(4.7),用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S.val5.625。 S

40、L.L | L L L B | B B 0 | 1,例 题 6(4.7),S L.L | L L L B | B B 0 | 1 (1)仅使用综合属性 S L1.L2 S.valL1.val+L2.val /2L2.length S L S.valL.val L L B L.val=L1.val * 2+B.val; L.length=L1.length+1 L B L.val=B.val; L.length=1 B 0 B.val=0 B 1 B.val=1,例 数学排版语言EQN E sub 1 .val S B B B1 B2 B B1 sub B2 B text,例 数学排版语言EQN

41、 E sub 1 .val,1. 产生式右边的符号的继承属性必须在先于这个符号的动作中计算出来。 2. 一个动作不能引用这个动作右边的符号的综合属性。 3. 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生式右端的末尾。,例 数学排版语言EQN S B.ps := 10 BS.ht := B.ht B B1.ps := B.ps B1B2.ps := B.ps B2B.ht := max(B1.ht, B2.ht ) B B1.ps :=B.ps B1 sub B2.ps := shrink(B.ps) B2B.ht := disp (

42、B1.ht, B2.ht ) B textB.ht := text.h B.ps ,例 左递归的消除引起继承属性,E T R.i := T.nptr T + T + T + RE.nptr := R.s R + TR1.i := mknode ( +, R.i, T.nptr) R1R.s := R1.s R R.s := R.i T F W.i := F.nptr WT.nptr := W.s W * FW1.i := mknode ( *, W.i, F.nptr) W1W.s := W1.s W W.s := W.i ,消除左递归后文法,R,R,R,T.nptr,？,使用继承属性构造a4

43、c的抽象语法树,E,T,R,id,T.nptr,-,T,num,T.nptr,R. i,R,+,T,R,id,T.nptr,R. i,R. i,R. s,R. s,R. s,E.nptr,E T R.i:=T.nptr R E.nptr:=R.s R + T R1.i:=mknode(+,R.i,T.nptr) R1 R.s:=R1.s R - T R1.i:=mknode(,R.i,T.nptr) R1 R.s:=R.s R R.s:=R.i T ( E ) T.nptr:=E.nptr T id T.nptr:=mkleaf(id,id.entry) T num T.nptr:=mklea

44、f(num,num.val),4.7 令综合属性val表示S产生的二进制数的值。 S L.L | L L L B | B B 0 | 1 (a) 试用各有关综合属性决定S.val.,如果只有整数部分，很显然，可以定义如下： S L S.val = L.val; L L1 B L.val = L1.val *2 + B.val; L B L.val = B.val; L.b = 2; B 0 B.val = 0; B 1 B.val = 1;,为了求小数部分的值， 引入L的综合属性b记录2的L的位数次幂值(2 length of L) S L1.L2 S.val = L1.val + L2.va

45、l / L2.b; S L S.val = L.val; L L1 B L.val = L1.val *2 + B.val; L.b = L.b*2; L B L.val = B.val; L.b = 2; B 0 B.val = 0; B 1 B.val = 1;,第六部分 局部存储分配策略,活动记录 一般的活动记录的布局,例题,在X86/Linux工作站上，以下两个结构的size分别是20和16，为什么不一样？ typedef struct _atypedef struct _b char c1; char c1; long i; char c2; charc2; long i; doub

46、le f; double f; a; b;,三种存储分配策略的比较,访问链,访问链的使用及建立 动态作用域和静态作用域产生的不同输出 值调用、引用调用、复写恢复调用、换名调用,6.3 非局部名字的访问,2、建立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的过程x np nx的情况 x肯定就声明在p中 被调用过程的访问链必须指向调用过程的活动记录的访问链,sort 1 readarray2 exchange2 quicksort2 partition 3,6.3 非局部名字的访问,2、建立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的过程x np nx的情况 p和x的嵌套深度分别

47、为1，2，nx 1的外围过程肯定相同 追踪访问链np （nx 1）次，到达了静态包围x和p的且离它们最近的那个过程的最新活动记录 所到达的访问链就是x的活动记录中的访问链应该指向的那个访问链,例 题,假定使用(a)值调用；(b)引用调用；(c)复写恢复调用；(d)换名调用。下面程序打印的结果是什么。 program main(input,output)； var a,b：integer； procedure p(x,y,z：integer)； begin y:y+1 ； z:z+x； end； begin a:2； b:3； p(a+b,a, a) ； print a； end,例 题,(a)

48、对值调用而言，由于被调用过程中对形式参数的赋值不会改变实在参数的值，因此对过程p的调用不改变a的值，因此a仍然是2。 (b)在引用调用的时候，p(a+b，a，a)相当于p(5，a，a)(注意，5的值存放在临时单元，传送的是临时单元的地址)。在被调用过程中任何对形式参数的引用和赋值，也就是对相应实在参数的引用和赋值。因此y:=y+1的执行结果使得a等于3，进一步执行z:z+x使得a=8。 (c)复写恢复调用等价于下面的执行序列： t:a+b；x:t；y:=a； z:a；实参的值传给形参 y:y+1； z:z+x； t:x； a:y；a:z； 形参的结果传给实参 如果回送形式参数值的次序反过来的话

49、，则调用后a的结果是3。,例 题,(d)换名调用等价于下面的执行序列 a:a+1； a:=a+(a+b)； 所以a的最后结果是9。,第七部分,把算术表达式-(a+b)*(b+c)翻译成(a)语法树(b)无环行向图dag(c)后缀表示(d)三地址代码。 后缀表达式：ab+-bc+*,三地址代码： t1=a+b; t2=-t1; t3=b+c; t4= t2 *t3;,7.2 声 明 语 句,7.2.1 过程中的声明,计算被声明名字的类型和相对地址 P offset := 0D S D D ; D D id : Tenter ( , T.type, offset); offset :

50、= offset + T.width T integer T.type := integer; T.width := 4 T real T.type := real; T.width := 8 T array num of T1 T.type := array (num.val, T1.type); T.width := num.val T1.width T T1 T.type := pointer (T1.type); T.width := 4 ,7.2 声 明 语 句,exchange,readarray,x,a,表 头,空,sort,quicksort,指向readarray,partition,v,k,表 头,quicksort,readarrary,i,表 头,exchange,表 头,指向exchange,partition,program sort(input,output) var a:array0.10 of integer; x:integer; prcedure readarray; procedure exchange(i,