編譯原理簡明教程（第3版）-課件 第4章 詞法分析

新工科建設(shè)·計算機類系列教材

免費提供編譯原理16目錄第一章

概述第二章形式語言理論基礎(chǔ)第三章自動機理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號表和出錯處理第十一章

面向?qū)ο笳Z言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造4詞法分析學(xué)習(xí)目標(biāo)詞法分析是編譯過程的第一步，其主要任務(wù)是對源程序進行掃描，從中識別出單詞，是編譯過程中不可缺少的部分。重點：詞法分析的過程；單詞的形式、種類；詞法分析程序的設(shè)計方法3

目錄4.1詞法分析概述4.2詞法分析程序4.3詞法分析程序的自動生成4.4本章小結(jié)44.1詞法分析概述4.1.1詞法分析的功能詞法分析程序的主要功能

輸入源程序輸出單詞符號單詞符號（單詞）：程序語言具有獨立意義的最小語法單位屬性字：單詞的一種機內(nèi)表示(反映單詞的有關(guān)特性).54.1.1詞法分析的功能包括處理說明部分·把單詞的全部屬性都識別出來不必包括處理說明部分·不把單詞的全部屬性都識別出來詞法分析分為兩類64.1.1詞法分析的功能識別單詞從用戶的源程序中把單詞分離出來;生成屬性字把單詞轉(zhuǎn)換成機內(nèi)表示，便于后續(xù)處理。詞法分析又稱為掃描器，任務(wù)有兩個：74.1.2詞法分析的兩種處理結(jié)構(gòu)詞法分析是主程序:詞法分析程序字符串表示的源程序源程序字符字符語法分析是主程序，詞法分析是子程序:源程序字符詞法分析程序單詞回送8符號表語法分析程序4.1.3單詞符號的種類保留字(關(guān)鍵字)常數(shù)標(biāo)識符界限符(特殊符號)程序語言定義的具有固定意義的標(biāo)識符如:Pascal中的begin、end、if、while…。用來表示各種名字.如:變量名、數(shù)組名、過程名等。如:128、0.123、3.14E-2…。如:+、-、*、/、>=、<=、》=、《=等。單詞符號94.1.4詞法分析程序的輸出形式

一般采用二元式

一個語言的單詞符號分為幾類，如何分類、怎樣編碼,是一個技術(shù)性問題，主要取決于處理上的方便。

如：標(biāo)識符分為一類

常數(shù)且按類型（整數(shù)、實數(shù)）分類

保留字可分為一類，也可一字一類

界限符可分為一類，也可一符一類

單詞類別單詞符號的屬性值對于采用一字一類、一符一類，不需再給出單詞的值。10

但若一個類別中含多個單詞符號，還需給出相應(yīng)的值（按某種編碼）例如：對于標(biāo)識符，常把存放它的有關(guān)信息的符號表項的指針作為屬性值。對于常數(shù)，常把存放它的常數(shù)表項的指針作為屬性值。11標(biāo)識符保留字常數(shù)特殊符號4.2詞法分析程序4.2.1詞法分析程序的設(shè)計與實現(xiàn)初始化讀字符是字母?讀標(biāo)識符數(shù)字?取數(shù)字查常量表生成屬性字寫到輸出流是否分析結(jié)束結(jié)束特殊符號?出錯查特殊符號表生成屬性字查保留字表查到?查名字表生成屬性字生成屬性字YYYYNNNNYN124.2.2單詞的識別單詞的文法規(guī)則:<標(biāo)識符>→<字母>|<標(biāo)識符><字母>|<標(biāo)識符><數(shù)字><無符號整數(shù)>→<數(shù)字>|<無符號整數(shù)><數(shù)字><特殊符號>→+|-|*|<=|…單詞的狀態(tài)轉(zhuǎn)換圖如下13標(biāo)識符或保留字

整

數(shù)實數(shù)（無指數(shù)部分）帶指數(shù)的實數(shù)

加號

減號

乘號

除號

等于

小于

小于等于

不等于144.2.3無符號數(shù)的識別文法規(guī)則如下：<無符號數(shù)>→<無符號實數(shù)>|<無符號整數(shù)><無符號實數(shù)>→<無符號整數(shù)>.<數(shù)字串>[E<比例因子>]|<無符號整數(shù)>E<比例因子><比例因子>→<有符號整數(shù)><有符號整數(shù)>→[+|-]<無符號整數(shù)><無符號整數(shù)>→<數(shù)字串><數(shù)字串>→<數(shù)字>{<數(shù)字>}<數(shù)字>→0|1|2…|915

