詞法分析1上課講義

詞法分析1圖2.1作為子程序的詞法分析器圖2.2詞法分析器進(jìn)行單獨(dú)一遍掃描2023/1/132編譯原理圖2.3并行工作模式2023/1/133編譯原理2、單詞符號(hào)的分類單詞符號(hào)分類：詞法分析程序簡(jiǎn)單地說(shuō)就是讀單詞程序，該程描用高級(jí)語(yǔ)言編寫的源程序，將源程序中由單詞符號(hào)組成的字符串分解出一個(gè)個(gè)單詞來(lái)。因此，單詞符號(hào)是程序語(yǔ)言的基本語(yǔ)法單位，具有確定的語(yǔ)法意義。程序語(yǔ)言的單詞符號(hào)通常可分為下面五種：2023/1/134編譯原理(1)保留字(也稱基本字)：如C語(yǔ)言中的if、else、while和do等，這些字保留了語(yǔ)言所規(guī)定的含義，是編譯程序識(shí)別各類語(yǔ)法成分的依據(jù)。幾乎所有程序語(yǔ)言都限制用戶使用保留字來(lái)作為標(biāo)識(shí)符。(2)

標(biāo)識(shí)符：用來(lái)標(biāo)記常量、數(shù)組、類型、變量、過(guò)程或函數(shù)名等，通常由用戶自己定義。(3)常數(shù)：包括各種類型的常數(shù)，如整型常數(shù)386、實(shí)型常數(shù)0.618、布爾型常數(shù)TRUE等。(4)運(yùn)算符：如“+”、“?”、“*”、“/”、“>”、“<”等。(5)界符：在語(yǔ)言中是作為語(yǔ)法上的分界符號(hào)使用的，如“，”、“；”、“（”、“）”等。2023/1/135編譯原理注意：一個(gè)程序語(yǔ)言的保留字、運(yùn)算符和界符的個(gè)數(shù)是確定的，而標(biāo)識(shí)符或常數(shù)的使用則不限定個(gè)數(shù)。將產(chǎn)生和識(shí)別單詞的規(guī)則稱為模式(patten)。按照某個(gè)模式(規(guī)則)識(shí)別出的元素稱為記號(hào)(token)。單詞(lexeme)一詞是指被識(shí)別出元素自身的值。2023/1/136編譯原理詞法分析程序的輸入是源程序字符串，而輸出是與源程序等價(jià)的單詞符號(hào)序列，并且所輸出的單詞符號(hào)通常表示成如下的二元式：

