编译原理2E全套配套课件龙书 Chapter_two(2).ppt

《编译原理2E全套配套课件龙书 Chapter_two(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、COMPILERCONSTRUCTIONPrinciplesandPracticeKennethC.Louden2.Scanning(LexicalAnalysis)PARTTWOContentsPARTONE2.1TheScanningProcess2.2RegularExpression2.3FiniteAutomataPARTTWO2.4FromRegularExpressionstoDFAs[Open]2.5ImplementationofaTINYScanner[Open]2.6UseofLextoGenerateaScanne

2、rAutomatically[Open]2.4FromRegularExpressionToDFAsMainPurposeStudyanalgorithm:TranslatingaregularexpressionintoaDFAviaNFA.RegularExpressionNFADFAProgramContentsFromaRegularExpressiontoanNFA[More]FromanNFAtoaDFA[More]SimulatinganNFAusingSubsetConstruction[More]Minimizingth

3、eNumberofStatesinaDFA[More]2.4.1FromaRegularExpressiontoanNFATheIdeaofThompson’sConstructionUseε-transitionsto“gluetogether”themachineofeachpieceofaregularexpressiontoformamachinethatcorrespondstothewholeexpressionBasicregularexpressionTheNFAsforbasicregularexpressionofth

4、eforma,ε,orφaTheIdeaofThompson’sConstructionConcatenation:toconstructanNFAequaltorsToconnecttheacceptingstateofthemachineofrtothestartstateofthemachineofsbyanε-transition.Thestartstateofthemachineofrasitsstartstateandtheacceptingstateofthemachineofsasitsacceptingstate.Th

5、ismachineacceptsL(rs)=L(r)L(s)andsocorrespondstotheregularexpressionrs.…r…sTheIdeaofThompson’sConstructionChoiceamongalternatives:ToconstructanNFAequaltor

6、sToaddanewstartstateandanewacceptingstateandconnectedthemasshownusingε-transitions.Clearly,thismachineacceptsthelang

7、uageL(r

8、s)=L(r)UL(s),andsocorrespondstotheregularexpressionr

9、s.…r…sTheIdeaofThompson’sConstructionRepetition:Givenamachinethatcorrespondstor，Constructamachinethatcorrespondstor*Toaddtwonewstates,astartstateandanacceptingstate.Therepetitionisaffordedbythenewε-transitio

10、nfromtheacceptingstateofthemachineofrtoitsstartstate.Todrawanε-transitionfromthenewstartstatetothenewacceptingstate.Thisconstructionisnotunique,simplificationsarepossibleinthemanycases.…rExamplesofNFAsConstructionExample1.12:Translateregularexpressionab

11、aintoNFAabab

12、abaExamplesofNFAsConstructionExample1.13:Translateregularexpressionletter(letter

13、digit)*into