程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++：自制Lex 詞法分析器生成器

C++：自制Lex 詞法分析器生成器

編輯：關於C++

前一陣子，編譯原理課實驗內容是要去做一個詞法分析器，實現後，覺得沒有把正規表達式和NFA、DFA這些知識用上，所以就產生了想自己去實現一個lex的想法，於是就有了這篇博文。

可以明確lex的功能：讀進一個代表詞法分析器規則的輸入字符串流，然後輸出以C語言實做的詞法分析器源代碼。
本質上，本人是在對原lex進行模仿，但使用規則細節什麼的與其並不一致，比如原lex用正則表達式來表示詞法分析器規則，而本人的自制lex使用的是正規表達式，所以接下來關於原lex的內容不再贅述。

執行流程

1.解析lex文本

1.1文本規則

%{
    c代碼區塊
%}
%!
    定義區塊
%!
%%
    規則1 方法體
%$
    規則2 方法體
%$
    ... 
%%

由上可以看到，整個lex文本分為三個區塊。

c代碼區

用%{ %}包圍，裡面內容是c代碼，這些代碼會原樣復制進程序生成的詞法分析器源代碼中，也就是說，我們可以在這個區塊裡預定義一些c函數、變量等等。

定義區

用%! %!包圍，裡面內容是一些定義，格式為 a = b。

a表示我們定義一種輸入字符，比如所有的字母、數字，或是a-v，3-7等等區間，或是除了字母以外的任何字符。我們可以給這些值的集合起一個名字為a。
b表示一個函數名，該函數接受一個char字符，返回1或者0，表示輸入是否匹配。該函數必須自己在c代碼區進行實現。
例如：我們定義 digit = isDigit
digit表示所有的數字，則我們需要實現這樣一個函數：

int isDigit(char ch){
    if(ch >= '0' && ch <= '9')
        return 1;
    return 0;
}

完成上述之後，我們就可以在規則區裡以{a}的形式在正規表達式中使用該自定義輸入。

規則區

這裡可以說是整個lex文件最核心的部分了。
我們需要在這裡對所有的詞法規則用正規表達式進行描述。
還是舉個例子，我們要將c語言的標識符的規則進行描述：

正規表達式  方法體

({letter}|_)({letter}|_|digit)* {printf("<$ID, %s>", LEX_TEXT);}

letter表示所有字母，digit表示所有數字，這兩者都屬於是我們在定義區所自定義的輸入類型。
那麼上面正規表達式代表的含義就是所有以字母或者下劃線開頭並後續字母是字母數字或者下劃線的字符串，即是我們認為合法的標識符。
後面{}包含的內容是我們的方法體，即定義我們生成的詞法分析器當識別出符合正規式定義的字符串後需要進行的操作，該操作用c語言來進行描述。
LEX_TEXT為我們預設定的保存識別出的串的char數組。
那麼上面的規則所定義的就是對標識符進行匹配，並在匹配成功之後將其進行輸出。

1.2文本識別細節

