Lexical Analysis

序

我最近在学习 SFU 的 Compiler 课程。由于疫情缘故， SFU 的 Compiler 课程在线上进行，才让我有机会白嫖到这门课程。这门课程理论与实践结合，课程作业提供了详细的文档、测试程序以及 testcase。

课程主页地址
http://anoopsarkar.github.io/compilers-class/syllabus.html

Lexical analysis

Lexical analysis （词法分析）是编译的第一个阶段，输入字符串流，输出等价的 Token 列表。关键字、标识符、数字常量、字符串常量等等都是一个 Token。部分 Token 还需要附加值属性才能完整表示。比如一个表示数字的 Token 还应该有对应的值属性。

正则表达式能很好地胜任 Token 识别工作，日常开发任务中经常使用正则表达式识别手机号、数字、邮箱等等。编译则利用正则表达式识别 Token。

词法分析器如何使用正则表达式识别 Token？

每一个 Token 都对应一个正则表达式，最终将所有 Token 的正则表达式组合起来构成一个能识别所有 Token 的正则表达式。
匹配字符串长度最长的 Token
相同字符串匹配长度的 Token，匹配优先级高的 Token
加入错误处理机制，比如提示错误

Finite state automata

正则表达式背后的原理是有限状态自动机(FA)，利用 FA 理论可以实现正则表达式。学习 FA 可以深入理解词法分析的工作原理。

FA 有两种:

确定有限状态自动机 Deterministic (DFA)
非确定有限状态自动机 Non-deterministic (NFA)

FA 的基本结构

输入字符表
有限状态集合
转移函数
开始状态
结束状态

Example

双圆圈为结束状态

特殊的 ε-move

DFA & NFA

确定有限状态自动机 Deterministic (DFA)
遵循两个原则:

每个一个状态的每一个输入只有一个对应的转移状态
没有 ε-move

NFA 则支持多个状态转移和ε-move

NFA 构造方便，而 DFA 编程方便，效率高。因此，一般操作如下
正则 pattern -> NFA -> DFA

NFA 转 DFA 方法：子集构造法

正则表达式转 NFA

方法：Thompson’s construction
https://en.wikipedia.org/wiki/Thompson%27s_construction

词法分析器使用 DFA

每一个 Token 通过正则表达式 $r_i$ 定义
合并所有 $r_i$ 为一个更大表达式 $R = (r_1 | r_2 | … | r_n)$
将 R 转换成 NFA，DFA，最后优化

编写 Decaf 语言词法分析器

decaf 语言是为学习这门课程设计的语言，具体信息 PDF 如下

Decaf.pdf

课程要求使用 lex 实现 decaf 的词法分析器， lex 是一个用于生成词法分析器代码的程序。

lex 源文件 -> lex -> 词法分析器C语言代码 -> gcc/clang -> 词法分析器

lex 简单写法

嵌入 C 语言代码

%{ .... C语言代码...  %}

例如:
%{
#include <stdio.h>
#define NUMBER     256
#define IDENTIFIER 257
%}

使用正则表达式定义 Token 并为每个 Token 添加处理代码

定义正则表达式的别名，在 lex 的最顶层定义，例如定义一个用于识别数字的正则表达式别名 num

1 2	`/* regexp definitions */ num [0-9]+`

使用正则表达式定义 Token 并添加处理代码

%%
正则表达式 {匹配处理代码，例如返回该 Token 对应的 Token 常量}
%%

例如：
%%
{num}                 { return NUMBER; }
[a-zA-Z][a-zA-Z0-9]*  { return IDENTIFIER; }
\n                    /* silently ignore */
.                     { return -1; }
%%

lex 将每次接收一个 Token 都就会执行对应 token {} 中的代码，并将返回值作为 yylex() 的返回值。 yylex 从输入流解析一个 token。

完整例子

%{
#include <stdio.h>
#define NUMBER     256
#define IDENTIFIER 257
%}

/* regexp definitions */
num [0-9]+