（單詞種別，單詞自身的值）詞法分析器輸出單詞的形式3、詞法分析器輸出單詞的形式2023/1/137編譯原理(1)單詞種別。單詞種別表示單詞的種類，它是語(yǔ)法分析所需要的信息。一個(gè)語(yǔ)言的單詞符號(hào)如何劃分種類、分為幾類、如何編碼都屬于技術(shù)性問(wèn)題，主要取決于處理上的方便。通常讓每種單詞對(duì)應(yīng)一個(gè)整數(shù)碼，這樣可最大限度地把各個(gè)單詞區(qū)別開來(lái)。對(duì)于保留字，可將其全體視為一種，也可一字一種，采用一字一種的分類方法處理起來(lái)比較方便；標(biāo)識(shí)符一般統(tǒng)歸為一種；常數(shù)可統(tǒng)歸為一種，也可按整型、實(shí)型、布爾型等分為幾種；運(yùn)算符和界符可采用一符一種的分法，也可統(tǒng)歸為一種。2023/1/138編譯原理(2)單詞自身的值。單詞自身的值是編譯中其它階段所需要的信息。對(duì)于單詞符號(hào)來(lái)說(shuō)：如果一個(gè)種別只含有一個(gè)單詞符號(hào)，那么對(duì)于這個(gè)單詞符號(hào)，其種別編碼就完全代表了它自身的值。如果一個(gè)種別含有多個(gè)單詞符號(hào)，那么對(duì)于它的每個(gè)單詞符號(hào)，除了給出種別編碼之外還應(yīng)給出單詞符號(hào)自身的值，以便把同一種類的單詞區(qū)別開來(lái)。注意：標(biāo)識(shí)符自身的值就是標(biāo)識(shí)符自身的字符串，而常數(shù)自身的值是常數(shù)本身的二進(jìn)制數(shù)值。此外，我們也可用指向某類表格中一個(gè)特定項(xiàng)目的指針來(lái)區(qū)分同類中的不同單詞。例如，對(duì)于標(biāo)識(shí)符，可以用它在符號(hào)表的入口指針作為它自身的值；而常數(shù)也可用它在常數(shù)表的入口指針作為它自身的值。2023/1/139編譯原理二、模式的形式化描述-正規(guī)式與正規(guī)集1、字符串與語(yǔ)言從詞法分析的角度看，程序設(shè)計(jì)語(yǔ)言是由記號(hào)組成的集合，每個(gè)記號(hào)又是由若干字母按照一定規(guī)則組成的字符串。2023/1/1310編譯原理定義2.1語(yǔ)言L是有限字母表∑上有限長(zhǎng)度字符串的集合。定義2.1明確指出，語(yǔ)言是一個(gè)集合，集合中的元素是字符串，并且強(qiáng)調(diào)了兩個(gè)有限:①字母表是有限的，即字母表中元素是有限多個(gè)；②字符串的長(zhǎng)度是有限的，即字符串中字符個(gè)數(shù)是有限多個(gè)。這是由于計(jì)算機(jī)所能表示的字符個(gè)數(shù)和字符串的長(zhǎng)度都是有限的。2023/1/1311編譯原理字符串的基本概念：2023/1/1312編譯原理字符串集合上的基本運(yùn)算2023/1/1313編譯原理2、正規(guī)式與正規(guī)集定義2.2令Σ是一個(gè)有限字母表，則Σ上的正規(guī)式及其表示的集合遞歸定義如下:①ε是正規(guī)式，它表示集合L(ε)=ε；②若a是Σ上的字符，則a是正規(guī)式，它表示集合L(a)=；③若正規(guī)式r和s分別表示集合L(r)和L(s)，則(a)r|s是正規(guī)式，表示集合L(r)∪L(s)；(b)rs是正規(guī)式，表示集合L(r)L(s)；(c)r*是正規(guī)式，表示集合(L(r))*；(d)(r)是正規(guī)式，表示的集合仍然是L(r)?？捎谜?guī)式描述的語(yǔ)言稱為正規(guī)語(yǔ)言或正規(guī)集。2023/1/1314編譯原理定義2.2中①和②規(guī)定了正規(guī)式的基本操作數(shù)或基本正規(guī)式。定義2.2的③給出了正規(guī)式上的三種運(yùn)算:(a)或運(yùn)算、(b)連接運(yùn)算和(c)閉包運(yùn)算。對(duì)于由多個(gè)操作數(shù)和多個(gè)操作符組成的正規(guī)式，可以利用(d)所給的括號(hào)規(guī)定運(yùn)算的先后次序。如果對(duì)或、連接和閉包運(yùn)算進(jìn)行如下約定:①三種運(yùn)算均具有左結(jié)合性質(zhì)；②運(yùn)算的優(yōu)先級(jí)從高到低順序排列為:閉包運(yùn)算、連接運(yùn)算、或運(yùn)算。則正規(guī)式中不必要的括號(hào)可以被省略。例如，(a)|((b)*(c))可以簡(jiǎn)化成a|b*c。2023/1/1315編譯原理正規(guī)集是一個(gè)集合，而正規(guī)式是表示正規(guī)集的一種方法。不同正規(guī)式也可以表示同一個(gè)正規(guī)集，即正規(guī)式與正規(guī)集之間是多對(duì)一的關(guān)系。定義2.3若正規(guī)式P和Q表示了同一個(gè)正規(guī)集，則稱P和Q是等價(jià)的，記為P=Q。正規(guī)式之間的一些恒等運(yùn)算，被稱為正規(guī)式的代數(shù)性質(zhì)。表2.6給出了正規(guī)式的若干代數(shù)性質(zhì)。利用這些性質(zhì)，可以對(duì)復(fù)雜的正規(guī)式進(jìn)行化簡(jiǎn)，使得可以用最簡(jiǎn)單形式的正規(guī)式表示一個(gè)集合。而簡(jiǎn)單的正規(guī)式意味著其所對(duì)應(yīng)的識(shí)別器的構(gòu)造也是簡(jiǎn)單的。2023/1/1316編譯原理正規(guī)式的代數(shù)性質(zhì)2023/1/1317編譯原理3、記號(hào)的說(shuō)明用自然語(yǔ)言對(duì)模式進(jìn)行了非形式化的描述，例如標(biāo)識(shí)符模式的非形式化描述是“以字母打頭的字母數(shù)字串”。這一描述很不精確，存在一些問(wèn)題，如哪些符號(hào)是字母，哪些符號(hào)是數(shù)字，字母數(shù)字串的長(zhǎng)度可以是多少等等。正規(guī)式是嚴(yán)格的數(shù)學(xué)表達(dá)式，采用正規(guī)式來(lái)描述模式，解決了精確描述模式的問(wèn)題。另外，從詞法分析器的角度上看程序設(shè)計(jì)語(yǔ)言，用正規(guī)式說(shuō)明的記號(hào)是一個(gè)正規(guī)集。用正規(guī)式說(shuō)明記號(hào)的公式為：記號(hào)=正規(guī)式，可以讀作為“(左邊)記號(hào)定義為(右邊)正規(guī)式”，或者“記號(hào)是正規(guī)式”。通常，在不引起混淆的情況下，也把說(shuō)明記號(hào)的公式簡(jiǎn)稱為正規(guī)式，或者規(guī)則。2023/1/1318編譯原理例2.5

