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