設(shè)無符號數(shù)為：

t=….…E…(整數(shù)部分)(小數(shù)部分)(指數(shù)部分)

令W=…

…1

P=…

e=

則t=W-1

讀無符號數(shù)的程序流程圖見圖4.7164.2.4標(biāo)識符的識別<標(biāo)識符>→<字母>{<字母>|<數(shù)字>}<字母>→A|B|C|…|Z|a|b|…|z<數(shù)字>→0|1|2|…|9保留字是特殊的標(biāo)識符特殊處理事先構(gòu)造保留字表事先構(gòu)造保留字樹規(guī)定保留字在源程序中用分界符括起來

174.3詞法分析程序的自動生成4.3.1基本思想通?？赏ㄟ^兩種途徑來構(gòu)造詞法分析程序：

手工方式和自動生成

1、手工方式根據(jù)對語言中各類單詞的描述或定義，手工構(gòu)造詞法分析程序。如：可根據(jù)文法或狀態(tài)轉(zhuǎn)換圖構(gòu)造相應(yīng)的狀態(tài)矩陣，讀狀態(tài)矩陣同控制程序一起組成了編譯程序的詞法分析程序。

也可根據(jù)文法或狀態(tài)轉(zhuǎn)換圖利用某種語言（匯編或高級語言）直接編寫詞法分析程序。184.3詞法分析程序的自動生成2、自動生成

只要給出某語言各類單詞詞法結(jié)構(gòu)的文法描述（如正則式），以及各類單詞在詞法分析時應(yīng)采取的語義動作，自動生成系統(tǒng)。對上述信息進行加工，即可得到所需的詞法分析程序，例：RWORD、LEXLEX是美國Bell實驗室1975年用C語言研制的一個詞法分析程序的自動生成工具。

LEX源程序LEX編譯系統(tǒng)詞法分析程序194.3.2LEX源程序結(jié)構(gòu)輔助定義轉(zhuǎn)換規(guī)則（識別規(guī)則）用戶子程序（代碼）LEX源程序201、輔助定義在使用LEX語言時，先將高級語言的詞法寫成輔助定義式（類似宏定義）。例：⑴標(biāo)識符letter→A|B…|a|b…|zdigit→0|1|…|9ident→letter(letter|digit)*⑵整常數(shù)integer→digit(digit)*21⑶一般實常數(shù)

sign→+|-|εsigninteger→signintegerdecimal→eger|eger⑷

含指數(shù)部分的實數(shù)

exprel→(decimal|signinteger)E

signinteger⑸

實常數(shù)real→decimal|exprel222.識別規(guī)則（規(guī)定了相應(yīng)詞法分析程序的功能）{}是定義在υ{,,…,}上的正則表達式—詞型{}是語義動作（一個可執(zhí)行的程序段）例：整常數(shù)：digit{val=int(id);求整型值return(16);return(val)}return()子程序;16:單詞的類別編碼23標(biāo)識符:

letter

{if(keyword(id)!=0)return(keyword(id));else{return(15);return(id)}}

keyword()查保留字表，=0未查到243.用戶子程序（輔助函數(shù)部分）

用戶編寫的函數(shù)代碼（可被識別規(guī)則調(diào)用）4.3.3LEX編譯程序工作過程

Ⅰ根據(jù)每條Pi，構(gòu)造相應(yīng)NFAⅡ?qū)⒏鱊FA連成一個完整的NFAⅢ由NFA構(gòu)造狀態(tài)轉(zhuǎn)換矩陣ⅣNFA→DFAⅤ根據(jù)DFA及識別規(guī)則構(gòu)造詞法分析程序254.3.4LEX的實現(xiàn)

經(jīng)LEX編譯后得到詞法分析程序由兩部分組成：

一張狀態(tài)轉(zhuǎn)換矩陣表(DFA)和一個控制程序可看作是如下形式的有限自動機

P1|P2|…|Pn

當(dāng)輸入的單詞與Pj匹配時，就進行相應(yīng)的動作(返回Ai所定義的單詞屬性)Pi例P66264.3.5LEX的使用方式

單獨使用：開發(fā)編輯器、模式識別等

與YACC等結(jié)合使用：生成掃描器和語法分析器27284.4本章小結(jié)1．詞法分析程序的工作是從輸入源代碼中取得單詞，以作為語法分析