%%

{num}                 { return NUMBER; }
[a-zA-Z][a-zA-Z0-9]*  { return IDENTIFIER; }
\n                    /* silently ignore */
.                     { return -1; }
%%

int main () {
  int token;
  while ((token = yylex())) {
    switch (token) {
      case NUMBER: printf("NUMBER: %s, LENGTH:%d\n", yytext, (int)yyleng); break;
      case IDENTIFIER: printf("IDENTIFIER: %s, LENGTH:%d\n", yytext, (int)yyleng); break;
      default: printf("Error: %s not recognized\n", yytext);
    }
  }
  exit(0);
}

Decaf Token 定义

T_AND            &&
T_ASSIGN         =
T_BOOLTYPE       bool
T_BREAK          break
T_CHARCONSTANT   char_lit (see section on Character literals)
T_COMMA          ,
T_COMMENT        comment
T_CONTINUE       continue
T_DIV            /
T_DOT            .
T_ELSE           else
T_EQ             ==
T_EXTERN         extern
T_FALSE          false
T_FOR            for
T_FUNC           func
T_GEQ            >=
T_GT             >
T_ID             identifier (see section on Identifiers)
T_IF             if
T_INTCONSTANT    int_lit (see section on Integer literals)
T_INTTYPE        int
T_LCB            {
T_LEFTSHIFT      <<
T_LEQ            <=
T_LPAREN         (
T_LSB            [
T_LT             <
T_MINUS          -
T_MOD            %
T_MULT           *
T_NEQ            !=
T_NOT            !
T_NULL           null
T_OR             ||
T_PACKAGE        package
T_PLUS           +
T_RCB            }
T_RETURN         return
T_RIGHTSHIFT     >>
T_RPAREN         )
T_RSB            ]
T_SEMICOLON      ;
T_STRINGCONSTANT string_lit (see section on String literals)
T_STRINGTYPE     string
T_TRUE           true
T_VAR            var
T_VOID           void
T_WHILE          while
T_WHITESPACE     whitespace (see section on Whitespace)

decaflex.lex 实现

%{
#include <iostream>
#include <cstdlib>
using namespace std;
enum {T_N_TOKEN,T_FUNC, T_INT, T_PACKAGE, T_LCB, T_RCB, T_LPAREN, T_RPAREN, T_ID, 
      T_WHITESPACE, T_WHITESPACE_N, T_AND, T_ASSIGN, T_BOOLTYPE, T_BREAK, 
      T_COMMA, T_CHARCONSTANT, T_COMMENT, T_CONTINUE, T_DIV, T_DOT, T_ELSE, 
      T_EQ, T_EXTERN, T_FALSE, T_FOR, T_GEQ, T_GT, T_IF, T_INTCONSTANT, 
      T_INTTYPE, T_LEFTSHIFT, T_LEQ, T_LSB, T_LT, T_MINUS, T_MOD, T_MULT,
      T_NEQ, T_NOT, T_NULL, T_OR, T_PLUS, T_RIGHTSHIFT, T_RSB, T_SEMICOLON, 
      T_STRINGCONSTANT, T_STRINGTYPE, T_TRUE, T_VAR, T_VOID, T_WHILE, T_RETURN
      };

string & covert_newline(string & s){ // 用来对换行转义为 \n
    string tmp = "";
    for(size_t i = 0; i < s.size(); i++)
      if(s[i] == '\n')
        tmp += "\\n";
      else
        tmp += s[i];
    s = tmp;
    return s;
}

%}

%%
  /*
    Pattern definitions for all tokens
  */
