編譯器構造/詞法分析

華夏公益教科書使用者已提名此頁面進行清理。
您可以幫助使其變得更好。請檢視任何相關討論。

詞法分析

詞法分析是將單個字元流（通常排列成行）分析成一系列詞法標記（標記化，例如組成原始碼的“單詞”和標點符號）的過程，以饋送到解析器。大致相當於將用自然語言（如英語）編寫的普通文字拆分成單詞和標點符號序列。詞法分析通常使用 lex、flex 和 jflex 等工具完成。

嚴格來說，標記化可能由解析器處理。在實踐中，我們傾向於使用標記化是因為它使解析器更簡單，並且將其與用於原始碼的字元編碼解耦。

例如，給定輸入字串

     integer aardvark := 2, b;

標記器可能會輸出以下標記

keyword integer
word aardvark
assignment operator
integer 2
comma
word b
semi_colon

什麼是詞法單元

在計算中，詞法單元是一個分類的文字塊，通常由稱為詞素的不可分割的字元組成。詞法分析器最初讀取詞素並根據其功能對其進行分類，從而賦予其意義。這種賦予意義的過程稱為標記化。詞法單元可以看起來像任何東西：英語、亂碼符號、任何東西；它只需要是結構化文字的有用部分。

考慮以下表格

詞素	詞法單元
sum	IDENT
=	ASSIGN_OP
3	NUMBER
+	ADD_OP
2	NUMBER
;	SEMICOLON

詞法單元通常由正則表示式定義，詞法分析器（如 lex）可以理解這些正則表示式。詞法分析器讀取詞素流並將其分類為詞法單元。這稱為“標記化”。如果詞法分析器發現無效詞法單元，它將報告錯誤。

標記化之後是解析。從那裡，解釋後的資料可以載入到資料結構中，用於一般用途、解釋或編譯。

考慮描述計算的文字："46 - number_of(cows);”。這裡的詞素可能是：“46”、“-”、“number_of”、“(”、“cows”、“)” 和“；”。詞法分析器將詞素 4 和 6 表示為“數字”，將 - 表示為字元，並將“number_of” 表示為單獨的詞法單元。即使在某些語言（如 C）中，詞素“；”也具有一些特殊的意義。

空格詞素有時會被語法分析器忽略。詞法單元不需要有效，才能被識別為詞法單元。“cows” 對語言來說可能是無意義的，“number_of” 可能是無意義的。但它們仍然是詞法單元，在這個例子中。

有限狀態自動機

我們首先研究被稱為有限狀態自動機，簡稱 FSA 的東西。FSA 通常用於進行詞法分析。

FSA 由狀態、起始狀態、接受狀態和轉換表組成。自動機讀取輸入符號並相應地移動狀態。如果 FSA 在讀取完輸入字串直到其結束之後到達接受狀態，則該字串被稱為被接受或被識別。一組被識別的字串被稱為 FSA 識別的語言。

假設這種語言中的每個字串都以“ab”開頭，並以一個或多個“c”結尾。使用 state 類，可以這樣編寫

State
  s0 = new State (),
  s1 = new State (),
  s2 = new State (),
  s3 = new State ();
		
s0.setTransition ('a', s1);
s1.setTransition ('b', s2);
s2.setTransition ('c', s3);
s3.setTransition ('c', s3);

State r[] = s0.move (inputString);
if (Arrays.asList (r).contains (s3))
  System.out.println ("the input string is accepted.");
else
  System.out.println ("the input string is not accepted.");

假設輸入字串為“abccc”。那麼自動機移動方式為：s0 -> s1 -> s2 -> s3 -> s3 -> s3。

簡單的手寫掃描

在本節中，我們將為用 Object Pascal 實現的簡單語言建立一個簡單的面向物件的掃描器/詞法分析器。考慮以下 EBNF

program     ::= { instruction }
instruction ::= "print" expr | "var" IDENTIFIER ":=" expr
expr        ::= simple-expr [ ("<" | "<>" ) simple-expr ]
simple-expr ::= factor { ( "+" | "-" ) factor }
factor      ::= INTEGER | IDENTIFIER

在哪裡

INTEGER    = [0-9]+
IDENTIFIER = [A-Za-z_][A-Za-z0-9_]*

從上面的 EBNF 中，我們即將識別的詞法單元是：IDENTIFIER、INTEGER、關鍵字“print”、關鍵字“var”、:=、+、-、<、<>、EOF 和未知詞法單元。所選詞法單元旨在簡明扼要，並能夠識別所有型別的詞法單元的詞素：確切的單個字元（+、-、<、EOF 和未知）、確切的多個字元（print、var、:= 和 <>）、無限多個（IDENTIFIER、INTEGER 和未知）、重疊字首（< 和 <>）和重疊整體（IDENTIFIER 和關鍵字）。此處識別符號和關鍵字不區分大小寫。請注意，某些詞素被歸類為多種型別的詞素。

