发布时间 : 星期六 文章编译原理期末复习更新完毕开始阅读
注：至于怎么填这个表请参见上一页中的PPT,这里不再赘述,Action表中si代表跳转到第i个状态，ri代表选择文法中第i条规则进行归约,acc代表接受，即分析成功。Goto表中数字i代表跳转到第i个状态。 （3）对accd#进行分析 步骤 1 2 3 4 5 6 7 8 9 #0 #0a2 #0a2c5 #0a2c5c5 #0a2c5c5d6 #0a2c5c5A10 #0a2c5A10 #0a2A4 #0E1 分析栈 accd# ccd# cd# d# # # # # # 输入串 s2 s5 s5 s6 r4 r3 r3 r1 acc 操作 8、写出表达式或者程序的中间形式 逆波兰式和四元式是三地址代码的两种记录表现形式，当然表示形式还有三元式、间接三元式等等，根据老师的意思应该不考，四元式和逆波兰式必考。
（1）逆波兰表达式
逆波兰表达式即后缀表达式，就是中缀表达式（也就是我们一般看到的表达式形式）对应的后续遍历结果，这个方法有很多，个人认为搞清楚运算优先级，观察一下就可写出，先算谁就将其对应的操作数写出，运算符放在后面就行很简单： 例如：写出下列各式的逆波兰表示 （1） -a-(b*c/(c-d) + (-b)*a) (2) -A+B*C↑ (D/E)/F
解： （1） a@bc*cd-/b@a*+ - （2） A@BCDE/↑*F/+ 注：@代表负号“-”
（2）四元式
四元式形式如下（op,arg1,arg2,Result）从左至右分别代表运算符，第一操作数，第二操作数,运算结果。
如：A + B * ( C - D ) + E / ( C - D ) ^N 对应的四元式序列如下: 四元式 : (1) ( - ,C ,D,T1 ) (2) ( * ,B,T1,T2) (3) ( + ,A,T2,T3) (4) ( - ,C,D,T4)
(5) ( ^ ,T4,N,T5) (6)( / ,E ,T5,T6)
(7) ( + ,T3 ,T6 ,T7)
注：T1,T2等等位存放结果的临时变量。
条件语句等四元式的表示
（jnz , a ,-- , p ) 表示 if a goto p
(jrop, x , y, p ) 表示 if x rop y goto p（rop代表关系运算符，如<,>等等）
(j , --, --- , p ) 表示 goto p
例如：写出条件语句 IF a>0 THEN x:=x+1 ELSE x:=4*( x- 1) 四元式序列
17 / 21
解：
(1)( j > , a ,0 ,(3)) (2)( j , -, -,(6)) (3)(+,x , 1 , T1) (4)( := , T1,-, T2 ) (5)(j ,-, -,(9)) (6)( -, x,1, T3) (7) (*, 4 ,T3 ,T4 ) (8) ( := , T4 ,-,x) (9) 注意：（5）和（9）不能写丢，否则一分没有！上述四元式中第二第三个位置的“-”代表没有元素。
其实四元式就是对上述程序进行解释，如果满足则跳转到哪里执行，不满足则跳转到哪里执行，大家自己分析一下，应该能够看懂。 考题：根据要求写出下列表达式的中间形式。
（1）5+6*（a+b）写出表达式的逆波兰式 逆波兰表达式为：56ab+*+ （2） if x > y then { y:=y-1; x：=y*z+10 } else x:= z + y 写出上述代码的四元式 或者三址码。 （有的试卷上问法是写出下列表达式三地址形式的中间表示，答案一样） 答案（1） (0)(j>,x,y,(2)) (1)(j,-,-,(8)) (2)(-,y,1,T1) (3)(:=,T1,-,y) (4)(*,y,z,T2) (5)(+,T2,10,T3) (6)( :=,T3,-,x) (7)(j,-,-,(10)) (8)(+,z,y,T4) (9)( :=,T4,-,x) (10) 答案（2） 100: if x>y goto 102 101: goto 108 102: T1:=y-1 103: y:=T1 104: T2:=y*z 105: T3:=T2+10 106: x:=T3 107: goto 110 108: T4:=z+y 109: x:=T4 110: 注意：同上题，本题答案加红色的部分此外上述编号随意，从0开始也行从100开始也行。不能丢，否则一分没有！
9、参数传递
这种题目很简单，是送分题，一定要做对！
参数传递方式分为三种，值传递，地址传递和传名。
值传递过程中形参值的改变不会影响实参值的改变，地址传递形参值的改变导致对应是实参值的改变，传名传递类似于C语言中的宏展开，将实参原封不动的替换相应的形参（文字替换）。 请看下题：
(1) 高级语言程序中常用的参数传递方式有哪些？请根据这些传递方式写出程序的运
行结果。
18 / 21
int main() {
int a=2; int b=3; p(a,a,a);
cout<<\< 分析：函数p中输出地a的值是全局变量a的值,与主函数中的局部变量a无关，不要被迷惑住，所以p中输出的a就是1.传值时，由于实参值不受影响，所以a仍为2； 传地址时，在函数P中，将实参代入后a=a+1得a=3;再由a=a+a得到a=6;传名时，直接将 实参带入形参，原来程序被替换为:a=a+1;a=a+a；将a=2代入得到结果为6. 答：①C语言中函数传递的方式有1)传值 2）传地址 3）传名 ②运行结果： 1)传值方式：In P 1 2)传地址：In P 1 3）传名: In P 1 In main 2 In main 6 In main 6 （2） Procedure p (x,y,z) ; begin begin a:=2; y:=y+1; b:=3; z:=z+x; p(a+b , a , a) end; {p} print a end. 传值传递时输出结果为： 2 (实参值不受影响,a=2) 传地址传递时输出结果为：8 （a=2+1=3;a=3+5=8） 传名传递时输出结果为：9 (a=a+1；a=a+a+b;得到a=2+1=3;a=3+3+3=9) static int a=1; int p(int x,int y,int z) { y=y+1; z=z+x; cout<<\< 10、程序分块、画DAG图 这个也比较简单，具体方法如下： （1） 分块就是将程序分成一块块的，主要就是确定每一块的入口语句： 1）寻找入口语句的方法：满足以下条件之一的都是入口语句 a）程序的第一条语句；b）条件转移语句或无条件转移语句可以转移到的语句 c)紧跟在条件转移语句后面的语句 2）对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。 3）凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。 19 / 21 例如划分基本块: (1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt 根据基本块画DAG图 (1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r?优化后的四元式划分结果 (1) (2) (3) (4) (5) (6) (7) (8) (9) read X （入口语句） read Y R:=X mod Y （入口语句） if R=0 goto (8) X:=Y （入口语句） Y:=R goto (3) write Y （入口语句） halt n8B*n6A, B, T5*n5T2, T4n7T6+-(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10)B:=T5*T6n1T0n2T1, T3n33.146.28R江西财经大学信息管理学院n4r(1) T0:=3.14(2) T1:=6.28(3) T3:=6.28n6A, B, T5(4) T2:=R+r*(5) T4:=T2n5T2, T4n7T6(6) A:=6.28*T2+-(7) T5:=A(8) T6:=R-rn1T0n2T1, T3n3n4(9)B:=A*T63.146.28Rr江西财经大学信息管理学院n8B* 上述图中的DAG只给出了最后完整的结果，老师要求在考试中需要把每一步都体现出来，具体请参见书上284页，因为篇幅限制所以不再赘述。另外，根据老师的意思可能会将DAG和四元式结合在一起考，给一段程序，先写出其四元式然后在画出其DAG图，四元式与DAG对应关系如下：根据下面的对应关系，DAG图很容易画出来。 20 / 21