表2.1中的記號(hào)relation、id和num分別是Pascal的關(guān)系運(yùn)算符、標(biāo)識(shí)符和無(wú)符號(hào)數(shù)，它們的正規(guī)式表示如下所示：relation=<|<=|<>|>|>=|=id=(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|0|1|2|3|4|5|6|7|8|9)*2023/1/1319編譯原理num=(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(ε|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)(ε|E(+|-|ε)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)上述正規(guī)式給出了標(biāo)識(shí)符的精確定義，用自然語(yǔ)言可以描述為“字母是英文26個(gè)字母大小寫中任何一個(gè)，數(shù)字是十進(jìn)制阿拉伯?dāng)?shù)字中的任何一個(gè)，標(biāo)識(shí)符是以字母打頭的、其后可跟隨0個(gè)或若干個(gè)字母或數(shù)字的字符串”。2023/1/1320編譯原理a．簡(jiǎn)化正規(guī)式描述為了簡(jiǎn)化正規(guī)式的描述，通?？梢圆捎萌缦碌膸追N正規(guī)式的縮寫形式。(1)正閉包。若r是表示L(r)的正規(guī)式，則r+是表示(L(r))+的正規(guī)式，且下述等式成立:r+=rr*=r*r，r*=r+|ε+與*具有相同的運(yùn)算優(yōu)先級(jí)和結(jié)合性。(2)可缺省。若r是正規(guī)式，則(r)?是表示L(r)∪ε的正規(guī)式，且下述等式成立:r?=r|ε2023/1/1321編譯原理(3)字符組。字符組是或關(guān)系的縮寫形式，它把所有存在或關(guān)系的字符集中在[]里面。其中的字符可以有如下兩種書寫方式:枚舉方式:如[abc]，它等價(jià)于a|b|c

分段方式:如[0-9a-z]，它等價(jià)于：[0123456789abcdefghijklmnopqrstuvwxyz]2023/1/1322編譯原理(4)非字符組。若[r]是一個(gè)字符組形式的正規(guī)式，則[^r]是表示∑L(r)的正規(guī)式。例如，若∑=，則L([^abc])={d,e,f,g}。(5)串。若r是字符連接運(yùn)算的正規(guī)式，則串"r"與r等價(jià)，即r="r"。特別地，ε="",?a="a"。引入串的表示可以避免與正規(guī)式中運(yùn)算符的沖突。例如："a|b"=a"|"b≠a|b。2023/1/1323編譯原理b．引入輔助定義式引入輔助定義式的主要目的是為較復(fù)雜、但需要重復(fù)書寫的正規(guī)式命名，并在定義式之后的引用中，用名字代替相應(yīng)的正規(guī)式。所以，輔助定義式實(shí)質(zhì)上仍然是正規(guī)式，唯一的區(qū)別是正規(guī)式與外部模式匹配，而輔助定義式不與任何模式匹配。2023/1/1324編譯原理例2.6引入正規(guī)式的縮寫形式和輔助定義式后，id和num的正規(guī)式可重寫如下。

char =[a-zA-Z]digit =[0-9]digits =digit+optional_fraction =(.digits)?optional_exponent =(E(+|)?digits)?id =char(char|digit)*num =digitsoptional_fra