lex && yacc

舉個栗子：

if(a > b && c < d)
{
}
           

假如需要分析上面的if語句

lex的模式規則定義如下：

"if"    {return IF;}
"("    {return BOL;}
")"    {return BOR;}
"&&"    {return AND;}
"{"    {return BEL;}
"}"    {return BER;}
">"    {return MOT;}
"<"    {return LET;}
[a-zA-Z]*    {return VALSTR;}
(\n|\r)+    {}
           

其中，BOL BOR等是一些枚舉值

則，lex打标記之後，變成如下形式：

IF BOL VALSTR MOT VALSTR AND VALSTR LET VALSTR BOR BEL BER
           

lex是對輸入文本進行模式比對的過程

之後yacc對标記進行文法分析

yacc的文法規則定義如下：

root: conditon trunk {do something...}

condition: IF BOL expr BOR {do something...}

trunk: BEL  BER | BEL action BER {do something...}

expr: BOL expr BOR{} | expr AND expr{} | expr MOT expr{} | expr LET expr{} | VALSTR{}
           

文法分析會按照設定的文法規則，生成一棵文法樹，并且從底向上執行每個規則對應的動作

可以看到，上面的文法規則和lex分析的結果一一對應，而規則對應的動作則可以自定義，這樣就可以實作自定義的文法了

lex:

    詞法分析器，和c是強耦合

    簡單地講，lex做的是一個字元串比對的工作，它從待比對的文本字元串中尋找預設的表達式，如果尋找到一個特定的表達式，則執行相應的動作

    支援的表達式類似正規表達式

    使用方式：

    1 按照lex的規則，指定表達式及其相應的動作

    2 根據上一步配置的表達式和動作，生成掃描器的c代碼

    lex的規則配置：

    共分為三個段

    1 c和lex的全局聲明

        這部分放置c變量聲明、include檔案、lex的标記聲明等，文法如

        %{

        int wordCount = 0;

        %}

        chars [A-za-z\_\'\.\"]

        numbers ([0-9])+

        delim [" "\n\t]

        whitespace {delim}+

        words {chars}+

        %%

        其中，c變量聲明、include檔案放在%{%}中， %%是段的分隔符，表示該段的結束和下一段的開始

        如上chars、numbers 等被聲明為一個标記，其後是對應的比對表達式。即當比對上相應表達式的時候，該文本會被打上對應的标記

    2 模式

        文法如下：

        {words} { wordCount++; }

        {whitespace} { }

        {numbers} { }

        %%

        如上定義的規則，遇到words的時候，wordCount自增，遇到空格，則跳過，其他未定義

        沖突解決規則：

        1） 總是選擇最長的字首

        2） 如果最長的可能字首與多個模式比對，總是選擇Lex中先被列出的模式。

    3 補充的c函數，此部分可以省略

        void main()

        {

        yylex();

        printf(" No of words:

        %d\n", wordCount);

        }

        int yywrap()

        {

        return 1;

        }

yacc:

    文法分析器

    終端和非終端符号

    終端符号 : 代表一類在文法結構上等效的标記。 終端符号有三種類型：

    命名标記: 這些由 %token 辨別符來定義。 按照慣例，它們都是大寫。

    字元标記 : 字元常量的寫法與 C 相同。例如, -- 就是一個字元标記。

    字元串标記 : 寫法與 C 的字元串常量相同。例如，"<<" 就是一個字元串标記。

    lexer 傳回命名标記。

    非終端符号 : 是一組非終端符号和終端符号組成的符号。 按照慣例，它們都是小寫。 在例子中，file 是一個非終端标記而 NAME 是一個終端标記。

    規則編寫也分為三部分

    1 聲明

    2 文法規則

    3 c代碼(可省略）

lex 和 yacc一起使用

    lex和yacc共享标記的聲明

    lex來做詞法分析，根據配置的規則，傳回對應的标記

    yacc 根據lex傳回的标記定義文法規則，并根據規則進行相應的動作

參考https://www.ibm.com/developerworks/cn/linux/sdk/lex