编译器构造/词法分析

维基教科书用户已提名此页面进行清理。 您可以 帮助使其变得更好。请查看任何 相关讨论。

维基教科书用户已提名此页面进行清理。 您可以 帮助使其变得更好。请查看任何 相关讨论。

词法分析

词法分析是将单个字符流（通常排列成行）分析成一系列词法标记（标记化，例如组成源代码的“单词”和标点符号）的过程，以馈送到解析器。大致相当于将用自然语言（如英语）编写的普通文本拆分成单词和标点符号序列。词法分析通常使用 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 以外的基数表示的数字、科学记数法、注释等。

编译通道常量

词法分析工具

通过工具扫描 - 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: { <~[]> }