編譯器（解釋器）編寫指南-編寫編譯器（解釋器）的工具-LEX

2019-11-18 18:37:03

字體：大中小

來源：轉載

供稿：網友

關鍵字：編譯器, 解釋器, LEX, YACC, 編譯原理, 正則表達式, Pascal

預備知識：編譯原理，正則表達式，Pascal

本文并不希望深入透徹的講解編譯原理，而是講解如何利用工具（生成編譯器的編譯器）去編寫編譯器。如果你完全不知道編譯什么東西，那么請看懂了編譯原理，在看此文，本文不是為初學者準備的。

一、什么是編譯器（解釋器）
編譯器是將一種計算機語言翻譯為另一種計算機語言的程序。編譯器將源程序(source language)
編寫的程序作為輸入，翻譯產生用目標語言(target language)編寫的等價程序。源程序一般為高級語言(high-level language)，如Pascal 或Delphi，而目標語言則是匯編語言或目標機器的目標代碼(object code)，有時也稱作機器代碼（machine code）
源程序→ 編譯器→ 目標程序
解釋器也是同編譯器一樣的一種語言翻譯程序。它與編譯器的不同之處在于：它立即執行源程序而不是生成目標代碼。從原理上講，任何程序設計語言都可以被解釋或被編譯。

(1) 掃描程序（scanner）
由掃描程序(Scanner)閱讀源程序（通常以字符流的形式表示），進行詞法分析(Lexical analysis)，它將源程序翻譯成單詞ID(Token)，放入單詞ID(Token)表中。在此過程中，掃描程序會進行簡單的拼寫檢查。

單詞ID(Token)：
一個Token可以有若干種類型，典型的有：關鍵字(keyWord)，例如 if 和 while；標識符(identifier)是由用戶定義的變量名，過程名等，它們通常由字母和數字組成并由一個字母開頭；特殊符號(special symbol)如算術符號+和*、一些多字符符號，如 >= 和<>。TokenType 為枚舉數據類型。實際上就是整數值，每一個數值代表一種單詞ID類型。
TTokenType = (ttNone, ttStrVal, ttIntVal, ttFloatVal,
    //ttNAME 就是標識符 Identifier 或關鍵字
    ttNAME,
    ttSWITCH,
    ttVAR, ttCONST, ttTYPE, ttRECORD, ttARRAY, ttDOT, ttDOTDOT, ttOF,
    ttTRY, ttEXCEPT, ttRAISE, ttFINALLY, ttON, ttREAD, ttWRITE, ttPROPERTY,
    ttPROCEDURE, ttFUNCTION, ttCONSTRUCTOR, ttDESTRUCTOR, ttCLASS, ttNIL, ttIS,
    ttAS,
    ttVIRTUAL, ttOVERRIDE, ttREINTRODUCE, ttINHERITED, ttABSTRACT,
    ttEXTERNAL, ttFORWARD, ttIN,
    ttBEGIN, ttEND, ttBREAK, ttCONTINUE, ttEXIT,
    ttIF, ttTHEN, ttELSE, ttWHILE, ttREPEAT, ttUNTIL, ttFOR, ttTO, ttDOWNTO, ttDO,
    ttCASE,
    ttTRUE, ttFALSE, ttAND, ttOR, ttXOR, ttDIV, ttMOD, ttNOT, ttPLUS, ttMINUS,
    ttTIMES, ttDIVIDE,
    ttEQ, ttNOTEQ, ttGTR, ttGTREQ, ttLESS, ttLESSEQ, ttSEMI, ttCOMMA, ttCOLON,
    ttASSIGN,
    ttBLEFT, ttBRIGHT, ttALEFT, ttARIGHT, ttCRIGHT,
    ttDEFAULT,

    // Tokens for compatibility to Delphi
    ttPRIVATE, ttPROTECTED, ttPUBLIC, ttPUBLISHED,
    ttREGISTER, ttPASCAL, ttCDECL, ttSTDCALL, ttFASTCALL);

