昆明理工大学编译原理课后习题[部分重点].ppt

第2章2-2试分别构造产生下列语言的文法;2-3试描述由下列文法所产生的语言的特点;2-6句子L: L: begin d; d; s; s; end的语法树;2-11;2-11;2-13化简文法;2-13化简文法;2-14消去ε-产生式;2-15消去无用产生式和单产生式;第3章3-9对应状态矩阵画出状态图,写出相应3型文法,描述输入串特征;3-12将图示NFA确定化和最小化;3-12将图示NFA确定化和最小化;3-13具有ε动作的NFA确定化;3-14最小化FA;3-22构造识别正规语言的DFA;%{ #include stdio.h #include string.h char buf[100]; char *p,*q; %} %% [a-zA-Z]+ {p=yytext; q=buf; while (*p) {*q=toupper(*p); p++; q++;} *q=‘\0’; strcpy(yytext, buf); ECHO; } [\040\t\n]+ {fprintf(yyout, );} . ECHO; ;%% main( int argc, char** argv ) { if ( argc 1 ) yyin = fopen( argv[1], r );//yyin存放LEXYY的输入源程序 else yyin = stdin; if ( argc 2 ) yyout = fopen( argv[2], w );//yyout存放LEXYY的输出程序 else yyout = stdout; yylex(); } int yywrap() { return 1; };4-1消除文法的左递归;4-4求出文法的FIRST集和FOLLOW集 解:FIRST(S) = {a, b, ε} FOLLOW(S) = {#} FIRST(A) = {a, ε} FOLLOW(A) = FIRST(B)/ε∪ FOLLOW(S) ∪{b} = {b, #} FIRST(B) = {b, ε} FOLLOW(B) = FOLLOW(S) = {#} 4-7验证文法是否为LL(1)文法 (1)解:∵FIRST(D →f D) ∩ FIRST(D →f) = {f} ≠Φ ∴不是LL(1)文法;4-8构造与G等价的LL(1)文法G’,并构造相应的LL(1)分析表;解二:消除左递归得G’ (S A) = (S A) b Φ + (b a) b a 设 b Φ * = Z = z11 z12 b a z21 z22 则有 (S A) = (b a) z11 z12 z21 z22 z11 z12 = ε Φ + b Φ z11 z12 z21 z22 Φ ε b a z21 z22 于是得到新的等价文法 S→bz11|az21 A→bz12|az22 z11→bz11|ε z12→bz12 z21→bz11|az21 z22→bz12|az22|ε 删除无用产生式得G’ S→ bz11|az21 z11→bz11|ε z21→bz11|az21 LL(1)分析表:;4-16改造G为简单优先文法G’,并求出全部简单优先关系;4-31构造算符优先矩阵,并用Floyd方式线性化;4-35构造识别活前缀的