基于LEX的C語言詞法分析器

1、基于LEX的C語言詞法分析器一、LEX語法簡介（一）文件結構Lex文件結構簡單，分為三個部分：dclarations/ 聲明%translation rules/轉(zhuǎn)換規(guī)則%auxiliary procedures/功能函數(shù)聲明段包括變量的聲明、符號常量的聲明和正則表達式聲明。希望出現(xiàn)在目標C源碼中的代碼，用%擴在一起。比如：%#include <stdio.h>int lineno = 1;%正則表達式聲明的格式為“命名 表達式”，比如：digit 0-9+alphabet A-Za-z+whitespace t+功能函數(shù)即為正常的C語言代碼，遵守C語言代碼格式即可。（二）Lex特

2、性簡介1Lex依次嘗試每一個規(guī)則，盡可能地匹配最長的輸入流。2如果有一些內(nèi)容根本不匹配任何規(guī)則，那么Lex將把它拷貝到標準輸出。二、正則表達式簡介在編寫處理字符串的程序或網(wǎng)頁時，經(jīng)常會有查找符合某些復雜規(guī)則的字符串的需要。正則表達式就是用于描述這些規(guī)則的工具。換句話說，正則表達式就是記錄文本規(guī)則的代碼。在這里，只用到了字符轉(zhuǎn)義、重復、字符類、反義、貪婪與懶惰等較為基礎的語法。以下就簡單對涉及到的語法進行介紹。（一）字符轉(zhuǎn)義例如，.*在正則表達式中表示匹配所有，因此若要匹配.或*，則需要對其進行轉(zhuǎn)義，即.和*。（二）重復在對數(shù)字和標識符等進行匹配時，字符位數(shù)不止一位，但遵守相同的規(guī)則，因此使用“

3、重復”進行匹配。例如，對數(shù)字進行匹配：0-9+，“+”表示至少重復一次，即數(shù)字長度至少為1。例如，對標識符進行匹配，由于C語言標識符必須以下劃線或字母開頭，所以規(guī)則為：_|A-Za-z+(_|A-Za-z|0-9)*?！癬|A-Za-z+”表示必須以下劃線或字母開頭，“(_|A-Za-z|0-9)*”表示之后可以跟字母數(shù)字下劃線，但是也可以不跟，這就是“+”和“*”所表示的“重復”的不同之處。（三）字符類與反義對沒有預定義元字符的字符集合，需要在方括號里將其列出，例如，aeiou就是對任何一個英文元音字母的匹配，同理，0-9代表的含義與元字符d完全一致，都是對一位數(shù)字進行的匹配。有時需要查找不

4、屬于某個能簡單定義的字符類的字符。比如想查找除了數(shù)字以外，其它任意字符都行的情況，這時需要用到反義：對于元字符，其反義即為其大寫：D，匹配非數(shù)字的字符。更為普遍的表達方式如下：aeiou，匹配除了aeiou這幾個字母以外的所有字符。（四）貪婪與懶惰與Lex對規(guī)則的處理類似，正則表達式也會在匹配整個表達式的前提下，匹配盡可能多的字符，這就是“貪婪”。有時，需要匹配盡可能少的字符，就是“懶惰”匹配，具體的例子如下：a.*?b，由于.*后加了?，表示“懶惰”匹配，因此會匹配最短的，以a開始，以b結束的字符。例如字符串a(chǎn)abab，“貪婪”匹配的結果是aabab，而“懶惰”匹配的結果則是aab。三、詞法

5、分類識別這里，將源程序中的字符分為七類。由于字符串對于詞法分析以及后續(xù)的語法分析的意義不大，因此，這里將其單獨列為一類；由于頭文件的聲明中會出現(xiàn)“<”“>”“”等分隔符，尤其是“<”和“>”，會與運算符中的大于小于號產(chǎn)生沖突，因此這里把頭文件也單獨列為一類。（一）保留字C語言共有32個保留字，如圖：（二）標識符C語言標識符的要求是， 必須以下劃線或者字母開頭，之后可以跟字母、數(shù)字、下劃線。（三）常數(shù)由于常數(shù)的表達方式較多，這里只是代表性地選取了幾種方式進行識別。（四）操作符C語言操作符包括一元操作符、二元操作符和三元操作符。（五）字符串這里的字符串是指包圍在單引號或雙引

6、號內(nèi)的字符串。（六）分隔符這里選取了以下經(jīng)常見到的分隔符：（七）頭文件頭文件的格式有一下兩種：四、詞法識別分類規(guī)則（一）常數(shù)的識別根據(jù)上述對常數(shù)識別的需求，構造出了如下正則表達式：0-9+.0-9*|0-9+.0-9*(e|E+|-0-9+)|0x|X(0-9abcdefABCDEF+)這里，為了美觀，以“|”為分隔符，對表達式進行了換行處理，每一行對應一個常數(shù)類別。第一行，表示對整數(shù)和浮點數(shù)進行匹配；第二行，先對整數(shù)或浮點數(shù)進行匹配，之后匹配e或E，最后匹配一個整數(shù)，即123.456e+789的形式，即科學計數(shù)法；第三行，先匹配數(shù)字0，之后匹配字母x或X，最后匹配0-9及a-f或A-F的字符

