[Compiler 筆記] lex

Published on:
Tags: compiler

Lex 是用來產生 lexical analyzer (scanner) 的 C 語言程式碼的工具
也可以說是 lexical analyzer generater

主要用來比對字串, 取出所要的 tokens
通常搭配另一個工具 yacc 使用

Lex 的字串分析是使用 Regular Expression (正規表達式),
可以以一個 FSA (Finite State Automaton)來解釋

一個簡單的範例如下:

demo.l
digit  [0-9]
letter [A-Za-z]

%%

{letter}({letter}|{digit})* {
  printf("Identifier read: %s", yytext);
}

. 

%%
int main() {
  yylex();
  return 0;
}

int yywrap() { return 1; }

編譯執行這個檔案:

lex demo.l    # 產生 lex.yy.c

gcc lex.yy.x -o demo

說明

lex 檔案分為三個區塊, 以單行的 "%%" 符號區隔

/*** definitions ***/
%%
/*** rules ***/
%%
/*** subroutines ***/

definitions 的區塊可以定義 lex 中使用的代稱,
也可以寫入要出現在所產生的 C 檔案頂端的程式碼, 以 "%{" 和 "%}" 框起
如:

digit  [0-9]

%{
  #include <string.h>
  int id_count;
%}

%%
/*** rules ***/
%%
/*** subroutines ***/

rules 區塊則定義匹配的規則, 以及匹配時的行為

digit  [0-9]
letter [A-Za-z]
%%
{letter}({letter}|{digit})* {
  printf("Identifier read: %s", yytext);
}
%%

以這段程式碼為例, 是在讀到變數名稱時將該名稱印出來
(變數名稱定義為由英文字母開頭, 並由字母和數字組成的字串

在 definitions 區塊已經定義了:
digit 是 0~9 這幾個字元, 而 letter 則是大寫和小寫的 A~Z

{letter}({letter}|{digit})* 的意思是:
讀進了一個 letter 之後, 之後連著零或多個 "letter 或 digit"
( "|" 表示"或", "*" 是重複零或多次 )

在匹配規則之後, 以 空白/tab/換行 分隔, 後方是在匹配時要執行的 C 程式
以本例來說, 就是單純的把找到的變數名稱印出來

最後的 subroutines 區塊則要擺 C 程式碼

int main() {
  yylex();
  return 0;
}

int yywrap() {
  return 1;
}

yylex() 是要 lex 執行比對匹配(也就是前面rules定義的動作)的函式
yywrap 會在讀完 input 後被呼叫, 回傳 1, 表示沒有其他事情要做, 反之回傳 0

簡單的概念大概是這樣, 關於正規表達式的規則就不再此詳述
另外補充一下會常用的幾個全域變數:
yytext: matched string
yyleng: length of the matched string
yyin / yyout: input / output FILE*

Comments

comments powered by Disqus