詞法單元類

TToken = class
protected
  FLine, FCol: LongWord;
public
  constructor Create(const ALine, ACol: LongWord);
  destructor Destroy; override;
end;

詞法單元的基類只是一個包含其宣告所在的行號和列號的物件。從這個基類，具有確切詞素的詞法單元（單個字元或多個字元）可以實現為直接子類。

TEOFToken = class(TToken)
end;

TPlusToken = class(TToken)
end;

TMinusToken = class(TToken)
end;

TAssignToken = class(TToken)
end;

TLessToken = class(TToken)
end;

TNotEqualToken = class(TToken)
end;

TPrintToken = class(TToken)
end;

TVarToken = class(TToken)
end;

TEOFToken = class(TToken)
end;

接下來，我們需要為具有可變詞素的詞法單元建立子類

TVariadicToken = class(TToken)
protected
  FLexeme: String;
public
  constructor Create(const ALine, ACol: LongWord; const ALexeme: String);
  destructor Destroy; override;
end;

與基詞法單元類唯一的區別在於 lexeme 屬性，因為它可能具有無限多種形式。從這裡，我們建立子類，用於詞素為無限多個的詞法單元

TUnknownToken = class(TVariadicToken)
end;

TIdentifierToken = class(TVariadicToken)
end;

TIntegerToken = class(TVariadicToken)
end;

關於詞法單元就這些了，讓我們繼續進行詞法分析器。

詞法分析器類

TLexer = class
private
  FLine: LongWord;
  FCol: LongWord;
  FStream: TStream;
  FCurrentToken: TToken;
  FLastChar: Char;
  function GetChar: Char;
public
  constructor Create(AStream: TStream);
  destructor Destroy; override;
  procedure NextToken;
  property CurrentToken: TToken read FCurrentToken;
end;

詞法分析器由其在原始碼中的位置（行和列）、表示原始碼的流、當前（或最後識別/形成）的詞法單元和最後讀取的字元組成。為了封裝原始碼中的移動，從流中讀取字元在 GetChar 方法中實現。儘管它的可能很簡單，但正如我們很快將看到的那樣，實現可能會很複雜。GetChar 被公共方法 NextToken 使用，NextToken 的作用是將詞法分析器移動提前 1 個詞法單元。讓我們繼續進行 GetChar 的實現

