詞法分析1上課講義

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

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

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

表2.1中的記號relation、id和num分別是Pascal的關系運算符、標識符和無符號數(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ī)式給出了標識符的精確定義，用自然語言可以描述為“字母是英文26個字母大小寫中任何一個，數(shù)字是十進制阿拉伯數(shù)字中的任何一個，標識符是以字母打頭的、其后可跟隨0個或若干個字母或數(shù)字的字符串”。2023/1/1320編譯原理a．簡化正規(guī)式描述為了簡化正規(guī)式的描述，通常可以采用如下的幾種正規(guī)式的縮寫形式。(1)正閉包。若r是表示L(r)的正規(guī)式，則r+是表示(L(r))+的正規(guī)式，且下述等式成立:r+=rr*=r*r，r*=r+|ε+與*具有相同的運算優(yōu)先級和結(jié)合性。(2)可缺省。若r是正規(guī)式，則(r)?是表示L(r)∪ε的正規(guī)式，且下述等式成立:r?=r|ε2023/1/1321編譯原理(3)字符組。字符組是或關系的縮寫形式，它把所有存在或關系的字符集中在[]里面。其中的字符可以有如下兩種書寫方式:枚舉方式:如[abc]，它等價于a|b|c

分段方式:如[0-9a-z]，它等價于：[0123456789abcdefghijklmnopqrstuvwxyz]2023/1/1322編譯原理(4)非字符組。若[r]是一個字符組形式的正規(guī)式，則[^r]是表示∑L(r)的正規(guī)式。例如，若∑=，則L([^abc])={d,e,f,g}。(5)串。若r是字符連接運算的正規(guī)式，則串"r"與r等價，即r="r"。特別地，ε="",?a="a"。引入串的表示可以避免與正規(guī)式中運算符的沖突。例如："a|b"=a"|"b≠a|b。2023/1/1323編譯原理b．引入輔助定義式引入輔助定義式的主要目的是為較復雜、但需要重復書寫的正規(guī)式命名，并在定義式之后的引用中，用名字代替相應的正規(guī)式。所以，輔助定義式實質(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