12 13 S→bBd· ，# S→bAe· ，# R2 R4
构造LR(1)分析表： 状态 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ACTION a S2 b S3 c S6 S9 d S10 R5 S12 R6 e S11 R6 S13 R5 # ACCEPT R1 R3 R2 R4 S 1 GOTO A 4 8 B 5 7
同核项目集合并，构造LALR(1)项目集规范族： 状态 0 项目集 S’→·S，# S→·aAd，# S→·bBd，# S→·aBe，# S→·bAe，# S’→S· ，# S→a·Ad，# S→a·Be，# A→·c，d B→·c，e S→b·Bd，# S→b·Ae，# A→·c，e B→·c，d S→aA·d，# S→aB·e，# A→c· ，d:e B→c· ，d:e S→bB·d，# S→bA·e，# 转换函数 GO[0，S]＝1 GO[0，a]＝2 GO[0，b]＝3 GO[0，a]＝2 GO[0，b]＝3 ACCEPT GO[2，A]＝4 GO[2，B]＝5 GO[2，c]＝6 GO[2，c]＝6 GO[3，B]＝7 GO[3，A]＝8 GO[3，c]＝6 GO[3，c]＝6 GO[4，d]＝9 GO[5，e]＝10 R5 R6 GO[7，d]＝11 GO[8，e]＝12 1 2 3 4 5 6 7 8
9 10 11 12 S→aAd· ，# S→aBe· ，# S→bBd· ，# S→bAe· ，# R1 R3 R2 R4
构造LALR(1)分析表： 状态 0 1 2 3 4 5 6 7 8 9 10 11 12 ACTION a S2 b S3 c S6 S9 d S10 S12 e S11 S13 # ACCEPT R1 R3 R2 R4 S 1 GOTO A 4 8 B 5 7 R5/R6 R5/R6 从LR(1)分析表可以看出，分析表无重定义，因此该文法是LR(1)文法。 从LALR(1)分析表可以看出，分析表ACTION[6,d]和ACTION[6,e]存在重定义，因此该文法不是LALR(1)文法。
7.1 给出编译下面程序的有序符号表。 main() {
int m,n[5]; real x;
char name; } 解： 名字 m n x 类型 int int real 维数 0 1 0 0 main keyword 0 name char 7.2 按“质数除余法”，给出编译上题程序的散列符号表。 解：正整数H＝ASC函数（字符串），质数＝5，散列符号表如下所示： 名字 m main n name x 正整数 109 421 110 417 120 H%5 4 1 0 2 0 位置 0 1 2 3 4 名字域 n main name m 属性域 x 7.3 给出编译到下面程序a、b、c处的栈式符号表。 real x,y;
char str;………………………………a int fun1(int ind) {
int x; ……………………………b x=m2(ind+1); }
main() {
char y; …………………………c
x=2;y=5; printf(\ } 解：
a： Top str y x 0
b：
Top x ind fun1 str y 4 x 0 c：
Top y main fun1 str y 5 x 0
10.1 对下列基本块应用DAG进行优化： (=，3， ，B) (+，A，C，D) (*，A，C，E) (+，D，E，F) (*，B，F，G) (+，A，C，H) (*，A，C，I) (+，H，I，J) (*，B，5，K) (+，K，J，L) (=，L， ，M)
解：构造DAG如下：
G n7 * B n1 3 n8 15 D,H n4 + n2 A K n6 + E,I n5 * n3 C L,M n9 + F,J
按照上图的DAG结点顺序，优化后生成的程序如下： (=，3， ，B) (+，A，C，D) (=，D， ，H) (*，A，C，E) (=，E， ，I)