《编译原理编译原理编译原理 (18).ppt》由会员分享，可在线阅读，更多相关《编译原理编译原理编译原理 (18).ppt（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、compiler1Chapter 2Scanning From Regular Expression to DFAcompilerS2From Regular Expression to DFARegular expressionNFADFAProgramcompilerS3From a Regular Expression to NFAThe construction we will describe is know as Thompsons construction.It uses-transitions to“glue together”the machines of each piec
2、e of a regular pilerS4Basic Regular ExpressionaacompilerS5ConcatenationClearly,this machine accepts L(rs)=L(r)L(s)and corresponds to the regular expression rsrrsNFA for a regular expression rsNFA for a regular expression sNFA for a regular expression rscompilerS6Choice among AlternativesWe added a n
3、ew start state and a new accepting state using-transitions.This machine accepts L(r|s)=L(r)L(s).rscompilerS7RepetitionThis machine corresponds to r*.r compilerS8Example 2.12Translate the regular expression ab|a into a NFA.ababaabcompilerS9Example 2.13letter(letter|digit)*letterdigitletterdigitletter