創造新語言（2）——用Lex&Yacc建構簡單的分析程式

昨天我們開始設計了一門新語言，制定了基本的開發架構，今天我們就先來了解一下，兩個非常好用的工具，編譯器前端建構的神器——Lex&Yacc，這兩個工具在linux下叫做flex和bison。

Lex是詞法分析器建構工具，我們安裝對應的詞法規則書寫，那麼就能夠為我們生成對應的詞法分析器，自動幫我們分好token，而分詞工作，一直是編譯系統的基礎任務。

我們今天，先來嘗試編寫一個BNF文法的解析器，将我們的BNF解析成代碼可以識别的資料格式，BNF的格式大概是這樣：

{{ do_init() }}

# 定義清單
<definelist> = <definelist> <define> | e ;
<define> = <constdef> | <vardef> | <functiondef> ;

# 變量和常量定義
<constdef> = "const" <const_def_run>  <vardef> {{ isconstdef = false }} ;
<vardef> = "int" <iddeflist> ";" ;
<iddeflist> = <iddeflist> "," <iddef> | <iddef> ;
           

這裡就是我們的原始輸入檔案了，我們希望将其解析成為記憶體中的樹結構，供我們的編譯器使用，目前的任務就是，讀入這樣的文本，解析成樹狀結構。

這裡我們可以發現，這種定義方式就是擴充BNF範式，而其中添加了語義動作的腳本

{{ }}

，腳本也可以單獨使用，用來做一些初始化工作等。

利用詞法分析程式處理單詞

我們先看一下基本的Lex掃描器如何編寫：

/* scanner.l */
%{

#include <stdio.h>
#include "parser.hpp"

#define SAVE_TOKEN yylval.str = yytext
extern "C" int yywrap() { return ; }

%}

/* show the line number */
%option yylineno

%%

"/*"([^\*]|(\*)*[^\*/])*(\*)*"*/" ; 

#[^\n]*\n               ; /* ignore line comment */ 

[ \t\v\n\f]             ; /* ignore blank token */

\"(\\.|[^\\"])*\"       SAVE_TOKEN; return STRING;

"{{"([^}]|\}[^}])*"}}"  SAVE_TOKEN; return SCRIPT;

"e"                     return 'e';

":"                     return ':'; 

"<"                     return '<'; 

">"                     return '>'; 

"["                     return '[';

"]"                     return ']';

"="                     return '='; 

"|"                     return '|';

";"                     return ';';

[a-zA-Z][a-zA-Z-]*  SAVE_TOKEN; return ID;

%%
           

這裡的掃描器是根據多個正則式同時比對的原理，注意，這裡的條目是有順序的，越靠上的元素優先級越高，假若第一個能比對上，那麼就不會比對下面的，但存在更長的比對時，取更長的。

這裡用到了非常神奇的比對:

"/*"([^\*]|(\*)*[^\*/])*(\*)*"*/"
           

能夠比對

這樣的注釋。

能夠比對C風格字元串。

能夠比對類似

{{ somefunction() }}

這樣的腳本。

如果您對這幾個正則式不了解的話，希望先看一下我寫的這篇文章，相信會對您有些幫助：

【Lex識别C風格字元串和注釋 】

詞法分析程式使用很多内置變量和函數，我再來介紹一下這幾句話的意思：

extern "C" int yywrap() { return ; }
           

yywrap

是一個用來處理多檔案的函數，它會在一個檔案處理到結尾時被調用。假若你有多個檔案，希望連續的被lex處理，那麼你可以開一個檔案清單，然後在這裡依次将對應的檔案接入到lex的輸入流中，并且傳回0，lex就認為還沒處理結束，而

yywrap

一旦傳回1時，表示所有的任務已經完成，可以結束了。

這個

SAVE_TOKEN

宏，用到了一個yacc中的内置變量

yylval

，這個變量是一個聯合類型，一會兒你會在yacc的檔案定義中發現一個

%union

的定義，就是它的類型定義。這部分的具體聲明，可以在yacc生成的

parser.hpp

的頭檔案中找到。

%option yylineno
           

這是一個參數設定，啟用了lex的報錯機制，能夠确定對應token的具體行号，雖然肯定會消耗一點資源，但debug也是十分重要的，使用時，隻要在外部引用其中的

yylineno

變量，就能知道目前識别到的位置的行号：

extern int yylineno;
           

