《編譯原理教程》第二章詞法分析

編譯原理教程第二章詞法分析目錄引言詞法分析基本概念正規(guī)表達(dá)式及其性質(zhì)有限自動(dòng)機(jī)及其性質(zhì)詞法分析器設(shè)計(jì)與實(shí)現(xiàn)典型案例分析與實(shí)踐總結(jié)回顧與拓展延伸01引言編譯原理概述編譯原理是計(jì)算機(jī)科學(xué)的一個(gè)重要分支，研究如何將高級(jí)語(yǔ)言程序翻譯成等價(jià)的低級(jí)語(yǔ)言程序，同時(shí)保證翻譯的正確性和效率。編譯過程通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析、優(yōu)化和代碼生成等多個(gè)階段，每個(gè)階段都有其特定的任務(wù)和目標(biāo)。詞法分析在編譯過程中的作用詞法分析是編譯過程的第一個(gè)階段，主要任務(wù)是將輸入的源程序分割成一個(gè)個(gè)的單詞或符號(hào)，即詞素（token）。詞法分析器（lexer或scanner）會(huì)讀取源程序，根據(jù)預(yù)定義的詞法規(guī)則識(shí)別出單詞和符號(hào)，并將其轉(zhuǎn)換為內(nèi)部表示形式（通常是token），供后續(xù)階段使用。詞法分析的準(zhǔn)確性對(duì)編譯器的正確性和效率至關(guān)重要，因?yàn)槿魏五e(cuò)誤或遺漏的詞素都可能導(dǎo)致編譯失敗或生成錯(cuò)誤的代碼。本章學(xué)習(xí)目標(biāo)和要求學(xué)習(xí)詞法規(guī)則的定義和描述方法，能夠編寫簡(jiǎn)單的詞法規(guī)則。掌握詞法分析器的實(shí)現(xiàn)方法和技術(shù)，能夠編寫簡(jiǎn)單的詞法分析器。掌握詞法分析的基本概念和原理，了解詞法分析器的作用和工作流程。了解詞法分析中的常見問題和解決方法，如處理空白、注釋和特殊字符等。02詞法分析基本概念詞法分析是編譯過程的第一階段，主要任務(wù)是對(duì)源程序進(jìn)行掃描，按照構(gòu)詞規(guī)則識(shí)別出各類單詞符號(hào)，并將其轉(zhuǎn)換為內(nèi)部編碼表示。詞法分析器作為編譯器的前端，主要功能是讀取源程序，將其分解為單詞符號(hào)序列，為后續(xù)語(yǔ)法分析和語(yǔ)義分析提供基礎(chǔ)。詞法分析定義及功能詞法分析功能詞法分析定義單詞符號(hào)單詞符號(hào)是程序語(yǔ)言的基本組成單位，包括標(biāo)識(shí)符、關(guān)鍵字、運(yùn)算符、界符等。詞法規(guī)則詞法規(guī)則定義了如何識(shí)別和處理這些單詞符號(hào)。通常，詞法規(guī)則包括單詞的構(gòu)成、分類和編碼等方面的規(guī)定。單詞符號(hào)與詞法規(guī)則正規(guī)表達(dá)式是一種描述單詞符號(hào)結(jié)構(gòu)的形式化工具，它可以用來表示詞法規(guī)則。正規(guī)表達(dá)式具有簡(jiǎn)潔、直觀和易于操作的特點(diǎn)。正規(guī)表達(dá)式有限自動(dòng)機(jī)是一種識(shí)別正規(guī)表達(dá)式的數(shù)學(xué)模型，它可以用來實(shí)現(xiàn)詞法分析器。有限自動(dòng)機(jī)由一組狀態(tài)、輸入符號(hào)、轉(zhuǎn)移函數(shù)和接受狀態(tài)等要素構(gòu)成，能夠高效地識(shí)別和處理單詞符號(hào)序列。有限自動(dòng)機(jī)正規(guī)表達(dá)式與有限自動(dòng)機(jī)03正規(guī)表達(dá)式及其性質(zhì)正規(guī)表達(dá)式定義及運(yùn)算規(guī)則正規(guī)表達(dá)式定義正規(guī)表達(dá)式是由字母表Σ上的字符、ε（空字符）以及運(yùn)算符“|”（或）、“·”（連接）和“*”（閉包）構(gòu)成的表達(dá)式，用于描述Σ上的正規(guī)集。運(yùn)算規(guī)則正規(guī)表達(dá)式的運(yùn)算遵循優(yōu)先級(jí)規(guī)則，其中“*”具有最高優(yōu)先級(jí)，“·”次之，“|”最低。同時(shí)，正規(guī)表達(dá)式中的括號(hào)可以改變運(yùn)算的優(yōu)先級(jí)。性質(zhì)正規(guī)表達(dá)式具有一些重要性質(zhì)，如交換律、結(jié)合律、分配律等，這些性質(zhì)在簡(jiǎn)化正規(guī)表達(dá)式和證明等價(jià)性時(shí)非常有用。等價(jià)變換等價(jià)變換是指在保持正規(guī)表達(dá)式所描述的正規(guī)集不變的情況下，對(duì)表達(dá)式進(jìn)行簡(jiǎn)化和變換。常見的等價(jià)變換包括消除冗余、合并相同項(xiàng)、提取公因子等。正規(guī)表達(dá)式性質(zhì)與等價(jià)變換例子1描述由0和1組成的所有二進(jìn)制數(shù)。該語(yǔ)言可以用正規(guī)表達(dá)式(0|1)*來描述，表示0和1可以任意組合，包括空字符串。例子2描述所有以ab開頭，以cd結(jié)尾的字符串。該語(yǔ)言可以用正規(guī)表達(dá)式ab(Σ*)cd來描述，其中Σ*表示任意字符串。例子3描述所有包含子串“xyz”的字符串。該語(yǔ)言可以用正規(guī)表達(dá)式(Σ*)xyz(Σ*)來描述，表示在任意位置都可以出現(xiàn)子串“xyz”。010203舉例：簡(jiǎn)單語(yǔ)言正規(guī)表達(dá)式描述04有限自動(dòng)機(jī)及其性質(zhì)特點(diǎn)對(duì)于每個(gè)輸入符號(hào)和當(dāng)前狀態(tài)，轉(zhuǎn)移函數(shù)都有唯一確定的下一個(gè)狀態(tài)。DFA的運(yùn)行過程是確定的，即對(duì)于相同的輸入序列，總是得到相同的結(jié)果。在任何給定的時(shí)刻，DFA都處于一個(gè)確定的狀態(tài)。定義：確定有限自動(dòng)機(jī)（DFA）是一個(gè)五元組，包括狀態(tài)集、輸入符號(hào)集、轉(zhuǎn)移函數(shù)、初始狀態(tài)和接受狀態(tài)集。確定有限自動(dòng)機(jī)（DFA）定義及特點(diǎn)NFA的運(yùn)行過程是不確定的，即對(duì)于相同的輸入序列，可能得到不同的結(jié)果。NFA允許“ε-轉(zhuǎn)移”，即在沒有輸入符號(hào)的情況下從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)。對(duì)于每個(gè)輸入符號(hào)和當(dāng)前狀態(tài)，NFA可能有多個(gè)可能的下一個(gè)狀態(tài)。定義：非確定有限自動(dòng)機(jī)（NFA）與DFA類似，但轉(zhuǎn)移函數(shù)可以映射到一個(gè)狀態(tài)集，而不是單一狀態(tài)。特點(diǎn)非確定有限自動(dòng)機(jī)（NFA）定義及特點(diǎn)DFA與NFA之間轉(zhuǎn)換關(guān)系通過子集構(gòu)造法可以將NFA轉(zhuǎn)換為等價(jià)的DFA。該方法將NFA的狀態(tài)集劃分為不相交的子集，每個(gè)子集代表DFA的一個(gè)狀態(tài)。轉(zhuǎn)換后的DFA具有與原始NFA相同的語(yǔ)言識(shí)別能力。NFA轉(zhuǎn)換為DFA任何DFA都可以直接看作是一個(gè)特殊的NFA，其中每個(gè)轉(zhuǎn)移都是確定的，并且沒有ε-轉(zhuǎn)移。因此，將DFA轉(zhuǎn)換為NFA是簡(jiǎn)單的，只需保留原始DFA的結(jié)構(gòu)即可。DFA轉(zhuǎn)換為NFA05詞法分析器設(shè)計(jì)與實(shí)現(xiàn)123使用正規(guī)表達(dá)式（正則表達(dá)式）來描述詞法規(guī)則，可以方便地表示詞素的模式和結(jié)構(gòu)。正規(guī)表達(dá)式描述詞法規(guī)則將正規(guī)表達(dá)式轉(zhuǎn)換為有限自動(dòng)機(jī)（FA），通過有限自動(dòng)機(jī)來識(shí)別輸入的字符串是否符合某個(gè)詞法規(guī)則。有限自動(dòng)機(jī)識(shí)別詞素根據(jù)詞法規(guī)則構(gòu)造詞法分析表，通過查表的方式驅(qū)動(dòng)詞法分析過程，提高分析效率。詞法分析表驅(qū)動(dòng)詞法分析過程詞法分析器設(shè)計(jì)思路和方法DFA（確定有限自動(dòng)機(jī)）實(shí)現(xiàn)DFA是一種每個(gè)狀態(tài)對(duì)每個(gè)輸入符號(hào)都有唯一確定的轉(zhuǎn)移狀態(tài)的有限自動(dòng)機(jī)。基于DFA實(shí)現(xiàn)詞法分析器時(shí)，需要構(gòu)造DFA的狀態(tài)轉(zhuǎn)移圖和狀態(tài)轉(zhuǎn)移表，然后根據(jù)輸入字符串進(jìn)行狀態(tài)轉(zhuǎn)移，直到達(dá)到接受狀態(tài)或拒絕狀態(tài)。NFA（非確定有限自動(dòng)機(jī)）實(shí)現(xiàn)NFA是一種允許存在多個(gè)可能的下一個(gè)狀態(tài)的有限自動(dòng)機(jī)。基于NFA實(shí)現(xiàn)詞法分析器時(shí)，需要構(gòu)造NFA的狀態(tài)轉(zhuǎn)移圖和狀態(tài)轉(zhuǎn)移表，然后使用回溯或預(yù)測(cè)的方法來處理非確定性，直到達(dá)到接受狀態(tài)或拒絕狀態(tài)?；贒FA或NFA實(shí)現(xiàn)詞法分析器壓縮DFA狀態(tài)通過合并DFA中的等價(jià)狀態(tài)來減少狀態(tài)數(shù)量，從而減小DFA的大小和提高分析速度。優(yōu)化正則表達(dá)式通過優(yōu)化正則表達(dá)式來減少DFA的狀態(tài)數(shù)量和轉(zhuǎn)移邊的數(shù)量，從而提高分析效率。例如，可以使用貪婪匹配、非貪婪匹配、預(yù)讀等技術(shù)來優(yōu)化正則表達(dá)式。并行處理和分布式處理使用并行處理或分布式處理的方法來提高詞法分析器的處理能力和效率。例如，可以使用多線程或多進(jìn)程來處理多個(gè)輸入字符串，或者使用分布式系統(tǒng)來處理大規(guī)模的輸入數(shù)據(jù)。使用字符類和快速映射將字符映射到相應(yīng)的字符類，可以減少比較次數(shù)和查表時(shí)間，提高分析效率。優(yōu)化技巧和提高效率方法06典型案例分析與實(shí)踐詞法單元定義定義算術(shù)表達(dá)式中的各類詞法單元，如數(shù)字、運(yùn)算符等。詞法分析器實(shí)現(xiàn)編寫詞法分析器，將輸入的算術(shù)表達(dá)式拆分為一個(gè)個(gè)的詞法單元。正則表達(dá)式描述使用正則表達(dá)式描述各類詞法單元的模式。案例一：簡(jiǎn)單算術(shù)表達(dá)式詞法分析詞法規(guī)則定義定義C語(yǔ)言子集中的詞法規(guī)則，包括關(guān)鍵字、標(biāo)識(shí)符、常量、運(yùn)算符等。詞法分析器設(shè)計(jì)設(shè)計(jì)詞法分析器的算法和數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)詞法分析功能。識(shí)別與處理識(shí)別輸入代碼中的各類詞法單元，并進(jìn)行相應(yīng)的處理，如關(guān)鍵字識(shí)別、標(biāo)識(shí)符識(shí)別等。案例二：C語(yǔ)言子集詞法分析列出Java語(yǔ)言中的所有關(guān)鍵字。關(guān)鍵字列表設(shè)計(jì)關(guān)鍵字的識(shí)別算法，可以采用哈希表等數(shù)據(jù)結(jié)構(gòu)提高識(shí)別效率。識(shí)別算法設(shè)計(jì)編寫程序?qū)崿F(xiàn)關(guān)鍵字識(shí)別功能，并進(jìn)行測(cè)試驗(yàn)證其正確性。實(shí)現(xiàn)與測(cè)試案例三：Java語(yǔ)言關(guān)鍵字識(shí)別07總結(jié)回顧與拓展延伸詞法分析器的功能和作用詞法分析器是編譯過程的第一階段，其主要任務(wù)是將輸入的源程序字符串轉(zhuǎn)換為單詞符號(hào)序列，為后續(xù)的語(yǔ)法分析和語(yǔ)義分析提供基礎(chǔ)。詞法單元的定義和分類詞法單元是源程序中的基本語(yǔ)法單位，包括關(guān)鍵字、標(biāo)識(shí)符、常量、運(yùn)算符、界符等。不同的詞法單元有不同的詞法和語(yǔ)法屬性。詞法分析器的設(shè)計(jì)和實(shí)現(xiàn)詞法分析器的設(shè)計(jì)通常采用正則表達(dá)式或有限自動(dòng)機(jī)來描述詞法規(guī)則，實(shí)現(xiàn)時(shí)可以采用手工編寫代碼或使用詞法分析器生成工具。關(guān)鍵知識(shí)點(diǎn)總結(jié)回顧要點(diǎn)三詞法錯(cuò)誤的處理在詞法分析過程中，可能會(huì)遇到源程序中存在的詞法錯(cuò)誤，如拼寫錯(cuò)誤、非法字符等。編譯器需要采取相應(yīng)的錯(cuò)誤處理機(jī)制，如報(bào)告錯(cuò)誤信息、定位錯(cuò)誤位置等。要點(diǎn)一要點(diǎn)二詞法分析器的優(yōu)化為了提高詞