编译原理期末试题（8套含答案+大题集）(11)

第49页共6页

（2）算符优先矩阵，如表A-5所示。

表A-5 优先矩阵 ( ) ; i # ( ) ; i # ?? B ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? B 5. 已知文法G(S)： S—>a|(T) T—>T,S|S

①给出句子((a,a),a)的最左推导并画出语法树；②给出句型(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。

解：（1）最左推导：S?(T)?(T,S)?(S,S) ?(a,S)?(a,(T))?(a,(T,S))?(a,(S,S))?(a,(a, S))?(a,(a,a))

语法树：如图A-16所示。

S( T )T , SSa( T )T , SSaa图A-16 (a,(a,a))的语法树

（2）句型(T, a, (T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。

短语：a || T,a || (T) || T , a , (T) || (T , a , (T)) 直接短语：a || (T) 素短语：a || (T) 最左素短语：a 句柄：a

活前缀：? || ( || (T || (T , || (T , a

S( T )T , ST , S( T )a 图A-17 (T,a,(T))的语法树

6. 设文法Ｇ（Ｓ）为：

Ｓ—＞ａ｜ａＡｂ Ｓ—＞ｂ｜ｂＢａ Ａ—＞１Ａ０｜ε Ｂ—＞１Ｂ０｜ε

第50页共6页