TTokenTypes = set of TTokenType;

為了表示 Token 的內容，一般我們這樣定義Token：
TToken = Record
TokenType: TTokenType;
TokenValue: Variant;
end;

TP LEX
TP Lex 是詞法分析(Lexical analysis)掃描器源程序的生成器，它用于創建Pascal(TurboPascal, Delohi)掃描器子過程。
TP Lex 分析 LEX 文件（默認擴展名為.L），產生詞法分析(Lexical analysis)掃描器過程，輸出pascal源程序文件。如果 LEX 文件在分析過程發現錯誤，錯誤信息將會被寫入相應的列表文件（擴展名為.lst）。
創建的 pascal 源文件程序將包含詞法分析(Lexical analysis)掃描器過程：yylex。
function yylex : Integer;
你應該在你的主程序中調用該過程進行詞法分析。每調用一次，yylex 的返回值為當前分析的Token類型值。當文件結束時，yylex 的返回值為0。

yylex 過程的代碼模板在 yylex.cod 文件中。TP Lex 需要該文件構建生成 pascal 源程序文件。該文件必須在當前目錄或TP LEX所在目錄下。另外生成好的源程序需要 LexLib.pas 文件進行編譯。

用法：
lex [options] lex-file[.l] [output-file[.pas]]

Options(參數)
-------
-v "詳盡(Verbose):" 在該參數下，Lex 在生成詞法分析器的同時，將生成一個可讀的說明文件，擴展名`.lst'.
-o "優化(Optimize):" Lex 將優化 DFA 表，產生一個最小的 DFA.

如何編寫 LEX 文件(.L)
LEX 文件(.L)分為三個部分，每個部分之間用“%%”隔開：
定義部分(definitions)
%%
規則部分(rules)
%%
輔助過程部分(auxiliary procedures)

三個部分可以都是空的也沒有關系，以行為單位作為語句的分隔符。

定義部分(definitions)
定義部分出現在第1個雙百分號之前。定義部分(definitions)可以包含以下的元素：
- 正則表達式一般定義格式：
定義的表達式名稱(name) 替換的結果(substitution)

正則表達式的名字也得在該部分定義。這個名字的定義寫在另一行的第1列，且其后（后面有一個或多個空格）是它所表示的正則表達式。定義的名稱(name)必須是一個合法的標識符（第一位必須是字母，第二位可以是字母或數字）
替換的結果(substitution)是一個LEX正則表達式，你也可以在正則表達式中引用前面定義好的表達式名稱，只要將該名稱用花括號("{}")擴起即可。例如，帶符號數字的定義：
Number [0-9]+
signedNumber ("+"|"-"）? {Number}

- 開始(start)狀態按照如下的格式書寫:
%start name ...
這用來指定規則的啟動條件（詳見規則部分）。%start 關鍵字可以被簡寫為 %s 或 %S.

- “%{”與“%}”對
插入在 “%{”與“%}”對中間的是函數外部的任意Pascal源代碼（請注意這些字符的順序）。

規則部分(rules)
它們由一連串帶有Pascal代碼的正則表達式組成；當匹配相對應的正則表達式時，后面的Pascal代碼(動作)就會被執行。規則的格式如下:
正則表達式(expression)      語句(statement);
注意：語句(statement)必須是單獨的一個Pascal語句，最后以分號結尾（如果有多個語句使用Begin...End）。語句(statement)可以分成多行書寫，不過后續行必須首先至少留一個空格或tab，用來指示該行是屬于上一行的。使用“|”表示該表達式執行的動作和下一個表達式執行的動作(語句)一樣。例如，Pascal的注釋：
"(*"            |
"{"             begin
                      repeat
                            c := get_char;
                            case c of
                               '}' : ;
                               '*' : begin
                                c := get_char;
                                if c=')' then exit else unget_char(c)
                              end;
                              #0 : begin
                                     commenteof;
                                     exit;
                                   end;
                             end;
                         until false
                     end;