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

S=Aa+B (1) A=Cc+Bb (2) B=Bb+a(3) C=D+Bab(4) D=d(5)

可得 D=dB=ab*C=ab*ab|bA=(ab*ab|b)c + ab*b S=(ab*ab|b)ca+ab*ba +ab* =(ab*ab|b)ca| ab*ba| ab* 20

? ?

识别此语言的正规式是S=?LABEL?d(d|,d)*; 从略。

21 从略。 22 构造NFA

其余从略。

23 下面举一个能够识别1,2,3,10,20,100的例子，读者可以推而广之。 %{

#include #include

#include #define ON1 #define TW 2 #define THRE 3 #define TE 10 #define TWENT 20 #define HUNDRE 100 #define WHITE9999 %}

upper[A-Z] %%

ONEreturn ON; TWOreturn TW; THREEreturn THRE; TENreturn TE; TWENTYreturn TWENT; HUNDREDreturn HUNDRE; \\\nreturn0; %%

main(int argc,char *argv[]) {

int c,i=0;

char tmp[30]; if (argc==2) {

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

printf(\} }

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

switch(c) { case ON: c=yylex();

if (c==0) goto {i+=1;label;} c=yylex(); if (c==HUNDRE) i+=100; else i+=1; break;

case TW:c=yylex(); c=yylex(); if (c==HUNDRE)

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(\} }