解：状态转换表为
{1} {2,3,4,5,7,10} {4,5,6,7,9,10} {4,5,7,8,9,10} 最小化DFA为：
letter {2,3,4,5,7,10} {4,5,6,7,9,10} {4,5,6,7,9,10} {4,5,6,7,9,10} digit {4,5,7,8,9,10} {4,5,7,8,9,10} {4,5,7,8,9,10}
例2.19 将下面与正则表达式(a| ε) b*对应的DFA进行最小化。
解：状态转换表为
{1} {2} {3} 最小化DFA为：
a {2} b {3} {3} {3}
词法分析代码：
state := 1; {start}
while state = 1 or 2 do case state of
1: case input character of
letter: advance the input;
state := 2;
else state := ... {error or other}; end case;
2: case input character of letter, digit: advance the input;
state := 2; {actually unnecessary} else state := 3; end case; end case; end while;
if state = 3 then accept else error;
state := 1; {start}
while state = 1, 2, 3 or 4 do case state of
1: case input character of “/”: advance the input; state := 2;
else state := ... ; {error or other} end case;
2: case input character of “*”: advance the input; state := 3;
else state := ... ; {error or other} end case;
3: case input character of “*”: advance the input; state := 4;
else advance the input; {and stay in state 3} end case;
4: case input character of
“/” : advance the input; state := 5;
“*”: advance the input; {and stay in state 4} else advance the input; state := 3; end case; end case; end while;
if state = 5 then accept else error;
递归子程序分析法
问题1： G[S] = { }
S → aA | bB A → cdA | d B → efB | f
试编写一个能分析该文法所对应任何串（如串acdd）的程序。
void match( expectedToken ){ if( token == expectedToken ) getToken(); else
Error(); }
void S(){
if( token == ‘a’ ){ match(‘a’); A();
}else if( token == ‘b’ ){ match(‘b’); B();
}else Error(); }//S
void A(){
if( token == ’c’ ){ match(‘c’); match(‘d’); A();
}else if( token == ‘d’ ){ match(‘d’); }else Error(); }//A
void B(){
if( token == ‘e’ ){ match(‘e’); match(‘f’); B();
}else if( token == ‘f’ ){
相关推荐：
loading