function TLexer.GetChar: Char;
begin
  try
    FLastChar := Chr(FStream.ReadByte);
    Inc(FCol);
    // Handles 3 types of line endings
    if FLastChar in [#13, #10] then begin
      FCol := 0;
      Inc(FLine);
      // CR met, probably CRLF
      if FLastChar = #13 then begin
        FLastChar := Chr(FStream.ReadByte);
        // Not CRLF, but CR only, move backward 1 position
        if FLastChar <> #10 then
          FStream.Seek(-1,soFromCurrent);
      end;
      // Always returns as LF for consistency
      FLastChar := #10;
    end;
  except // Exception? Returns EOF
    FLastChar := #26;
  end;
  GetChar := FLastChar;
end;

如前所述，GetChar 的工作並不像它的名字那麼簡單。首先，它必須從輸入流中讀取一個字元並增加詞法分析器的列位置。然後它必須檢查此字元是否為可能的換行符之一（我們的詞法分析器能夠處理 CR-、LF- 和 CRLF- 樣式的換行符）。接下來是我們的詞法分析器的核心，NextToken

procedure TLexer.NextToken;
var
  StartLine,StartCol: LongWord;

  function GetNumber: TIntegerToken;
  var
    NumLex: String;
  begin
    NumLex := '';
    repeat
      NumLex := NumLex + FLastChar;
      FLastChar := GetChar;
    until not (FLastChar in ['0' .. '9']);
    Result := TIntegerToken.Create(StartLine, StartCol, NumLex);
  end;
  
  function GetIdentifierOrKeyword: TVariadicToken;
  var
    IdLex: String;
  begin
    IdLex := '';
    repeat
      IdLex := IdLex + FLastChar;
      // This is how we handle case-insensitiveness
      FLastChar := LowerCase(GetChar);
    until not (FLastChar in ['a' .. 'z','0' .. '9','_']);
    // Need to check for keywords
    case IdLex of
      'print' : Result := TPrintToken.Create(StartLine,StartCol);
      'var'   : Result := TVarToken.Create(StartLine,StartCol);
      otherwise Result := TIdentifier.Create(StartLine,StartCol,IdLex);
    end;
  end;

begin
  // Eat whitespaces
  while FLastChar in [#32,#9,#13,#10] do
    FLastChar := GetChar;
  // Save first token position, since GetChar would change FLine and FCol
  StartLine := FLine;
  StartCol := FCol;
  if FLastChar = #26 then
    FCurrentToken := TEOFToken.Create(StartLine, StartCol)
  else
    case LowerCase(FLastChar) of
      // Exact single character
      '+': begin
        FCurrentToken := TPlusToken.Create(StartLine, StartCol);
        FLastChar := GetChar;
      end;
      '-': begin
        FCurrentToken := TMinusToken.Create(StartLine, StartCol);
        FLastChar := GetChar;
      end;
      // Exact multiple character
      ':': begin
        FLastChar := GetChar;
        if FLastChar = '=' then
          FCurrentToken := TAssignToken.Create(StartLine, StartCol)
        // ':' alone has no meaning in this language, therefore it's invalid
        else
          FCurrentToken := TUnknownToken.Create(StartLine, StartCol);
      end;
      // Overlapping prefix
      '<': begin
        FLastChar := GetChar;
        // '<>'
        if FLastChar = '>' then
          FCurrentToken := TNotEqualToken.Create(StartLine, StartCol)
        // '<'
        else
          FCurrentToken := TLessToken.Create(StartLine, StartCol);
      end;
      // Infinitely many is handled in its own function to cut down line length here
      '0' .. '9': begin
        FCurrentToken := GetNumber;
      end;
      'a' .. 'z','_': begin
        FCurrentToken := GetIdentifierOrKeyword;
      end;
      else begin
        FCurrentToken := TUnknownToken.Create(StartLine, StartCol, FLastChar);
        FLastChar := GetChar;
      end;
    end;
end;

如您所見，核心是一個（可能很大的）case 語句。其他部分相當自文件化並且有很好的註釋。最後但並非最不重要的一點是建構函式

constructor TLexer.Create(AStream: TStream; AErrorList: TErrorList);
begin
  FStream := AStream;
  FLine := 1;
  FCol := 0;
  FLastChar := GetChar;
  NextToken;
end;

它設定初始的行號和列號（猜猜為什麼它是行的 1 但列的 0 :)), 以及設定第一個可用的詞法單元，以便在呼叫建構函式後 CurrentToken 可用，無需在之後顯式呼叫 NextToken。

測試程式

uses
  Classes,SysUtils,lexer,tokens;
var
  Stream: TStream;
  lex: TLexer;
begin
  Stream := THandleStream.Create(StdInputHandle);
  lex := TLexer.Create(Stream,nil);
  while not(lex.CurrentToken is TEOFToken) do begin
    WriteLn(lex.CurrentToken.ToString);
    lex.NextToken;
  end;
  lex.Free;
  Stream.Free;
end.

作為練習，您可以嘗試將詞法分析器擴充套件為浮點數、字串、以 10 以外的基數表示的數字、科學記數法、註釋等。

表驅動的書寫掃描

編譯通道常量

詞法分析工具

透過工具掃描 - lex/flex

待辦事項
我的 Wikipedia:en:Flex 詞法分析器文章。

透過工具掃描 - JavaCC

JavaCC 是標準的 Java 編譯器編譯器。與本章介紹的其他工具不同，JavaCC 是一個解析器和掃描器（詞法分析器）生成器合二為一。JavaCC 只接受一個輸入檔案（稱為語法檔案），然後使用該檔案建立詞法分析的類以及解析器。

在 JavaCC 的術語中，掃描器/詞法分析器被稱為詞法單元管理器。事實上，包含詞法單元管理器的生成的類被稱為ParserNameTokenManager。當然，按照通常的 Java 檔案命名要求，該類儲存在名為ParserNameTokenManager.java 的檔案中。ParserName 部分取自輸入檔案。此外，JavaCC 建立第二個類，稱為ParserNameConstants。正如其名稱所暗示的那樣，第二個類包含常量的定義，尤其是詞法單元常量。JavaCC 還生成一個樣板類，稱為Token。這個類始終相同，包含用於表示詞法單元的類。還會獲得一個名為ParseError 的類。這是一個異常，如果出現問題則會丟擲該異常。

可以指示 JavaCC 不要生成ParserNameTokenManger，而是提供您自己的手寫詞法單元管理器。通常，對於本章中介紹的所有工具來說，手寫掃描器/詞法分析器/詞法單元管理器效率要高得多。因此，如果您發現生成的編譯器太大，請仔細檢視生成的掃描器/詞法分析器/詞法單元管理器。如果您需要解析二進位制資料並將其饋送到解析層，則自行編寫詞法單元管理器也很有用。