利用Yacc識别文法

為了正确的識别整個BNF文法，并且結構化的解析他們，我們寫了如下的一個yacc程式：

/* parser.y */
%{

#include <stdio.h>

extern int yylex();

extern int yylineno;
extern char* yytext;
void yyerror(const char *s);

%}


%union {

    char *str = NULL;

}


%token <str> ID STRING SCRIPT


%start list

%%
/* 總的混合bnf和腳本的清單 */
list : item 
     | list item 
     ;

/* 可以是bnf或腳本 */
item : bnf_item
     | SCRIPT
     ;

/* 一行bnf的定義 */
bnf_item : symbol '=' bnf_list ';'
         ;

/* bnf後面的部分 */
bnf_list : symbol_list
         | bnf_list '|' symbol_list
         ;

/* 一條bnf項的清單 */
symbol_list : symbol
            | symbol_list symbol
            ;

/* 可用的bnf符号 */
symbol : '<' name '>' 
       | '[' name ']'
       | 'e'
       | STRING
       | SCRIPT
       ;

/* 名字，并且可以定義執行個體名 */
name : ID
     | ID ':' ID
     ;
%%

void yyerror(const char* s){
    fprintf(stderr, "%s \n", s);    
    fprintf(stderr, "line %d: ", yylineno);
    fprintf(stderr, "error %s \n", yytext);
}
           

這段程式就是在定義整個BNF文法的結構，以及按照什麼樣的規則規約他們，這裡我們并沒有添加語義動作，我們會在接下來的時間裡将其添加成為一個可用的分析器。

添加主處理函數

我們的yacc和lex寫的源檔案可以被翻譯為C++代碼，但僅僅擁有一個基本的處理函數，要想處理檔案，那就有自己編寫檔案的打開部分并将該檔案重定向到yyin輸入流中。

#include <stdio.h>
#include "parser.hpp"
#include "help_message.h"

extern FILE* yyin;
FILE* file_in;

int main(int argc,const char *argv[])
{
    printf("Welcome to use the XScript!\n");
    if (argc <= ) printf(help_message);
    else {
        /* open the file and change the yyin stream. */
        const char *file_in_name = argv[];
        if ((file_in=fopen(file_in_name,"r"))==NULL) {
            printf("error on open %s file!",file_in_name);
            getchar();
            return ;
        }
        yyin = file_in;
        yyparse();

        /* you should close the file. */
        fclose(file_in);
    }
    return ;
}
           

恩，主函數都寫完了，我也想給這個項目起個名字，就先叫做XScript吧，意為多變的腳本，希望能成為一門自定義文法的翻譯語言。

然後大家應該問，既然都寫完了，那麼如何編譯建構呢？這裡我們使用cmake建構整個工程，現在cmake也比較友善，能夠支援直接調用lex和yacc的linux版，我們隻需要增加兩個cmake子產品就可以實作項目的建構：

cmake_minimum_required(VERSION )

project(scanner)
SET(CMAKE_CXX_COMPILER_ENV_VAR "CXX")
SET(CMAKE_CXX_FLAGS "-std=c++11")
include_directories(include build src)

# bison and flex
find_package(BISON)
find_package(FLEX)
flex_target(SCANNER src/scanner.l  ${CMAKE_CURRENT_BINARY_DIR}/scanner.cpp)
bison_target(PARSER src/parser.y  ${CMAKE_CURRENT_BINARY_DIR}/parser.cpp)
ADD_FLEX_BISON_DEPENDENCY(SCANNER PARSER)

# src files and make exe
file(GLOB_RECURSE source_files "${CMAKE_CURRENT_SOURCE_DIR}/src/*.cpp")
add_executable(scanner
    ${source_files}
    ${BISON_PARSER_OUTPUTS}
    ${FLEX_SCANNER_OUTPUTS})
           

項目的檔案組織目前是這樣的：

LR_Scanner
    | ---- build
    | ---- src
            | ---- main.cpp
            | ---- help_message.h
            | ---- parser.y 
            | ---- scanner.l
    | ---- CMakeLists.txt
           

好的，在build路徑下：

cmake ..
make
           

就搞能編譯通過了，但運作并沒有什麼效果，這隻是因為語義動作并沒有執行，等我們添加好語義動作後，效果就不一樣了，而且目前的解析器，隻要你給的文法不對，他就會在對應的位置報錯，還是很友善的。