递归下降分析 (21).ppt

《递归下降分析 (21).ppt》由会员分享，可在线阅读，更多相关《递归下降分析 (21).ppt（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、compilerS1Minimizing Number of StatesoThe resulting DFA may be more complex than necessary.nIn Example 2.15 we got DFA for a*,but there is a more simple DFA.oImportant result from automata theory:For any given DFA there is an equivalent DFA containing a minimum number of states,and it is unique.1,2,

2、42,3,4aaacompilerS2Minimizing Number of States Algorithm1.Create two sets of states:all accepting states and all non-accepting states.2.For each set of states,consider the transitions on each character a of the alphabet.If all states in the set have transitions on a to the same set of states,then it

3、 defines a-transition from the set of states to itself.If there are two states in the set s and t that have transitions on a that land in different sets,we must split the set of states into two sets according to where a-transitions land.3.Repeat step 2 until either all states contain one element or

4、no further splitting pilerS3Example 2.1812,3,4,5,7,104,5,6,7,9,104,5,7,8,9,10letterletterletterletterdigitdigitdigitletter letterdigitcompilerS4Example 2.19o(a|)b*oAll states are accepting states.Each accepting state has a b-transition to another accepting state.oa distinguishes state 1 from states 2 and 3.nThere is a-transition to error state from 2 and 3123abbb12,3abbb