7、，即0x123abc的形式，即16進制表示法。（二）保留字的識別C語言中有32個保留字，且區(qū)分大小寫，因此，這里構造如下正則表達式進行匹配：auto|break|case|char|const|continue|default|do|double|else|enum|extern|float|for|goto|if|int|long|register|return|short|signed|sizeof|static|struct|switch|typedef|union|unsigned|void|volatile|while可見，只需簡單的將各個保留字通過“|”符號進行連接，即可實現(xiàn)對所有

8、保留字的識別。（三）分隔符的識別由于分隔符中存在與正則表達式中元字符相沖突的字符，如“.”，“”等，因此需要對這些產(chǎn)生沖突的符號進行轉(zhuǎn)義，構造如下正則表達式：,|;|(|)|'|"|<|>（四）標識符的識別根據(jù)上述的C語言標識符的要求，構造如下正則表達式：_|A-Za-z+(_|A-Za-z|0-9)*此處涉及正則表達式語法較為簡單，不再贅述。（五）操作符的識別由于操作符中，存在大量運算符號與正則表達式的元字符沖突，因此，根據(jù)C語言中的三種操作符，構造以下正則表達式：>>=|<<=|+|-|=|>=|<=|!=|&&am

9、p;|<<|>>|+=|-=|*=|/=|%=|&=|=|=|+|-|*|/|%|>|<|!|&|=可以看到表達式中含有大量轉(zhuǎn)義字符，使得原本容易識別的C語言操作符變得難以分辨，但根據(jù)“|”連接符的指示，單個單個的分析，還是很容易明白的。（六）其他字符的識別對于空白、換行、注釋、頭文件等的識別，規(guī)則較為簡單，這里不再一一舉出。五、詞法識別分類順序由于Lex對正則表達式的支持并不完全，因此存在不同表達式匹配同一字符串的現(xiàn)象。這里，為了減少這種現(xiàn)象的發(fā)生，降低出錯率，對規(guī)則的優(yōu)先級進行了調(diào)整，以更好的滿足設計需求。這里從兩方面進行說明，一是標識符

10、和保留字的識別順序，二是一、二、三元操作符的識別順序。（一）標識符和保留字的識別順序由于標識符的識別規(guī)則會同時把保留字當做標識符進行匹配，從而產(chǎn)生錯誤，因此，需要調(diào)換這兩條規(guī)則的匹配優(yōu)先級，調(diào)整的結果如圖所示：這樣就能保證，Lex在進行詞法分析時，優(yōu)先將滿足保留字匹配規(guī)則的字符串匹配出來，從而避免誤判。（二）一、二、三元操作符的識別順序由于C語言中存在多元操作符，因此在對操作符進行匹配的時候，就要考慮到將其完整匹配，而不是將一個多元操作符分為多個一元操作符進行匹配。這里，就需要對正則表達式內(nèi)匹配規(guī)則的順序進行一個調(diào)整，即對位數(shù)多的操作符優(yōu)先進行匹配，具體的做法就是，將其匹配規(guī)則提前，如下所示：

11、>>=|<<=|+|-|=|>=|<=|!=|&&|<<|>>|+=|-=|*=|/=|%=|&=|=|=|+|-|*|/|%|>|<|!|&|=這樣在對操作符進行匹配時，就能夠正確進行匹配，不產(chǎn)生錯誤和沖突。六、測試代碼為了檢驗該詞法分析器是否能實現(xiàn)詞法分析，根據(jù)功能需求，設計了如下測試代碼ori.c：對頭文件、兩種注釋方式、四種類型的數(shù)字、一元和三元運算符、字符串、分隔符、標識符、保留字在詞法上進行了相關的構造。由于未涉及語義分析，因此，為了便于做詞法分析，代碼加入了各種類型的語句，但只

12、是形式，不能正常運行。七、結果分析程序運行命令：其中l(wèi)ex.l即為編寫的Lex源代碼；是上一步flex對lex.l源代碼進行處理，生成的文件；用gcc對進行編譯，生成可執(zhí)行二進制文件flex；運行flex，將對ori.c文件進行詞法分析。以下為程序分析結果：可以看出，該詞法分析器能夠正常運行，對程序的詞法進行了準確率較高的識別。但是，仍然存在一些問題，比如，對于負數(shù)無法進行識別，程序會將負號識別為操作符，這一錯誤無法通過調(diào)整優(yōu)先級進行改正，需要對正則表達式進行進一步改進。由于減號和負號的適用場合較為復雜，之前嘗試著使用正則表達式的“負向零寬斷言”語法進行匹配，但發(fā)現(xiàn)Lex無法識別該語法，導致無法運行，目前暫時還未