哈工大编译原理习题及答案

i+=200; else i+=2; break;

case TWENT: i+=20; break;

case TE:i+=10; break;

default:break; }

}/*while*/

label: printf(\return; }

24 （1）Dn表示的正规集是长度为2n任意a和b组成的字符串。

? ?

此正规式的长度是2n

用来识别Dn的DFA至多需要2n＋1个状态。

25 从略。

26（1）由{}括住的,中间由任意个非{组成的字符串, 如{},{}},{a},{defg}等等。 （2）匹配一行仅由一个大写字母和一个数字组成的串，如A1,F8,Z2等。 （3）识别\\r\\n和除数字字符外的任何字符。

?

由?和?括住的，中间由两个??或者非?和\\n组成的任意次的字符串。如????, ?a?,?bb?,?def?，??????等等

27O[Xx][0-9]*[a-fA-F]*|[0-9]+|(\\’([a-zA-Z]|\\\\[Xx][0-7][0-7a-fA-F]|\\\\0[01][0-7][0-7]|\\\\[a-z])\\’)

28^[a-zA-Z_]+[0-9]*[a-zA-Z_]*

29 参考程序如下： %{

#include #include #include #define UPPER2 #define WHITE3 %}

upper[A-Z] %%

{upper}+returnUPPER; \\t|\%%

main(int argc,char *argv[]) { int c,i; if (argc==2) {

if ((yyin=fopen(argv[1],\{

printf(\} }

while ((c=yylex())!=EOF) {

if (c==2) {

for (i=0;yytext[i];i++)

printf(\yytext[0]='\\000'; }

if (c==3) printf(\

else printf(\} return; } yywrap() { return ; }

30 从略。

4.1消除下列文法的左递归性。 (1) S→SAS→A A→SBA→B A→(S)A→( ) B→［S］B→［ ］ (2) S→ASS→b

A→SAA→a (3) S→(T)S→a S→εT→S T→T,S

4.2设已给文法： S→AbBS→d A→CAbA→Bf B→CSdB→d C→edC→a

试写出对符号串eddfbbd进行带回溯的自顶向下语法分析的过程。 4.3对于如下的文法，用某种高级语言写出递归下降分析程序。 (1) P→begin d; X end X→d;X X→sY Y→;sY Y→ε

(2) 〈程序〉→begin〈语句〉end 〈语句〉→〈赋值语句〉|〈条件语句〉 〈赋值语句〉→〈变量〉∶=〈表达式〉 〈条件语句〉→if〈表达式〉then〈语句〉 〈表达式〉→〈变量〉

〈表达式〉→〈表达式〉+〈变量〉 〈变量〉→i

4.4对于如下的文法，求出各个FIRST集和FOLLOW集。 S→aABS→bA S→εA→aAb A→εB→bB B→ε

4.5试证明： 任何具有左递归性的前后文无关文法均非LL(1)文法。 4.6试证明： 任何LL(1)文法均为无二义性文法。 4.7验证下列文法是否为LL(1)文法。 (1)S→ABS→CDa A→abA→c B→dEC→eC C→εD→fD D→fE→dE E→ε

(2) S→aABbCDS→ε A→ASdA→ε B→SAcB→eC B→εC→Sf C→CgC→ε