func                       { return T_FUNC; }
return                     { return T_RETURN; }
while                      { return T_WHILE; }
void                       { return T_VOID; }
var                        { return T_VAR; }
string                     { return T_STRINGTYPE; }
true                       { return T_TRUE; }
null                       { return T_NULL; }
int                        { return T_INTTYPE; }
if                         { return T_IF; }
extern                     { return T_EXTERN; }
int                        { return T_INT; }
for                        { return T_FOR; }
package                    { return T_PACKAGE; }
break                      { return T_BREAK; }
continue                   { return T_CONTINUE; }
,                          { return T_COMMA; }
else                       { return T_ELSE; }
false                      { return T_FALSE; }
==                         { return T_EQ;  }
>=                         { return T_GEQ; }
>                          { return T_GT;  }
\<\<                       { return T_LEFTSHIFT;  }
>>                         { return T_RIGHTSHIFT; }
\<=                        { return T_LEQ; }
\[                         { return T_LSB; }
\]                         { return T_RSB; }
\<                         { return T_LT; }
\-                         { return T_MINUS; }
\+                         { return T_PLUS; }
\%                         { return T_MOD; }
\*                         { return T_MULT; }
!=                         { return T_NEQ; }
!                          { return T_NOT; }
\|\|                       { return T_OR; }
;                          { return T_SEMICOLON; }
\"([^\n"\\]|\\(a|b|t|n|v|f|r|\\|\'|\"))*\" { return T_STRINGCONSTANT; }

([0-9]+(\.[0-9]+)?)|(0[xX][0-9A-Fa-f]+)          { return T_INTCONSTANT; }
\'([^\n'\\]|\\(a|b|t|n|v|f|r|\\|\'|\"))\'        { return T_CHARCONSTANT; }
"//".*"\n"                 { return T_COMMENT; }
\{                         { return T_LCB; }
\}                         { return T_RCB; }
\(                         { return T_LPAREN; }
\)                         { return T_RPAREN; }
[a-zA-Z\_][a-zA-Z\_0-9]*   { return T_ID; }
\n+[\t\r\a\v\b ]*          { return T_WHITESPACE_N; }
[\t\r\a\v\b ]+             { return T_WHITESPACE; }
&&                         { return T_AND; }
=                          { return T_ASSIGN; }
\/                         { return T_DIV; }
"."                        { return T_DOT; } 
.                          { cerr << "Error: unexpected character in input" << endl; return -1; }
%%

int main () {
  int token;
  string lexeme;
  while ((token = yylex())) {
    if (token > 0) {
      lexeme.assign(yytext);
      switch(token) {
        case T_FUNC: cout << "T_FUNC " << lexeme << endl; break;
        case T_INT: cout << "T_INT " << lexeme << endl; break;
        case T_PACKAGE: cout << "T_PACKAGE " << lexeme << endl; break;
        case T_LCB: cout << "T_LCB " << lexeme << endl; break;
        case T_RCB: cout << "T_RCB " << lexeme << endl; break;
        case T_LPAREN: cout << "T_LPAREN " << lexeme << endl; break;
        case T_RPAREN: cout << "T_RPAREN " << lexeme << endl; break;
        case T_ID: cout << "T_ID " << lexeme << endl; break;
        case T_WHITESPACE: cout << "T_WHITESPACE " << lexeme << endl; break;
        case T_WHITESPACE_N:
          cout << "T_WHITESPACE ";
          for( size_t i = 0; i < lexeme.size(); i++)
            if( lexeme[i] == '\n' ) cout << "\\n"; else cout << lexeme[i];
          cout << endl;
          break;

        // mycode
        case T_AND: cout << "T_AND " << lexeme << endl; break;
        case T_ASSIGN: cout << "T_ASSIGN " << lexeme << endl; break;
        case T_BOOLTYPE: cout << "T_BOOLTYPE " << lexeme << endl; break;
        case T_BREAK: cout << "T_BREAK " << lexeme << endl; break;
        case T_COMMA: cout << "T_COMMA " << lexeme << endl; break;
        case T_CHARCONSTANT: cout << "T_CHARCONSTANT " << lexeme << endl; break;
        case T_COMMENT: cout << "T_COMMENT " << covert_newline(lexeme) << endl; break;
        case T_CONTINUE: cout << "T_CONTINUE " << lexeme << endl; break;
        case T_DIV: cout << "T_DIV " << lexeme << endl; break;
        case T_DOT: cout << "T_DOT " << lexeme << endl; break;
        case T_ELSE: cout << "T_ELSE " << lexeme << endl; break;
        case T_EQ: cout << "T_EQ " << lexeme << endl; break;
        case T_EXTERN: cout << "T_EXTERN " << lexeme << endl; break; 
        case T_FALSE: cout << "T_FALSE " << lexeme << endl; break;
        case T_FOR: cout << "T_FOR " << lexeme << endl; break;
        case T_GEQ: cout << "T_GEQ " << lexeme << endl; break;
        case T_GT: cout << "T_GT " << lexeme << endl; break;
        case T_IF: cout << "T_IF " << lexeme << endl; break;
        case T_INTCONSTANT: cout << "T_INTCONSTANT " << lexeme << endl; break;
        case T_INTTYPE: cout << "T_INTTYPE " << lexeme << endl; break;
        case T_LEFTSHIFT: cout << "T_LEFTSHIFT " << lexeme << endl; break;
        case T_LEQ: cout << "T_LEQ " << lexeme << endl; break;
        case T_LSB: cout << "T_LSB " << lexeme << endl; break;
        case T_LT: cout << "T_LT " << lexeme << endl; break;
        case T_MINUS: cout << "T_MINUS " << lexeme << endl; break;
        case T_MOD: cout << "T_MOD " << lexeme << endl; break;
        case T_MULT: cout << "T_MULT " << lexeme << endl; break;
        case T_NEQ: cout << "T_NEQ " << lexeme << endl; break;
        case T_NOT: cout << "T_NOT " << lexeme << endl; break;
        case T_NULL: cout << "T_NULL " << lexeme << endl; break;
        case T_OR: cout << "T_OR " << lexeme << endl; break;
        case T_PLUS: cout << "T_PLUS " << lexeme << endl; break;
        case T_RIGHTSHIFT: cout << "T_RIGHTSHIFT " << lexeme << endl; break;
        case T_RSB: cout << "T_RSB " << lexeme << endl; break;
        case T_SEMICOLON: cout << "T_SEMICOLON " << lexeme << endl; break;
        case T_STRINGCONSTANT: cout << "T_STRINGCONSTANT " << lexeme << endl; break;
        case T_STRINGTYPE: cout << "T_STRINGTYPE " << lexeme << endl; break;
        case T_TRUE: cout << "T_TRUE " << lexeme << endl; break;
        case T_VAR: cout << "T_VAR " << lexeme << endl; break;
        case T_VOID: cout << "T_VOID " << lexeme << endl; break;
        case T_WHILE: cout << "T_WHILE " << lexeme << endl; break;
        case T_RETURN: cout << "T_RETURN " << lexeme << endl; break;
        default: exit(EXIT_FAILURE);
      }
    } else {
      if (token < 0) {
        exit(EXIT_FAILURE);
      }
    }
  }
  exit(EXIT_SUCCESS);
}

makefile 文件


lexlib=l
bindir=.
rm=/bin/rm -f
targets=
cpptargets=decaflex

all: $(targets) $(cpptargets)

$(targets): %: %.lex
	@echo "compiling lex file:" $<
	@echo "output file:" $@
	flex -o$@.c $<
	gcc -o $(bindir)/$@ $@.c -l$(lexlib)
	$(rm) $@.c

$(cpptargets): %: %.lex
	@echo "compiling cpp lex file:" $<
	@echo "output file:" $@
	flex -o$@.cc $<
	g++ -o $(bindir)/$@ $@.cc -l$(lexlib)
	$(rm) $@.cc

clean:
	$(rm) $(targets) $(cpptargets)

lex 默认从 stdin 获取输入流。
我的实现 https://github.com/P4nda0s/compilers-class-hw

compiler

note

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Yacc practice Previous

Hello World Next