東北大學(xué)秦皇島分校編譯原理課件第六章

東北大學(xué)秦皇島分校編譯原理課件第六章目錄contents引言語(yǔ)法分析器概述自頂向下語(yǔ)法分析自底向上語(yǔ)法分析語(yǔ)法分析器的實(shí)現(xiàn)語(yǔ)法錯(cuò)誤處理與恢復(fù)總結(jié)與展望01引言本章主要介紹編譯原理中的語(yǔ)法分析部分，包括語(yǔ)法分析器的功能、分類(lèi)、設(shè)計(jì)原理和實(shí)現(xiàn)方法等內(nèi)容。語(yǔ)法分析是編譯過(guò)程的核心環(huán)節(jié)之一，其主要任務(wù)是根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，對(duì)輸入的源程序進(jìn)行結(jié)構(gòu)上的分析和檢查，構(gòu)造出抽象語(yǔ)法樹(shù)或產(chǎn)生式規(guī)則所描述的中間代碼。通過(guò)本章的學(xué)習(xí)，學(xué)生應(yīng)該能夠掌握語(yǔ)法分析的基本原理和方法，了解不同類(lèi)型語(yǔ)法分析器的特點(diǎn)和適用場(chǎng)景，并能夠設(shè)計(jì)和實(shí)現(xiàn)簡(jiǎn)單的語(yǔ)法分析器。章節(jié)概述學(xué)習(xí)目標(biāo)掌握LL(1)分析法和遞歸下降分析法的基本原理和實(shí)現(xiàn)方法，能夠設(shè)計(jì)和實(shí)現(xiàn)簡(jiǎn)單的LL(1)分析器和遞歸下降分析器。掌握上下文無(wú)關(guān)文法和上下文有關(guān)文法的概念和區(qū)別，了解正規(guī)文法和正則表達(dá)式的相關(guān)內(nèi)容。掌握語(yǔ)法分析器的功能和分類(lèi)，了解不同類(lèi)型語(yǔ)法分析器的特點(diǎn)和適用場(chǎng)景。了解LR分析法和自底向上分析法的基本原理和實(shí)現(xiàn)方法，能夠理解和分析相關(guān)算法和代碼。掌握語(yǔ)法錯(cuò)誤的處理方法和報(bào)告方式，了解編譯優(yōu)化和代碼生成的相關(guān)內(nèi)容。02語(yǔ)法分析器概述語(yǔ)法分析器的定義語(yǔ)法分析器是一種計(jì)算機(jī)程序，用于將輸入的符號(hào)序列（通常是源代碼）轉(zhuǎn)換為抽象語(yǔ)法樹(shù)（AST）或其他中間表示形式。語(yǔ)法分析器是編譯器或解釋器的重要組成部分，負(fù)責(zé)檢查源代碼的語(yǔ)法正確性并構(gòu)建其內(nèi)部表示。識(shí)別語(yǔ)法錯(cuò)誤語(yǔ)法分析器通過(guò)檢查源代碼中符號(hào)的排列和組合，識(shí)別出不符合語(yǔ)法規(guī)則的代碼段，并報(bào)告錯(cuò)誤。構(gòu)建抽象語(yǔ)法樹(shù)對(duì)于符合語(yǔ)法規(guī)則的代碼段，語(yǔ)法分析器將其轉(zhuǎn)換為抽象語(yǔ)法樹(shù)，這是一種反映源代碼結(jié)構(gòu)和語(yǔ)義的內(nèi)部表示形式。為后續(xù)階段提供信息語(yǔ)法分析器生成的抽象語(yǔ)法樹(shù)和其他中間表示形式為后續(xù)的語(yǔ)義分析、優(yōu)化和代碼生成等階段提供了必要的信息。語(yǔ)法分析器的功能010203自頂向下分析器從根節(jié)點(diǎn)開(kāi)始，根據(jù)語(yǔ)法規(guī)則逐步推導(dǎo)出輸入符號(hào)序列的分析器。也稱(chēng)為預(yù)測(cè)分析器或遞歸下降分析器。自底向上分析器從輸入符號(hào)序列開(kāi)始，逐步歸約到根節(jié)點(diǎn)的分析器。也稱(chēng)為移進(jìn)-歸約分析器或LR分析器。確定性分析器和非確定性分析器根據(jù)分析算法的性質(zhì)，語(yǔ)法分析器可分為確定性分析器和非確定性分析器。確定性分析器對(duì)于每個(gè)輸入符號(hào)序列都能給出唯一的正確分析結(jié)果，而非確定性分析器可能給出多個(gè)可能的分析結(jié)果。語(yǔ)法分析器的分類(lèi)03自頂向下語(yǔ)法分析遞歸下降分析的基本思想從文法的開(kāi)始符號(hào)出發(fā)，根據(jù)產(chǎn)生式規(guī)則進(jìn)行推導(dǎo)，直到推導(dǎo)出輸入符號(hào)串或發(fā)現(xiàn)推導(dǎo)錯(cuò)誤為止。遞歸下降分析的步驟首先構(gòu)造一組遞歸過(guò)程，每個(gè)過(guò)程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。然后，從代表開(kāi)始符號(hào)的過(guò)程開(kāi)始，根據(jù)當(dāng)前輸入符號(hào)和預(yù)測(cè)分析表選擇正確的產(chǎn)生式進(jìn)行推導(dǎo)。如果推導(dǎo)成功，則繼續(xù)處理下一個(gè)輸入符號(hào)；否則，報(bào)告錯(cuò)誤。遞歸下降分析的特點(diǎn)易于理解和實(shí)現(xiàn)，但存在回溯問(wèn)題，效率較低。遞歸下降分析要點(diǎn)三預(yù)測(cè)分析的基本思想根據(jù)已經(jīng)讀入的輸入符號(hào)和語(yǔ)法規(guī)則，預(yù)測(cè)下一個(gè)可能的輸入符號(hào)，并根據(jù)預(yù)測(cè)結(jié)果指導(dǎo)語(yǔ)法分析的進(jìn)行。要點(diǎn)一要點(diǎn)二預(yù)測(cè)分析的步驟首先構(gòu)造預(yù)測(cè)分析表，然后根據(jù)當(dāng)前讀入的輸入符號(hào)和棧頂?shù)姆墙K結(jié)符查找預(yù)測(cè)分析表，得到相應(yīng)的動(dòng)作指導(dǎo)。按照動(dòng)作指導(dǎo)進(jìn)行推導(dǎo)或讀入新的輸入符號(hào)，直到棧為空且所有輸入符號(hào)都已處理完畢。預(yù)測(cè)分析的特點(diǎn)避免了回溯問(wèn)題，提高了效率。但需要構(gòu)造預(yù)測(cè)分析表，且對(duì)于某些文法可能不存在有效的預(yù)測(cè)分析算法。要點(diǎn)三預(yù)測(cè)分析LL(1)文法的定義一個(gè)文法G是LL(1)文法，當(dāng)且僅當(dāng)對(duì)于G的任意兩個(gè)產(chǎn)生式A→α和A→β，滿足SELECT(A→α)∩SELECT(A→β)=?，其中SELECT(A→α)表示在當(dāng)前輸入符號(hào)為a且A為棧頂符號(hào)時(shí)，能夠推導(dǎo)出α的所有a的集合。LL(1)文法的判別方法首先求出文法的所有SELECT集合，然后檢查是否存在任意兩個(gè)產(chǎn)生式的SELECT集合有交集。如果存在交集，則該文法不是LL(1)文法；否則，是LL(1)文法。LL(1)文法的特點(diǎn)LL(1)文法是自頂向下語(yǔ)法分析的重要基礎(chǔ)之一。一個(gè)文法如果是LL(1)文法，則存在有效的預(yù)測(cè)分析算法對(duì)其進(jìn)行語(yǔ)法分析。同時(shí)，LL(1)文法也具有易于理解和實(shí)現(xiàn)的特點(diǎn)。LL(1)文法及判別方法04自底向上語(yǔ)法分析算符優(yōu)先關(guān)系定義算符間的優(yōu)先關(guān)系，用于確定表達(dá)式中算符的求值順序。棧的應(yīng)用使用棧來(lái)保存臨時(shí)結(jié)果和尚未處理的符號(hào)，按照優(yōu)先關(guān)系逐步進(jìn)行歸約。算法實(shí)現(xiàn)通過(guò)掃描輸入符號(hào)并比較棧頂符號(hào)與當(dāng)前符號(hào)的優(yōu)先關(guān)系，執(zhí)行相應(yīng)的入棧或歸約操作。算符優(yōu)先分析一種可用于自底向上語(yǔ)法分析的文法，具有確定的句柄識(shí)別和預(yù)測(cè)能力。LR(1)文法根據(jù)LR(1)文法構(gòu)造分析表，包括動(dòng)作表和狀態(tài)轉(zhuǎn)換表。分析表構(gòu)造使用棧保存狀態(tài)和符號(hào)，根據(jù)輸入符號(hào)和分析表執(zhí)行動(dòng)作，逐步完成語(yǔ)法分析。分析過(guò)程LR(1)分析SLR(1)分析和LALR(1)分析SLR(1)分析和LALR(1)分析在減少分析表大小方面有所優(yōu)化，但可能不適用于所有文法。在實(shí)際應(yīng)用中，需要根據(jù)具體需求選擇合適的分析方法。比較與應(yīng)用簡(jiǎn)化LR(1)分析的方法，通過(guò)合并具有相同前綴的LR(1)項(xiàng)集來(lái)減少分析表的大小。SLR(1)分析在SLR(1)分析的基礎(chǔ)上進(jìn)一步合并狀態(tài)，生成更小的分析表，同時(shí)保持較高的分析能力。LALR(1)分析05語(yǔ)法分析器的實(shí)現(xiàn)ANTLRANTLR（ANotherToolforLanguageRecognition）是一個(gè)強(qiáng)大的語(yǔ)法分析器生成器，支持多種語(yǔ)言和平臺(tái)。Bison/FlexBison是一個(gè)Yacc的替代品，F(xiàn)lex是一個(gè)Lex的替代品，它們提供了更多的功能和更好的性能。Lex/YaccLex是一個(gè)詞法分析器生成器，Yacc是一個(gè)語(yǔ)法分析器生成器，它們通常一起使用來(lái)構(gòu)建編譯器前端。工具介紹實(shí)現(xiàn)步驟定義語(yǔ)法規(guī)則使用BNF或EBNF等形式化工具定義語(yǔ)言的語(yǔ)法規(guī)則。構(gòu)建詞法分析器使用Lex、Flex等工具生成詞法分析器，將輸入文本分割成一個(gè)個(gè)的單詞或符號(hào)。構(gòu)建語(yǔ)法分析器使用Yacc、Bison、ANTLR等工具生成語(yǔ)法分析器，根據(jù)定義的語(yǔ)法規(guī)則對(duì)輸入文本進(jìn)行語(yǔ)法分析，生成語(yǔ)法樹(shù)或抽象語(yǔ)法樹(shù)。實(shí)現(xiàn)語(yǔ)義分析在語(yǔ)法分析的基礎(chǔ)上，實(shí)現(xiàn)語(yǔ)義分析，檢查語(yǔ)法樹(shù)是否符合語(yǔ)言的語(yǔ)義規(guī)則。首先定義算術(shù)表達(dá)式的語(yǔ)法規(guī)則，如加法、減法、乘法、除法等。然后使用Lex生成詞法分析器，將輸入文本分割成一個(gè)個(gè)的單詞或符號(hào)，如數(shù)字、運(yùn)算符等。最后實(shí)現(xiàn)語(yǔ)義分析，檢查語(yǔ)法樹(shù)是否符合算術(shù)表達(dá)式的語(yǔ)義規(guī)則，如運(yùn)算符的優(yōu)先級(jí)、括號(hào)的使用等。接著使用Yacc生成語(yǔ)法分析器，根據(jù)定義的語(yǔ)法規(guī)則對(duì)輸入文本進(jìn)行語(yǔ)法分析，生成語(yǔ)法樹(shù)。以一個(gè)簡(jiǎn)單的算術(shù)表達(dá)式為例，演示如何使用Lex和Yacc構(gòu)建語(yǔ)法分析器。實(shí)例演示06語(yǔ)法錯(cuò)誤處理與恢復(fù)語(yǔ)法錯(cuò)誤類(lèi)型詞法錯(cuò)誤語(yǔ)法錯(cuò)誤語(yǔ)義錯(cuò)誤如缺少分號(hào)、括號(hào)不匹配等。如類(lèi)型不匹配、變量未聲明等。如拼寫(xiě)錯(cuò)誤、非法字符等。恐慌模式恢復(fù)遇到錯(cuò)誤時(shí)立即停止編譯，報(bào)告錯(cuò)誤信息。語(yǔ)句級(jí)別恢復(fù)在錯(cuò)誤發(fā)生處跳過(guò)整個(gè)語(yǔ)句，以便繼續(xù)編譯后續(xù)代碼。短語(yǔ)級(jí)別恢復(fù)嘗試在錯(cuò)誤發(fā)生處跳過(guò)一些符號(hào)，以恢復(fù)語(yǔ)法結(jié)構(gòu)的正確性。錯(cuò)誤恢復(fù)策略缺少分號(hào)錯(cuò)誤編譯器可以在錯(cuò)誤位置插入分號(hào)，并給出警告信息。變量未聲明錯(cuò)誤編譯器可以指出未聲明的變量名稱(chēng)，并給出錯(cuò)誤信息。括號(hào)不匹配錯(cuò)誤編譯器可以指出不匹配的括號(hào)位置，并給出錯(cuò)誤信息。錯(cuò)誤處理實(shí)例07總結(jié)與展望章節(jié)總結(jié)介紹了編譯原理的基本概念、原理和方法，包括詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成等各個(gè)階段。詳細(xì)闡述了編譯原理中的核心技術(shù)和算法，如正則表達(dá)式、有限自動(dòng)機(jī)、上下文無(wú)關(guān)文法、語(yǔ)法制導(dǎo)翻譯等，以及它們?cè)诰幾g過(guò)程中的應(yīng)用。通過(guò)實(shí)例分析和編程實(shí)踐，加深了對(duì)編譯原理的理解和掌握，提高了分析問(wèn)題和解決問(wèn)題的能力。后續(xù)章節(jié)將介紹更高級(jí)的編譯優(yōu)化技術(shù)，如循環(huán)展開(kāi)、內(nèi)聯(lián)函數(shù)、常量折疊等，以提高生成代碼