第3章词法分析和词法分析程序ppt课件.ppt

《第3章词法分析和词法分析程序ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理第三章词法分析和词法分析程序PrinciplesofCompilerDesignChapter3.LexicalAnalysis3.1设计扫描器时应考虑的问题词法分析程序亦称为扫描器任务：扫描程序，识别单词扫描器的输出是语法分析程序的输入3.1HowtoconstructalexicalanalyzerAlexicalanalyzerisalsocalledScannerThemaintaskofthelexicalanalyzeristoreadtheinputcharactersofthesourcepro

2、gram,andgroupthemintolexemes.Thelexicalanalyzeroutputsasequenceoftokensforeachlexemeinthesourceprogramtotheparserforsyntaxanalysis.3.1.1词法分析的必要性描述单词的结构比其它语法结构简单，仅用3型文法就够了；将单词识别从语法分析识别分离出来，可采用更有效的工具实现；有些语言的单词识别与前后文相关，不宜将其与语法分析合并；使编译程序各部分独立出来，有利于设计、调试和维护3.1.1Lexic

3、alAnalysisVersusParsingTheseparationoflexicalandsyntacticanalysisoftenleadstoacleaneroveralldesign.Compilerefficiencyisimproved.Aseparatelexicalanalyzerallowsustoapplyspecializedtechniquesthatserveonlythelexicaltask,notthejobofparsing.Compilerportabilityisenhanc

4、ed.Input-device-specificpeculiaritiescanberestrictedtothelexicalanalyzer.3.1.2单词符号的内部表示常用的内部表示方法:(class,value)为便于阅读，常用助记符（或常量标识符、宏定义等）表示class。单词的分类方法：可一词一类（+、-、begin、end等）或多词一类（如关键字类、操作符类、分隔符类、变量名类、常数类等）。在识别出变量名、函数（过程）名时，还应进行查填符号表的工作。3.1.2TokensAtokenisapaircons

5、istingofatokennameandanoptionalattributevalue(class,value)Thetokennameisanabstractsymbolrepresentingakindoflexicalunit,e.g.,aparticularkeyword,orasequenceofinputcharactersdenotinganidentifier.Thetokennamesaretheinputsymbolsthattheparserprocesses.Wewilloftenrefer

6、toatokenbyitstokenname.3.1.3识别标识符的若干约定和策略一般来说，单词的长度是有限制的。在允许长度下，应按最长匹配原则进行识别有时需要超前扫描来进行单词识别。在进行超前扫描时，还应注意“回退”字符，即将多吃掉的字符退还回输入缓冲区。3.1.3TokenRecognitionAlltokenshavefinitelength.Tokensarerecognizedwhenallpossiblesymbolsarescanned.Sometimesweneedtolookatleastoneadd

7、itionalcharacterahead.3.2正规文法和状态转换图3.2RegularExpressions&TransitionDiagrams3.2.1由正规文法构造状态转换图程序设计语言的单词都能用正规文法描述一般说来，凡能用正规文法描述的语言，均可由某种有限状态算法——状态转换图进行分析状态转换图：有向图（一个初态+N个终态）射出结点，进入结点3.2.1Conversionfromregular-expressionpatternstotransitiondiagramsTokenscanbedescri

8、bedbyregular-expressionSuchtokenscanthereforebeanalyzedbytransitiondiagrams.Transitiondiagram:Directedflowchartswithone(onestateoflexemeBeginandsomestatescalledfinal)