2011~2012学年第一学期期末考试《编译原理》试卷工 商 一.(15)设有文法G[E],画出句型 P * F + ( E )↑i 对应的语法树,求出该句型的所有短语、直接短语、句柄。 E → E + T | T T→ T * F | F F → P ↑ F | P P →(E)| i 二.(5*3=15)给定文法 T → FS S → *FS|ε F → i|(T) 1. 写出该文法的终结符集合、非终结符集合以及产生式集合。 2.写出句型 (T)*i*FS 的最左推导和最右推导。 3.对下列符号串,指出哪些是句型,哪些是句子。 i, (i), ii, (T)S, ((T)) 三.(15)已知不确定的自动机 NFA=({A,B,C}, {0,1}, M, {A}, {D}), 其中 M(A,0)={B} M(A,1)={C} M(B,0)=ф M(B,1)={C,D} M(C,0)={B} M(C,1)={D} M(D,0)={C} M(D,1)=ф 构造对应的确定的自动机,并画出状态图。 四.(10分) 消除下列文法的左递归。 S → AS | b A → SA | a 五.(15)求出下列文法非终结符的FIRST集合,FOLLOW集合,每条产生式的SELECT集合,判断是否是LL(1)文法?若是, 构造预测分析表。 F → PD D → *D|ε P → a | b |(F) 六.(15)已知文法: S → a | ∧ | ( T ) T → T , S | S 求出FIRSTVT和LASTVT集合,算符优先关系表。 七.(15分)构造下列文法的LR(0)项目集族(即识别活前缀的自动机),该文法是LR(0)文法,还是SLR(1)文法? 为什么? 构造其对应的分析表。 (0) S′→S (1) S →rD (2) D →D,i (3) D →i