然而，由於本節是關於使用 JavaCC 生成詞法單元管理器，而不是手寫詞法單元管理器，因此此處不再詳細討論。

在 JavaCC 語法檔案中定義詞法單元

JavaCC 語法檔案通常以與解析器相關但與掃描器無關的程式碼開頭。對於簡單的語法檔案，它看起來類似於

options { LOOKAHEAD=1; }

PARSER_BEGIN(ParserName)
public class ParserName {
   // code to enter the parser goes here
}
PARSER_END(ParserName)

這通常緊隨其後的是標記的定義。這些定義是我們本章感興趣的資訊。當涉及到標記的定義時，JavaCC 理解四種不同的型別，由四個不同的關鍵字表示。

TOKEN: 指定標記管理器應能夠識別的標記的正則表示式。

SPECIAL_TOKEN: SPECIAL_TOKEN 與 TOKEN 類似，只是解析器會忽略它們。這對於指定註釋很有用，註釋應該被理解，但對解析器沒有意義。

SKIP: 標記管理器應該完全忽略的標記（輸入資料）。這通常用於忽略空白。SKIP 標記仍然會中斷其他標記。例如，如果跳過空白，並且定義了標記“else”，並且輸入是“el se”，則不會匹配標記。

MORE: 這用於一種高階技術，其中標記是逐步構建的。MORE 標記被放入緩衝區，直到下一個 TOKEN 或 SPECIAL_TOKEN 匹配。然後返回所有資料，緩衝區中累積的標記以及最後一個 TOKEN 或 SPECIAL_TOKEN。

一個使用 *MORE* 標記的例子是構造，其中希望匹配某個起始字串、任意資料和某個結束字串。許多程式語言中的註釋或字串文字都符合這種形式。例如，要匹配由 *"* 分隔的字串文字，不會將第一個找到的 *"* 作為標記返回。相反，會累積更多標記，直到找到字串文字的結束 *"*。然後返回完整的文字。有關此用於掃描註釋的示例，請參見註釋示例。

上面提到的每個關鍵字都可以根據需要使用多次。這使得可以對標記進行分組，例如，將運算子放在一個列表中，將關鍵字放在另一個列表中。所有相同型別的部分都被合併，就像只有一個部分被指定一樣。

每個標記規範都包含標記的符號名稱和一個正則表示式。如果正則表示式匹配，標記管理器將返回該符號。

簡單示例

讓我們看一個例子

//
// Skip whitespace in input
// if the input matches space, carriage return, new line or a tab,
// it is just ignored
//
SKIP: { " " | "\r" | "\n" | "\t" }

// Define the tokens representing our operators
//
TOKEN: {
    < PLUS:  "+" >
  | < MINUS: "-" >
  | < MUL:   "*" >
  | < DIV:   "/" >
}

//
// Define the tokens representing our keywords
//
TOKEN: {
    < IF:    "if" >
  | < THEN:  "then" >
  | < ELSE:  "else" >
}

以上所有標記定義都使用簡單的正則表示式，其中只匹配常量。建議研究 JavaCC 文件以瞭解所有可能的正則表示式。

當以上檔案透過 JavaCC 執行時，會生成一個標記管理器，它能夠理解上面宣告的標記。

註釋示例

在程式語言中消除（忽略）註釋是詞法分析器的常見任務。當然，當使用 JavaCC 時，這項任務通常由標記管理器完成，方法是指定特殊標記。

基本上，JavaCC 已經演化出一種關於如何忽略註釋的標準習慣用法。它將 *SPECIAL_TOKEN* 和 *MORE* 型別的標記與 *詞法狀態* 結合起來。假設我們有一種程式語言，其註釋以 *--* 開頭，並以另一個 *--* 或行尾結束（這是 ASN.1 和其他幾種語言的註釋模式）。那麼，為其構建掃描器的辦法是

//
// Start of comment. Don't return as token, instead
// shift to special lexical state.
//
SPECIAL_TOKEN: {  <"--"> : WithinComment }

//
// While inside the comment lexicals state, look for end
// of comment (either another '--' or EOL). Don't return
// the (accumulated data). Instead switch back to normal
// lexical state
//
<WithinComment> SPECIAL_TOKEN:
{
    <("--" | "\n" )> : DEFAULT
}

//
// While inside the comment state, accumulate all contents
//
<WithinComment> MORE: { <~[]> }

待辦事項
文件詞法狀態；標記管理器宣告；有關正則表示式的詳細資訊；內部 (#) 正則表示式。