這部分做的比較粗略。
1.上述三個區域的界符即%{，%!等必須出現在每行的行首，否則會被忽略。
2.所有出現在三個區域外的文本內容全部忽略
3.當出現文本忽略時會報出警告(文本內容及行號)
4.當出現文本識別錯誤時會進行報錯(文本內容及行號)並程序終止。
5.因為正規式裡面原本就有(,),|,*等符號，再加上{}用於標識自定義輸入的符號以及空格，這些字符均需要進行轉義，我定義的轉義標志是%，與c語言的\沒有什麼區別。用%$表示正規表達式裡的空。

根據lex文本內容生成NFA等

這部分我用了一個棧來實現，具體細節可參看之前寫的一篇博客正規表達式轉NFA(C++)，細節有所差異，但是實現思想是一致的，這裡就不再重復描述了。
除了要生成NFA，還要完成兩件事。
1. 保存定義區裡自定義輸入與對應判斷函數名的映射。
2. 保存NFA的終點狀態的序號集合，並保存其各自對應的方法體的映射。

根據NFA生成DFA

這裡使用的方法是子集法：
每個狀態表示為一個數字，這一點在上面已經提過，那麼我們用一個vector表示一個狀態集合。
再使用一個set和一個queue，set用於對vector進行查重，queue用於遍歷，從起始狀態的集合開始，將其經每個輸入到達的狀態加入queue，當然，前提是該狀態集合沒有在set中出現過。
這裡有個重點是關於空的處理，見代碼。

//i為當前狀態，input為輸入，state為存放可到達的狀態的集合
void Lex::findBeGo(int i, string input, vector* state)
{
    for(auto x : nfaVet[i])
    {
        int sId = x.toId;
        bool flag = true;
        for(auto iter=state->begin(); iter!=state->end(); iter++)
            if((*iter) == sId)
            {
                flag = false;
                break;
            }

        if(flag && input.compare(x.input) == 0)
        {
            state->push_back(sId);
            findBeGo(sId, "", state);
        }
    }
}

當然，這裡也需要保存DFA的終點狀態的序號，並保存其各自對應的方法體的映射。

將DFA轉換為C代碼

如果用自動機的模式寫過一次詞法分析器，就很明了，DFA只跟自動機的狀態裡面內容相關。
即：switch(狀態){//} ；裡面的內容是需要根據DFA動態生成的，其他的都不需要改變。
所以我們一開始就將switch部分上下的代碼都確定，然後根據DFA來生成。
對每一個case來說，我們需要輸出的內容只有以下幾點：
1. 狀態id
2. 狀態接受的輸入，以及該輸入轉向的狀態id
3. 枚舉完所有可接受的輸入後，如果當前字符與以上輸入都不符合，那麼根據該狀態是否是終止狀態來確定是結束並執行方法體還是報錯。例子如下：

case ID:
        {
            ch = *str++;
            SYLEX_TEXT[SYLEX_TEXT_LEN++]=ch;
            if(ch == 輸入1){
                SYLEX_STATE = 轉向的狀態;
            }
            else
            if(ch == 輸入2){
                SYLEX_STATE = 轉向的狀態;
            }
            else
            {
                //根據id是否可終止，來決定是報錯還是執行方法體
            }

這裡還有個細節，關於我們的自定義輸入，因為普通輸入字符我們直接是用if(ch == ‘X’)來判斷。而自定義輸入，我們是通過if(函數名(ch))來判斷，所以在輸出源代碼時，需要先對其輸入進行判斷是否是自定義輸入，這裡我們用第一步時建立的映射直接就可以解決。

源碼

全部流程都封裝在了Lex類中，因為篇幅問題，就只貼類的成員變量和成員函數聲明部分的代碼。
有興趣的朋友，可以去github上看完整代碼，鏈接如下。
shiyi1996/project/tree/master/Lex

//
//  Lex.hpp
//  Lex
//
//  Created by shiyi on 2016/10/18.
//  Copyright ? 2016年 shiyi. All rights reserved.
//

#ifndef Lex_hpp
#define Lex_hpp

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 

using namespace std;

struct Node
{
    Node(int fromId, string input, int toId)
    {
        this->fromId = fromId;
        this->input = input;
        this->toId = toId;
    }
    int fromId;
    string input;
    int toId;
};

class Lex
{
public:
    static const int MAXID = 100000;

    Lex(string _lexFile);
    Lex(string _lexFile, string _outCFile);
    void init();

    //寫入scanner函數之前
    void outCodeLeft();
    //寫入scanner函數之後
    void outCodeRight();
    //寫入scanner函數
    void outCodeMid();
    //解析lex源文件
    void scanner();
    //錯誤警告等輸出
    inline void printError(int line, string str, string mess);
    inline void printWaring(int line, string str, string mess);
    //解析方法體
    void getFunc(string str, int line);
    //解析正規式
    void getRegular(string str, int line);

    //------日後補充
    //判斷正規式是否合法
    bool isExpre(vector>);
    //DFA最小化
    void getSimpDFA();

    // -----------

    //添加NFA節點
    inline void addNFANode(int fromId, string input, int toId);
    //添加DFA節點
    inline void addDFANode(int fromId, string input, int toId);

    //正規式轉NFA
    void regrToNFA(vector> regr, int startId, int endId, int &itemId);
    //生成NFA
    void getNFA();
    //生成DFA
    void getDFA();
    //nfa查詢
    void findBeGo(int i, string input, vector* state);
    //獲取nfa目標狀態集合
    vector* getState(vector* fromState, string input);
    //獲取終態
    void getVt(map, int> stateMap);

    //執行操作
    void work();

    //輸出-測試-
    inline void print();

private:
    string lexFile;
    string outCFile;
    //自定義輸入對應方法體
    map funcMap;
    //正規式
    vector>> regrVet;
    //方法體
    vector funcVet;
    //NFA
    vector nfaVet[MAXID];
    //DFA
    vector dfaVet[MAXID];
    //儲存所有輸入
    set inputSet;
    //DFAend
    int dfaEnd[MAXID];
    //NFAend   值為funcVet item的下標
    int nfaEnd[MAXID];
    int nfaNum;
    int dfaNum;
};

#endif /* Lex_hpp */

測試

Lex代碼

%{
#include
#include
#include

const int KEY_NUM = 32;
const char* KEY_SET[] = {
    "auto", "break", "case", "char", "const", "continue",
    "default", "do", "double", "else", "enum", "extern",
    "float", "for", "goto", "if", "int", "long", "register",
    "return", "short", "signed", "sizeof", "static", "struct",
    "switch", "typedef", "union", "unsigned", "void", "volatile",
    "while"
};

int isDigit(char ch)
{
    if(ch <= '9' && ch >= '0')
        return 1;
    return 0;
}

int isLetter(char ch)
{
    if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
        return 1;
    return 0;
}

int getKeyId(char *str)
{
    for(int i=0; i
#include 
#include 

#define SYLEX_MAXSIZE_TEXT 120
#define SYLEX_MAXSIZE_BUFF 1024

char SYLEX_FILE_NAME[100];
char SYLEX_OUT_FILE_NAME[100];
int SYLEX_LINE = 0;
int SYLEX_STATE = 0;
int SYLEX_TEXT_LEN = 0;
char SYLEX_TEXT[SYLEX_MAXSIZE_TEXT];
char SYLEX_BUFF[SYLEX_MAXSIZE_BUFF];

//掃描函數
void SYLEX_scanner(char *str)
{
    char ch = ' ';
    while(ch != '\0')
    {
        //printf("%c %d\n", ch, SYLEX_STATE);
        switch(SYLEX_STATE) {
        case 0:
        {
            ch = *str++;
            SYLEX_TEXT[SYLEX_TEXT_LEN++]=ch;
            if(ch == ' '){
                SYLEX_STATE = 1;
            }
            else
            if(ch == '#'){
                SYLEX_STATE = 2;
            }
            else
            if(ch == '&'){
                SYLEX_STATE = 3;
            }
            else
            if(ch == '('){
                SYLEX_STATE = 4;
            }
            else
            //。。。
            else
            if(ch == '}'){
                SYLEX_STATE = 28;
            }
            else
            if(ch == '~'){
                SYLEX_STATE = 29;
            }
            else
            {
printf("Error in line %d\n", SYLEX_LINE);
exit(1);
            }
            break;
        }
        case 1:
        {
            ch = *str++;
            SYLEX_TEXT[SYLEX_TEXT_LEN++]=ch;
            {
SYLEX_TEXT[SYLEX_TEXT_LEN-1] = '\0';
SYLEX_TEXT_LEN=0;
SYLEX_STATE=0;
str--;
//**************s
{}
//**************e
            }
            break;
        }
      //考慮篇幅，省略中間的狀態
        case 81:
        {
            ch = *str++;
            SYLEX_TEXT[SYLEX_TEXT_LEN++]=ch;
            {
SYLEX_TEXT[SYLEX_TEXT_LEN-1] = '\0';
SYLEX_TEXT_LEN=0;
SYLEX_STATE=0;
str--;
//**************s
{   printf("%s 應該預處理的，暫時先忽略", SYLEX_TEXT);}
//**************e
            }
            break;
        }
        }
    }
}

int main(int argc, char **args)
{
    if(argc == 1)
    {
        printf("沒有輸入源文件名");
        return 0;
    }
    else if(argc == 2)
    {
        strcpy(SYLEX_FILE_NAME, args[1]);
        sprintf(SYLEX_OUT_FILE_NAME, "%s.out", SYLEX_FILE_NAME);
    }
    else
    {
        strcpy(SYLEX_FILE_NAME, args[1]);
        strcpy(SYLEX_OUT_FILE_NAME, args[2]);
    }
    FILE* file = fopen(SYLEX_FILE_NAME, "r");
    while(NULL != fgets(SYLEX_BUFF, SYLEX_MAXSIZE_BUFF, file))
    {
        ++SYLEX_LINE;
        SYLEX_scanner(SYLEX_BUFF);
    }
    return 0;
}

測試C代碼

#include 
#include 
#include"aaa.h"

int main()
{
    int a = 5;
    int b = a + 3.5E3;
    char s[] = "I love the world\n";
    for(int i=0; i<5; i++)
        printf("%s\n",s);
}

輸出

#include  應該預處理的，暫時先忽略#include  應該預處理的，暫時先忽略#include"aaa.h" 應該預處理的，暫時先忽略
<$ID,main>
<(,->
<),->
<{,->

<$ID,a>
<=,->
<$NUM,5>
<;,->

<$ID,b>
<=,->
<$ID,a>
<+,->
<$NUM,3.5E3>
<;,->

<$ID,s>
<[,->
<],->
<=,->
<$STR,"I love the world\n">
<;,->

<(,->

<$ID,i>
<=,->
<$NUM,0>
<;,->
<$ID,i>
<<,->
<$NUM,5>
<;,->
<$ID,i>
<++,->
<),->
<$ID,printf>
<(,->
<$STR,"%s\n">
<,,->
<$ID,s>
<),->
<;,->
<},->