嵌軟第一學(xué)期萬海編譯原理課件analysis

PrinciplesofCompilerLecture5 ysisLecturer:HaiNotethatmostoftheseslideswerecreatedDr.Zhong-meiSHU(DepartmentofComputerScience)Dr.HanLIN(DepartmentofComputerScience)CourseCourse語法分析的任ThepipebetweenaparserandaMethodinvocation(procedurecall)Logicalvs.physical Parsetree,derivation,andreduction語法分析的任語法分析要解決的問題包括token）例如：同樣一個數(shù)字，在程序中可能是一個加數(shù)，可能是數(shù)的下標，可能是循環(huán)的次數(shù)，可能是某個函數(shù)的參數(shù)檢查語句或程序是否符合程序語言的問題的進一步明要解決這些問題 須先明確一個程序包括哪些語法成分這些語法成分以什么方式構(gòu)成程因為我們要用計算機來分析，所以需要嚴格精確的借助形式化的思 思比如對于含else的if語句，其構(gòu)成方式如下if(expr)stmtelseif語句是語句的stmt→if(expr)stmtelseParsingTop-downHowtochooseauniqueproductioninmultiplecandidates?Bottom-upHowtofindthehandleinasententialformTop-DownAmotivatingTop-Down|^|array[simple]of||numdotdotarray[1..10]ofParsingProcessParsingProcess[]Match

[]Match

[]Derivewith"simplenumdotdot

[]Match

[]Match

[]Match

[]Match

[]Match

[]

Derivewith"type

[]

Derivewith"simple

[]MatchandAccept

[]一個上下文無關(guān)文法（CFG）包括四終端符號（terminal）的集合非終端符號（nonterminal）的集合若干以下形式的產(chǎn)生式X其 XN且YiTN一些為了方便的規(guī)多個形如A1A2Ak的產(chǎn)生式A1|2||例EEE|E*E|E|(E)|顯然對于上面的文法，id(idid)id*id都是符合文法定義的，而(id,id*+id都是不符合的Chomskyr3r3eAaBorAa,whereA,BNa{}.ApermittedifAisthestartsymbolanddoesnotappearontherightofanyproduction.2A,AN(1yContext-,,(N)*||can'tbe,unlessisthestartsymbolanddoesnotappearontherightofanyproduction.0,,(N)*TuringMachineUsefulinWhatlanguagesitcangenerateL0={anbn|nionofsomeprobleminWhatlanguagesitcannotgenerateL1={c|(a|b)*a,b,cionofsomeprobleminHowtosolvetheproblemL2={anbmcndm|n1mionofsomeprobleminHowtosolvetheproblem推例如EE(E)(EE)(idE)(id所有句子的集合，記為L(G)斷一個終端符號串x是討練用上下文無關(guān)文法定義下列語L{0n1n|n只含有0和1的回文只含有(和)的匹配括號最左推導(dǎo)和最右推例如例如文法的二義例：對于文法EEE|E*E|E|E|存在句子id+id*id，有兩種推文法的二義這兩種推導(dǎo)對應(yīng)兩棵不同的分因此這個文法是二義的文文文法二義性的消EEE|E*E|(E)|文法二義性的消文法二義性的消壞消息：有些文法的二義性是無法消L{anbncmdm|n,m}{anbmcmdn|n,mCFGCFG.）文法二義性的判的.（證明超出課程范圍）上下文無關(guān)文法vs.正則表達正則表達式無法定義語FromNFAto