精华内容
下载资源
问答
  • Lex Yacc (一) 入门
    万次阅读 多人点赞
    2016-05-23 12:11:33

    准备工作

    • 文法分析用Flex(Lex):将数据分隔成一个个的标记token (标示符identifiers,关键字keywords,数字numbers, 中括号brackets, 大括号braces, 等等etc.)
    • 语法分析用Bison(Yacc): 在分析标记的时候生成抽象语法树. Bison 将会做掉几乎所有的这些工作, 我们定义好我们的抽象语法树就OK了.
    • 组装用LLVM: 这里我们将遍历我们的抽象语法树,并未每一个节点生成字节/机器码。 这听起来似乎很疯狂,但是这几乎就是最简单的 一步了.
    • sudo apt-get install flex bison
    • flex -h && bison -h 进行测试
    • cd ~/shellscript/bin
    • gedit lexya
    • 将执行后面每一个例子时一连串的命令放进去
    • chmod u+x lexya 就像下面这样
    • ~/shellscript/bin/lexya 针对草木鱼(四五六七)和汇编版本的一个脚本
    #! /bin/bash
    name=`basename $0`
    # 针对草木鱼(四五六七)和汇编版本
    if [ $name = "lexya6" ]
    then
        bison -d lexya_e.y
        lex -d lexya_e.l
        gcc -g -o graph lex.yy.c lexya_e.tab.c liwei.c
        ./graph < treeinput
    elif [ $name = "lexya5" ]
    then
        bison -d lexya_e.y
        lex -d lexya_e.l
        gcc -g -o parser lex.yy.c lexya_e.tab.c parser.c
        ./parser < input
    elif [ $name = "lexya4" ]
    then
        bison -d lexya_e.y
        lex -d lexya_e.l
        gcc -g -o parser lex.yy.c lexya_e.tab.c parser.c
        ./parser < input
    elif [ $name = "lexya7" ]
    then
        bison -d tree.y
        lex -d tree.l
        gcc -g -c lex.yy.c tree.tab.c parser.c # 有Waring,忽略之 -c 只编译不链接
        ar -rl compile.a *.o
        # 使用静态库文件编译外部程序:
        gcc -g  -o lw main.c compile.a
        # 运行编译显示结果:
        ./lw < input
    elif [ $name = "lexyan" ]
    then
        make lex
        make yacc
        make
        ./parser < testfile/test.c > test.asm
        # nasm -f elf64 test.asm
        # ld -s -o test test.o
        as --32 -o test.o test.asm
        ld -s -m elf_i386 -o test test.o
    fi
    • ln -s lexya lexyan && ln -s lexya lexya4 && ln -s lexya lexya5 && ln -s lexya lexya6 && ln -s lexya lexya7

    一个简单的编译器 flex & bison

    • 目标编译代码
    int do_math(int a) {
      int x = a * 5 + 3
    }
    do_math(10)
    • 看起来很简单。它和C非常相似,但是它没有使用分号做语句的分隔,同时你也会注意到我们的语法中没有return语句。这就是你可以自己实现的部分。
    • 现在我们还没有任何机制来验证结果。我们将通过检查我们编译之后LLVM打印出的字节码验证我们程序的正确性。
    • 编写tokens.l 和 parser.y 去github上下载最新版,可能有错,自己读代码改正
    • bison -d -o parser.cpp parser.y
    • flex -o tokens.cpp tokens.l
    • 如果上面没有错误,你可以编译一个简单的main.cpp
    #include <iostream>
    #include "node.h"
    extern NBlock* programBlock;
    extern int yyparse();
    int main(int argc, char **argv)
    {
        yyparse();
        std::cout << programBlock << endl;
        return 0;
    }
    • g++ -o parser parser.cpp tokens.cpp main.cpp
    • 具体参见原博客:使用Flex Bison 和LLVM编写自己的编译器

    Lex

    • Lex工具是一种词法分析程序生成器,它可以根据词法规则说明书的要求来生成单词识别程序,由该程序识别出输入文本中的各个单词。 一般可以分为<定义部分><规则部分><用户子程序部分>。其中规则部分是必须的,定义和用户子程序部分是任选的。

    简单的处理Lex的例子

    • lex.l
    %{
    #include "stdio.h"
    %}
    %%
    [\t\n]                  ;
    [0-9]+                printf("Int     : %s\n",yytext);
    [0-9]*\.[0-9]+        printf("Float   : %s\n",yytext);
    [a-zA-Z][a-zA-Z0-9]*  printf("Var     : %s\n",yytext);
    [\+\-\*\/\%]          printf("Op      : %s\n",yytext);
    .                     printf("Unknown : %c\n",yytext[0]);
    %%
    • flex -o a.c lex.l
    • gcc -o a a.c -ll
    • ./a 或者 ./a file.txt
    • file.txt 如下
    title
    i=1+3.9;
    a3=909/6
    bcd=4%9-333
    • 对lex.l进行改进
    %{
    #include "stdio.h"
    int linenum;
    %}
    %%
    title                 showtitle();
    [\n]                  linenum++;
    [0-9]+                printf("Int     : %s\n",yytext);
    [0-9]*\.[0-9]+        printf("Float   : %s\n",yytext);
    [a-zA-Z][a-zA-Z0-9]*  printf("Var     : %s\n",yytext);
    [\+\-\*\/\%]          printf("Op      : %s\n",yytext);
    .                     printf("Unknown : %c\n",yytext[0]);
    %%
    showtitle()
    {
    printf("----- Lex Example -----\n");
    }
    int main()
    {
      linenum=0;
      yylex(); /* 进行分析 */
      printf("/nLine Count: %d/n",linenum);
      return 0;
    }
    int yywrap()
    {
    return 1;
    }
    • flex -o a.c lex.l
    • gcc -o a a.c 这里不加 -ll 也可以编译通过
    • ./a 或者 ./a file.txt

    -ll 参数选项

    • 当编译时不带-ll选项时,是必须加入main函数和yywrap(yywrap将下后面说明)。

    lex 内部预定义变量和函数

    • 变量
    • ytext char * 当前匹配的字符串
    • yleng int 当前匹配的字符串长度
    • yin FILE * lex当前的解析文件,默认为标准输出
    • yout FILE * lex解析后的输出文件,默认为标准输入
    • ylineno int 当前的行数信息
    • CHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字符的默认动作
    • 函数
    • nt yylex(void) 调用Lex进行词法分析
    • nt yywrap(void) 在文件(或输入)的末尾调用。如果函数的返回值是1,就停止解析。 因此它可以用来解析多个文件。代码可以写在第三段,这样可以解析多个文件。 方法是使用 yyin 文件指针指向不同的文件,直到所有的文件都被解析。最后,yywrap() 可以返回1来表示解析的结束。

    Yacc

    • yacc文法采用BNF(Backus-Naur Form)的变量规则描述。
    • 处理 1+2/3+4*6-3
        BNF文法:     优先级
        E = num      规约a    0
        E = E / E    规约b    1
        E = E * E    规约c    1
        E = E + E    规约d    2
        E = E - E    规约e    2
    • 我们将 “1+2/3+4*6-3-2”逐个字符移进堆栈,如下所示:
        0      .1+2/3+4*6-3
        1      1.+2/3+4*6-3     移进
        2      E.+2/3+4*6-3     规约a
        3      E+.2/3+4*6-3     移进
        4      E+2./3+4*6-3     移进
        5      E+E./3+4*6-3     规约a
        6      E+E/.3+4*6-3     移进
        7      E+E/3.+4*6-3     移进
        8      E+E/E.+4*6-3     规约a
        9      E+E/E+.4*6-3     移进
        10     E+E/E+4.*6-3     移进
        11     E+E/E+E.*6-3     规约a
        12     E+E/E+E*.6-3     移进
        13     E+E/E+E*6.-3     移进
        14     E+E/E+E*E.-3     规约a
        15     E+E/E+E*E-.3     移进
        16     E+E/E+E*E-3.     移进
        17     E+E/E+E*E-E.     规约a
        18     E+E+E*E-E.       规约b
        19     E+E+E-E.         规约c
        20     E+E-E.           规约d
        21     E-E.             规约d
        22     E.               规约e
    • 我们在实际运算操作中是把一个表达式逐步简化成一个非终结符。称之为“自底向上”或者“移进归约”的分析法
    • 在第1步中我们把1压入堆栈中。第2步对应规则a,把1转换成E。然后继续压入和归约,直到第5步。此时堆栈中剩下E+E,按照规则d,可以进行E=E+E的合并,然而输入信息并没有结束,这就产生了“移进-归约”冲突(shift-reduce conflict)。在yacc中产生这种冲突时,会继续移进
    • 在第17步,E+E/E,即可以采用E+E规则d,也可以采用E/E规则b,如果使用E=E+E规约,显然从算法角度是错误的,这就有了运算符的优先级概念。这种情况称为“归约-归约”冲突(reduce-reduce conflict)。此时yacc会采用第一条规则,即E=E/E。这个内容会在后面的实例做进一步深化

    小计算器 lex && yacc 对应于草木鱼 (二)

    我的理解

    • 维护者两个栈,内容栈和分析栈
    • 在.l文件的词法分析时,进行一次压栈,例如:[0-9]+ { yylval = atoi(yytext); return INTEGER; }
    • yylval = atoi(yytext); 是将yylval的值压入内容栈
    • return INTEGER; 是将INTEGER对应的数字压入分析栈
    • .l的结果传给了.y文件,yacc再次进行压栈 但是这次压栈不一定是紧接着.l进行的,因为会有移近-移近冲突和移近-规约冲突
    • 例如:expr: INTEGER { $$ = $1; }
    • expr: INTEGER 是将INTEGER从分析栈弹出,压入expr
    • { $$ = $1; } 是将INTEGER 对应的内容栈中的值弹出,并赋值给expr对应的yyval,同时压入内容栈

    lexya_a.l

    • lexya_a.l
    %{
    #include <stdlib.h>
    void yyerror(char *);
    #include "lexya_a.tab.h"
    %}
    %%
    [0-9]+       { yylval = atoi(yytext); return INTEGER; }
    [-+*/\n]     return *yytext;
    [/t]         ;/* 去除空格 */
    .            yyerror("无效字符");
    %%
    int yywrap(void) {
      return 1;
    }

    lexya_a.y

    • lexya_a.y
    %{
    #include <stdlib.h>
    #include <stdio.h>
    int yylex(void);
    void yyerror(char *);
    %}
    %token INTEGER
    %left '+' '-'
    %left '*' '/'
    %%
    program:
    program expr '\n' { printf("%d\n", $2); }
    |
    ; /* 先理解expr,再递归理解program。首先program可以为空,也可以用单单的expr加下“/n”回车符组成,结合起来看program定义的就是多个表达式组成的文件内容 */
    expr:
    INTEGER { $$ = $1; }
    | expr '*' expr { $$ = $1 * $3; }
    | expr '/' expr { $$ = $1 / $3; }
    | expr '+' expr { $$ = $1 + $3; }
    | expr '-' expr { $$ = $1 - $3; }
    ; /* 可以由单个INTEGER值组成,也可以有多个INTERGER和运算符组合组成。以表达式“1+4/2*3-0”为例,1 4 2 3 都是expr,就是expr+expr/expr*expr-expr说到底最后还是个expr。递归思想正好与之相反,逆推下去会发现expr这个规则标记能表示所有的数值运算表达式 */
    %%
    void yyerror(char *s) {
      printf("%s\n", s);
    }
    int main(void) {
      yyparse();
      return 0;
    }
    • bison -d lexya_a.y 参数 -d 将头文件和.c文件分离
    • lex lexya_a.l
    • cc -o parser *.c
    • ./parser 输入计算式,回车会显示运行结果
    • bison -d lexya_a.y 编译后会产生 lexya_a.tab.c lexya_a.tab.h
    • lex文件lexya_a.l中头声明已包括了 lexya_a.tab.h。这两个文件是典型的互相协作的示例
    • 详细分析见 草木鱼系列的第二篇

    yacc 堆栈原理

    %}
    %token INTEGER
    %left '+' '-'
    %left '*' '/'
    %%
    • %}和%%这一段可以看作预定义标记部分。%token INTEGER 定义声明了一个标记。
    • 当我们编译后,它会在lexya_a.tab.c中生成一个剖析器,同时会在lexya_a.tab.h
    • 产生包含信息:
    # define INTEGER 257
    其中0-255的之间的标记值约定为字符值,是系统保留的后定义的token。
    lexya_a.tab.h其它部分是默认生成的,与token INTEGER无关。
    # ifndef YYSTYPE
    #  define YYSTYPE int
    #  define YYSTYPE_IS_TRIVIAL 1
    # endif
    extern YYSTYPE yylval;
    • lex文件需要包含lexya_a.tab.h这个头文件,并且使用其中对标记值的定义。为了获得标记,yacc会调用yylex。yylex的返回值类型是整型,可以用于返回标记。而在yylval变量中保存着与返回的标记相对应的值
    • yacc在内部维护着两个堆栈,一个分析栈和一个内容栈。分析栈中保存着终结符和非终结符,并且记录了当前剖析状态。而内容栈是一个YYSTYPE类型的元素数组,对于分析栈中的每一个元素都保存着一个对应的值。例如,当yylex返回一个INTEGER标记时,把这个标记移入分析栈。同时,相应的yacc值将会被移入内容栈中。分析栈和内容栈的内容总是同步的,因此从栈中找到对应的标记值是很容易的。
    • 比如lex文件中下面这一段:
    [0-9]+       { yylval = atoi(yytext); return INTEGER; }
    • 这是将把整数的值保存在yylval中,同时向yacc返回标记INTEGER。即内容栈存在了整数的值,对应的分析栈就为INTEGER标记了。yylval类型由YYSTYPE决定,由于它的默认类型是整型,所以在这个例子中程序运行正常。
    • lex文件还有一段:
    [-+*//n]     return *yytext;
    • 这里显然只是向yacc的分析栈返回运算符标记,系统保留的0-255此时便有了作用,内容栈为空。把“-”放在第一位是防止正则表达式发现类似a-z的歧义。
    • 再看下面的:
    %left '+' '-'
    %left '*' '/'
    • %left 表示左结合,%right 表示右结合。最后列出的定义拥有最高的优先权。因此乘法和除法拥有比加法和减法更高的优先权。+ - * / 所有这四个算术符都是左结合的。运用这个简单的技术,我们可以消除文法的歧义。
    • 粗略有了概念之后,再看lex如何执行相应的行为。
    • 以expr: expr ‘+’ expr { $$ = $1 + $3; }为例
    • 在分析栈中我们其实用左式替代了右式。在本例中,我们弹出“ expr ‘+’ expr ”然后压入“expr”。我们通过弹出三个成员,压入一个成员来缩小堆栈。在我们的代码中可以看到用相对地址访问内容栈中的值。如1,2,这样都是yacc预定义可以直接使用的标记。“1”代表右式中的第一个成员,“2”代表第二个,后面的以此类推。“$$”表示缩小后的堆栈顶部。在上面的动作中,把对应两个表达式的值相加,弹出内容栈中的三个成员,然后把得到的和压入堆栈中。这样,保持分析栈和内容栈中的内容依然同步。
    • program:
    • program expr ‘\n’ { printf(“%d\n”, $2); }
    • 说明每当一行表达式结束时,打印出第二个栈值,即expr的值,完成字符运算。

    计算器升级版 ()运算符 变量保存 lex && yacc 对应于草木鱼 (三)

    lexya_b.l

    • lexya_b.l
    %{
    #include <stdlib.h>
    #include "lexya_b.tab.h"
    void yyerror(char *);
    void add_buff(char *);
    extern char sBuff[10][20];
    extern int iX;
    extern int iY;
    %}
    %%
    [a-z]         { yylval = *yytext; add_buff(yytext); return VAR; }
    [0-9]+        { yylval = atoi(yytext); add_buff(yytext); return INT; }
    [-+()=*/]     { yylval = *yytext; add_buff(yytext); return *yytext; }
    [\n]          { yylval = *yytext; iY=0;iX++; return *yytext; }
    [\t]          ;
    .             yyerror("无效字符");
    %%
    void add_buff(char * buff) {
        sBuff[iX][iY]=*buff; iY++;
    }
    int yywrap(void) {
        return 1;
    }

    lexya_b.y

    • lexya_b.y
    %{
    #include <stdlib.h>
    int yylex(void);
    void yyerror(char *);
    void debuginfo(char *, int *, char *);
    void printinfo();
    int sMem[256];
    char sBuff[10][20]={0};
    int iX=0;
    int iY=0;
    %}
    %token INT VAR
    %left '+' '-'
    %left '*' '/'
    %%
    program:
    program statement
    |
    ;
    statement:
    expr { printf("%d\n",$1); }
    | VAR '=' expr { debuginfo("=",yyvsp,"110"); sMem[$1]=$3; }
    | statement '\n' { printf("--------------------------------\n\n"); }
    ;
    expr:
    INT { debuginfo("INT",yyvsp,"0"); $$ = $1; }
    | VAR { debuginfo("VAR",yyvsp,"1"); $$ = sMem[$1]; }
    | expr '*' expr { debuginfo("*",yyvsp,"010"); $$ = $1 * $3; }
    | expr '/' expr { debuginfo("/",yyvsp,"010"); $$ = $1 / $3; }
    | expr '+' expr { debuginfo("+",yyvsp,"010"); $$ = $1 + $3; }
    | expr '-' expr { debuginfo("-",yyvsp,"010"); $$ = $1 - $3; }
    | '(' expr ')'   { debuginfo("()",yyvsp,"101"); $$ = $2; }
    ;
    %%
    void debuginfo(char * info,int * vsp, char * mark) {
        printf("--RULE: %s \n", info);
        int i=0;
        int ilen=strlen(mark);
        for(i=0;i>=1-ilen;i--) {
        if(mark[ilen+i-1]=='1')
            printf("$%d %d %c \n", i+ilen, vsp[i], vsp[i]);
        else
            printf("$%d %d \n", i+ilen, vsp[i]);
        }
        printinfo();
    }
    void printinfo() {
        int i=0;
        printf("--STATEMENT: \n");
    
        if(iY==0)
            printf("%s \n",sBuff[iX-1]);
        else
            printf("%s \n",sBuff[iX]);
        printf("\n");
    }
    void yyerror(char *s) {
        printf("%s\n", s);
    }
    int main(void) {
        yyparse();
        return 0;
    }

    input

    • input 编译文本
    a=4+2*(3-2-1)+6
    b=1-10/(6+4)+8
    c=a-b
    a
    b
    c
    • bison -d lexya_b.y
    • lex lexya_b.l
    • gcc -g -o parser lex.yy.c lexya_b.tab.c 参数-g是调试选项
    • ./parser < input

    上面的计算器升级版分析

    • 这里只是做了一些扩充变化:
    • 1.增加了全局数组sMem来存放变量,不过变量名有限制,只支持单字符。
    • 2.增加了全局数组sBuff存放分析过的语句
    • 3.增加debuginfo打印堆栈信息
    • 4.增加printinfo打印目前的分析语句
    • 要进行内部分析,就需要剖析生成的c文件,对程序(parser)进行跟踪调试。
    • (注:Lex编译时加上d参数,会在程序解释时输出详细的调试信息。如:lex -d lexya_$1.l)
    • 通过本示例再加上实际对lexya_b.tab.c的分析理解,会对lex,yacc理论有更进一步的理解。

    增加支持的变量字符数,根据运行结果精读下面的源代码 草木鱼(三)

    • 上面的例子只支持单字符的变量,想支持多字符,需要定义一全局变量如:
    struct varIndex
    {
        int iValue;
        char sMark[10];
    };
    • 同时打印信息加入对变量的显示,下面列出全部文件内容,比较简单,不再附加说明。
    • 下面是需要的四个文件

    userdef.h

    • 头文件 userdef.h
    typedef struct {
        int iValue; //存放的是标识符b被赋予的数值
        char sMark[10]; //存放的是标识符的字符串
    } varIndex;
    varIndex strMem[256];

    lexya_c.l

    • lexya_c.l
    %{
    #include <stdlib.h>
    #include "userdef.h"
    #include "lexya_c.tab.h"
    
    void yyerror(char *);
    void add_buff(char *);
    void add_var(char *);
    
    extern char sBuff[10][20]; //引用其他地方定义的sBuff,存放源代码
    extern int iBuffX; //源代码第几行
    extern int iBuffY; //源代码第几列
    
    extern varIndex strMem[256]; //存放标识符
    extern int iMaxIndex; //标识符的个数
    extern int iCurIndex; //当前指向第几个标识符
    %}
    %%
    [a-zA-Z][a-zA-Z0-9]*         { add_var(yytext); yylval = iCurIndex; add_buff(yytext);   return VAR; }
    [0-9]+        { yylval = atoi(yytext); add_buff(yytext); return INT;   }
    [-+()=*/]     { yylval = *yytext; add_buff(yytext); return *yytext; }
    [\n]          { yylval = *yytext; iBuffY=0;iBuffX++; return *yytext; }
    [\t]          ;
    .             yyerror("无效字符");
    %%
    void add_buff(char * buff) {
        strcat(sBuff[iBuffX],buff);
        iBuffY+=strlen(buff);
    }
    void add_var(char *mark) {
        if(iMaxIndex==0){
            strcpy(strMem[0].sMark,mark);
            iMaxIndex++;
            iCurIndex=0;
            return;
        }
        int i;
        for(i=0;i<=iMaxIndex-1;i++) {
            if(strcmp(strMem[i].sMark,mark)==0) {
                iCurIndex=i;
                return;
            }
        }
        strcpy(strMem[iMaxIndex].sMark,mark);
        iCurIndex=iMaxIndex;
        iMaxIndex++;
    }
    int yywrap(void) {
        return 1;
    }

    lexya_c.y

    • lexya_c.y
    %{
    #include <stdlib.h>
    #include "userdef.h"
    int yylex(void);
    void yyerror(char *);
    void debug_info(char *, int *, char *);
    void stm_info();
    
    extern varIndex strMem[256];
    
    int iMaxIndex=0;
    int iCurIndex=0;
    
    char sBuff[10][20]={0};
    int iBuffX=0;
    int iBuffY=0;
    
    %}
    %token INT VAR //token表示终结符
    %left '+' '-' //left表示左结合
    %left '*' '/' //再后面的优先级比较高
    %%
    program:
    program statement
    |
    ;
    statement:
    expr { printf("%d\n",$1); }
    | VAR '=' expr { debug_info("=",yyvsp,"210"); strMem[$1].iValue=$3;   }
    | statement '\n' { printf("--------------------------------\n\n"); }
    ;
    expr:
    INT { debug_info("INT",yyvsp,"0"); $$ = $1;   }
    | VAR { debug_info("VAR",yyvsp,"2"); $$ =   strMem[$1].iValue; }
    | expr '*' expr { debug_info("*",yyvsp,"010"); $$ = $1 * $3; }
    | expr '/' expr { debug_info("/",yyvsp,"010"); $$ = $1 / $3; }
    | expr '+' expr { debug_info("+",yyvsp,"010"); $$ = $1 + $3; }
    | expr '-' expr { debug_info("-",yyvsp,"010"); $$ = $1 - $3; }
    | '(' expr ')'   { debug_info("()",yyvsp,"101"); $$ = $2;      }
    ;
    %%
    void debug_info(char * info,int * vsp, char * mark) {
        printf("--RULE: %s \n", info);
        int i=0;
        int ilen=strlen(mark);
        for(i=0;i>=1-ilen;i--) {
            switch(mark[ilen+i-1]){
                case '1':
                    printf("$%d %d %c \n", i+ilen, vsp[i], vsp[i]);
                    break;
                case '0':
                    printf("$%d %d \n", i+ilen, vsp[i]);
                    break;
                case '2':
                    printf("$%d %s %d\n", i+ilen, strMem[vsp[i]].sMark, strMem[vsp[i]].iValue);
                    break;
            }
        }
        stm_info();
    
    }
    void stm_info() {
        int i=0;
        printf("--STATEMENT: \n");
        if(iBuffY==0)
            printf("%s \n",sBuff[iBuffX-1]);
        else
            printf("%s \n",sBuff[iBuffX]);
        printf("\n");
    }
    void yyerror(char *s) {
        printf("%s\n", s);
    }
    int main(void) {
        yyparse();
        return 0;
    }

    input

    • input
    aa=4+2*(3-2-1)+6
    bb=1-10/(6+4)+8
    cd=aa-bb
    aa
    bb
    cd
    • bison -d lexya_c.y
    • lex -d lexya_c.l //-d是打印调试信息
    • gcc -g -o parser lex.yy.c lexya_c.tab.c //参数-g是调试选项,这里可能会报Warning
    • ./parser < input
    更多相关内容
  • 如果你从事编译器或解析器的开发工作,你可能对lexyacc不会陌生,是David Beazley实现的基于Python的lexyacc。作者最著名的成就可能是其撰写的Python Cookbook, 3rd Edition。我因为偶然的原因接触了PLY,觉得是...
  • lex yacc for windows

    2017-11-19 20:47:09
    非常好用的windows下的yacc 和 flex工具 非常好用的windows下的yacc 和 flex工具 非常好用的windows下的yacc 和 flex工具 说三遍哟
  • LexYacc教程

    2014-04-02 23:51:34
    包含教程呢,还有工具
  • LEXYACC第二版中文版。LEX是词法分析工具,YACC是语法分析工具,使用这两个工具可以编写编译器等。
  • Python Lex Yacc手册

    千次阅读 多人点赞 2020-02-23 22:22:46
    本文是PLY (Python Lex-Yacc)的中文翻译版。转载请注明出处。 如果你从事编译器或解析器的开发工作,你可能对lexyacc不会陌生,PLY是David Beazley实现的基于Python的lexyacc。作者最著名的成就可能是其撰写的...

    本文是PLY (Python Lex-Yacc)的中文翻译版。转载请注明出处。

    如果你从事编译器或解析器的开发工作,你可能对lex和yacc不会陌生,PLY是David Beazley实现的基于Python的lex和yacc。作者最著名的成就可能是其撰写的Python Cookbook, 3rd Edition。我因为偶然的原因接触了PLY,觉得是个好东西,但是似乎国内没有相关的资料。于是萌生了翻译的想法,虽然内容不算多,但是由于能力有限,很多概念不了解,还专门补习了编译原理,这对我有很大帮助。为了完成翻译,经过初译,复审,排版等,花费我很多时间,最终还是坚持下来了,希望对需要的人有所帮助。另外,第一次大规模翻译英文,由于水平有限,如果错误或者不妥的地方还请指正,非常感谢。

    一些翻译约定

    英文翻译
    token标记
    context free grammar上下文无关文法
    syntax directed translation语法制导的翻译
    ambiguity二义
    terminals终结符
    non-terminals非终结符
    documentation string文档字符串(python中的_docstring_)
    shift-reduce移进-归约
    Empty Productions空产生式
    Panic mode recovery悲观恢复模式

    1 前言和预备

    本文指导你使用PLY进行词法分析和语法解析的,鉴于解析本身是个复杂性的事情,在你使用PLY投入大规模的开发前,我强烈建议你完整地阅读或者浏览本文档。

    PLY-3.0能同时兼容Python2和Python3。需要注意的是,对于Python3的支持是新加入的,还没有广泛的测试(尽管所有的例子和单元测试都能够在Pythone3下通过)。如果你使用的是Python2,应该使用Python2.4以上版本,虽然,PLY最低能够支持到Python2.2,不过一些可选的功能需要新版本模块的支持。

    2 介绍

    PLY是纯粹由Python实现的Lex和yacc (流行的编译器构建工具)。PLY的设计目标是尽可能的沿袭传统lex和yacc工具的工作方式,包括支持LALR(1)分析法、提供丰富的输入验证、错误报告和诊断。因此,如果你曾经在其他编程语言下使用过yacc,你应该能够很容易的迁移到PLY上。

    2001年,我在芝加哥大学教授“编译器简介”课程时开发了的早期的PLY。学生们使用Python和PLY构建了一个类似Pascal的语言的完整编译器,其中的语言特性包括:词法分析、语法分析、类型检查、类型推断、嵌套作用域,并针对SPARC处理器生成目标代码等。最终他们大约实现了30种不同的编译器!PLY在接口设计上影响使用的问题也被学生们所提出。从2001年以来,PLY继续从用户的反馈中不断改进。为了适应对未来的改进需求,PLY3.0在原来基础上进行了重大的重构。

    由于PLY是作为教学工具来开发的,你会发现它对于标记和语法规则是相当严谨的,这一定程度上是为了帮助新手用户找出常见的编程错误。不过,高级用户也会发现这有助于处理真实编程语言的复杂语法。还需要注意的是,PLY没有提供太多花哨的东西(例如,自动构建抽象语法树和遍历树),我也不认为它是个分析框架。相反,你会发现它是一个用Python实现的,基本的,但能够完全胜任的lex/yacc。

    本文的假设你多少熟悉分析理论、语法制导的翻译、基于其他编程语言使用过类似lex和yacc的编译器构建工具。如果你对这些东西不熟悉,你可能需要先去一些书籍中学习一些基础,比如:Aho, Sethi和Ullman的《Compilers: Principles, Techniques, and Tools》(《编译原理》),和O’Reilly’出版的John Levine的《lex and yacc》。事实上,《lex and yacc》和PLY使用的概念几乎相同。

    3 PLY概要

    PLY包含两个独立的模块:lex.py和yacc.py,都定义在ply包下。lex.py模块用来将输入字符通过一系列的正则表达式分解成标记序列yacc.py通过一些上下文无关的文法来识别编程语言语法。yacc.py使用LR解析法,并使用LALR(1)算法(默认)或者SLR算法生成分析表。

    这两个工具是为了一起工作的。lex.py通过向外部提供token()方法作为接口,方法每次会从输入中返回下一个有效的标记。yacc.py将会不断的调用这个方法来获取标记并匹配语法规则。yacc.py的的功能通常是生成抽象语法树(AST),不过,这完全取决于用户,如果需要,yacc.py可以直接用来完成简单的翻译。

    就像相应的unix工具,yacc.py提供了大多数你期望的特性,其中包括:丰富的错误检查、语法验证、支持空产生式、错误的标记、通过优先级规则解决二义性。事实上,传统yacc能够做到的PLY都应该支持。

    yacc.py与Unix下的yacc的主要不同之处在于,yacc.py没有包含一个独立的代码生成器,而是在PLY中依赖反射来构建词法分析器和语法解析器。不像传统的lex/yacc工具需要一个独立的输入文件,并将之转化成一个源文件,Python程序必须是一个可直接可用的程序,这意味着不能有额外的源文件和特殊的创建步骤(像是那种执行yacc命令来生成Python代码)。又由于生成分析表开销较大,PLY会缓存生成的分析表,并将它们保存在独立的文件中,除非源文件有变化,会重新生成分析表,否则将从缓存中直接读取。

    4 Lex

    lex.py是用来将输入字符串标记化。例如,假设你正在设计一个编程语言,用户的输入字符串如下:

    x = 3 + 42 * (s - t)
    

    标记器将字符串分割成独立的标记:

    'x','=', '3', '+', '42', '*', '(', 's', '-', 't', ')
    

    标记通常用一组名字来命名和表示:

    'ID','EQUALS','NUMBER','PLUS','NUMBER','TIMES','LPAREN','ID','MINUS','ID','RPAREN'
    

    将标记名和标记值本身组合起来:

    ('ID','x'),('EQUALS','='),('NUMBER','3'),('PLUS','+'), ('NUMBER','42),('TIMES','*'),('LPAREN','('), ('ID','s'),('MINUS','-'),('ID','t'), ('RPAREN',')
    

    正则表达式是描述标记规则的典型方法,下一节展示如何用lex.py实现。

    4.1 Lex的例子

    下面的例子展示了如何使用lex.py对输入进行标记

    # -----------------------------------------------------------
    # calclex.py
    #
    # tokenizer for a simple expression evaluator for
    # numbers and +,-,*,/
    # ------------------------------------------------------------
    import ply.lex as lex
    
    # List of token names.   This is always required
    tokens = (
       'NUMBER',
       'PLUS',
       'MINUS',
       'TIMES',
       'DIVIDE',
       'LPAREN',
       'RPAREN',
    )
    
    # Regular expression rules for simple tokens
    t_PLUS    = r'\+'
    t_MINUS   = r'-'
    t_TIMES   = r'\*'
    t_DIVIDE  = r'/'
    t_LPAREN  = r'\('
    t_RPAREN  = r'\)'
    
    # A regular expression rule with some action code
    def t_NUMBER(t):
        r'\d+'
        t.value = int(t.value)    
        return t
    
    # Define a rule so we can track line numbers
    def t_newline(t):
        r'\n+'
        t.lexer.lineno += len(t.value)
    
    # A string containing ignored characters (spaces and tabs)
    t_ignore  = ' \t'
    
    # Error handling rule
    def t_error(t):
        print "Illegal character '%s'" % t.value[0]
        t.lexer.skip(1)
    
    # Build the lexer
    lexer = lex.lex()
    

    为了使lexer工作,你需要给定一个输入,并传递给input()方法。然后,重复调用token()方法来获取标记序列,下面的代码展示了这种用法:

    # Test it out
    data = '''
    3 + 4 * 10
      + -20 *2
    '''
    
    # Give the lexer some input
    lexer.input(data)
    
    # Tokenize
    while True:
        tok = lexer.token()
        if not tok: break      # No more input
        print tok
    

    程序执行,将给出如下输出:

    $ python example.py
    LexToken(NUMBER,3,2,1)
    LexToken(PLUS,'+',2,3)
    LexToken(NUMBER,4,2,5)
    LexToken(TIMES,'*',2,7)
    LexToken(NUMBER,10,2,10)
    LexToken(PLUS,'+',3,14)
    LexToken(MINUS,'-',3,16)
    LexToken(NUMBER,20,3,18)
    LexToken(TIMES,'*',3,20)
    LexToken(NUMBER,2,3,21)
    

    Lexers也同时支持迭代,你可以把上面的循环写成这样:

    for tok in lexer:
        print tok
    

    lexer.token()方法返回的标记是LexToken类型的实例,拥有tok.type,tok.value,tok.linenotok.lexpos属性,下面的代码展示了如何访问这些属性:

    # Tokenize
    while True:
        tok = lexer.token()
        if not tok: break      # No more input
        print tok.type, tok.value, tok.line, tok.lexpos
    

    tok.type和tok.value属性表示标记本身的类型和值。tok.line和tok.lexpos属性包含了标记的位置信息tok.lexpos表示标记相对于输入串起始位置的偏移。

    4.2 标记列表

    词法分析器必须提供一个标记的列表,这个列表将所有可能的标记告诉分析器,用来执行各种验证,同时也提供给yacc.py作为终结符。

    在上面的例子中,是这样给定标记列表的:

    tokens = (
       'NUMBER',
       'PLUS',
       'MINUS',
       'TIMES',
       'DIVIDE',
       'LPAREN',
       'RPAREN',
    )
    

    4.3 标记的规则

    每种标记用一个正则表达式规则来表示每个规则需要以”t_“开头声明表示该声明是对标记的规则定义。对于简单的标记,可以定义成这样(在Python中使用raw string能比较方便的书写正则表达式):

    t_PLUS = r'\+'
    

    这里,紧跟在t_后面的单词,必须跟标记列表中的某个标记名称对应. 如果需要执行动作的话,规则可以写成一个方法。例如,下面的规则匹配数字字串,并且将匹配的字符串转化成Python的整型:

    def t_NUMBER(t):
        r'\d+'
        t.value = int(t.value)
        return t
    

    如果使用方法的话,正则表达式写成方法的文档字符串。方法总是需要接受一个LexToken实例的参数,该实例有一个t.type的属性(字符串表示)来表示标记的类型名称t.value是标记(匹配的实际的字符串),t.lineno表示当前在源输入串中的作业行t.lexpos表示标记相对于输入串起始位置的偏移。默认情况下,t.type是以t_开头的变量或方法的后面部分。方法可以在方法体里面修改这些属性。但是,如果这样做,应该返回结果token,否则,标记将被丢弃。

    在lex内部,lex.py用re模块处理模式匹配,在构造最终的完整的正则式的时候,用户提供的规则按照下面的顺序加入:

    所有由方法定义的标记规则,按照他们的出现顺序依次加入
    由字符串变量定义的标记规则按照其正则式长度倒序后,依次加入(长的先入)
    顺序的约定对于精确匹配是必要的。比如,如果你想区分‘=’和"= =", 你需要确保"==" 优先检查. 如果用字符串来定义这样的表达式的话,通过将较长的正则式先加入,可以帮助解决这个问题。用方法定义标记,可以显示地控制哪个规则优先检查。
    为了处理保留字,你应该写一个单一的规则来匹配这些标识,并在方法里面作特殊的查询:

    reserved = {
       'if' : 'IF',
       'then' : 'THEN',
       'else' : 'ELSE',
       'while' : 'WHILE',
       ...
    }
    
    tokens = ['LPAREN','RPAREN',...,'ID'] + list(reserved.values())
    
    def t_ID(t):
        r'[a-zA-Z_][a-zA-Z_0-9]*'
        t.type = reserved.get(t.value,'ID')    # Check for reserved words
        return t
    

    这样做可以大大减少正则式的个数,并稍稍加快处理速度。注意:你应该避免为保留字编写单独的规则,例如,如果你像下面这样写:

    t_FOR   = r'for'
    t_PRINT = r'print'
    

    但是,这些规则照样也能够匹配以这些字符开头的单词,比如’forget’或者’printed’,这通常不是你想要的。

    4.4 标记的值

    标记被lex返回后,它们的值被保存在value属性中。正常情况下,value是匹配的实际文本。事实上,value可以被赋为任何Python支持的类型。例如,当扫描到标识符的时候,你可能不仅需要返回标识符的名字,还需要返回其在符号表中的位置,可以像下面这样写:

    def t_ID(t):
        ...
        # Look up symbol table information and return a tuple
        t.value = (t.value, symbol_lookup(t.value))
        ...
        return t
    

    需要注意的是,不推荐用其他属性来保存值,因为yacc.py模块只会暴露出标记的value属性,访问其他属性会变得不自然。如果想保存多种属性,可以将元组、字典、或者对象实例赋给value。

    4.5 丢弃标记

    想丢弃像注释之类的标记,只要不返回value就行了,像这样:

    def t_COMMENT(t):
        r'\#.*'
        pass
        # No return value. Token discarded
    

    为标记声明添加”ignore_“前缀同样可以达到目的

    t_ignore_COMMENT = r'\#.*'
    

    如果有多种文本需要丢弃,建议使用方法来定义规则,因为方法能够提供更精确的匹配优先级控制(方法根据出现的顺序,而字符串的正则表达式依据正则表达式的长度)

    4.6 行号和位置信息

    默认情况下,lex.py对行号一无所知。因为lex.py根本不知道何为”行”的概念(换行符本身也作为文本的一部分)。不过,可以通过写一个特殊的规则来记录行号:

    # Define a rule so we can track line numbers
    def t_newline(t):
        r'\n+'
        t.lexer.lineno += len(t.value)
    

    在这个规则中,当前lexer对象t.lexer的lineno属性被修改了,而且空行被简单的丢弃了,因为没有任何的返回。

    lex.py也不自动做列跟踪。但是,位置信息被记录在了每个标记对象的lexpos属性中,这样,就有可能来计算列信息了。例如:每当遇到新行的时候就重置列值:

    # Compute column. 
    #     input is the input text string
    #     token is a token instance
    def find_column(input,token):
        last_cr = input.rfind('\n',0,token.lexpos)
        if last_cr < 0:
            last_cr = 0
        column = (token.lexpos - last_cr) + 1
        return column
    

    通常,计算列的信息是为了指示上下文的错误位置,所以只在必要时有用。

    4.7 忽略字符

    t_ignore规则比较特殊,是lex.py所保留用来忽略字符的,通常用来跳过空白或者不需要的字符。虽然可以通过定义像t_newline()这样的规则来完成相同的事情,不过使用t_ignore能够提供较好的词法分析性能,因为相比普通的正则式,它被特殊化处理了。

    4.8 字面字符

    字面字符可以通过在词法模块中定义一个literals变量做到,例如:

    literals = [ '+','-','*','/' ]
    

    或者:

    literals = "+-*/"
    

    字面字符是指单个字符,表示把字符本身作为标记,标记的type和value都是字符本身。不过,字面字符是在其他正则式之后被检查的,因此如果有规则是以这些字符开头的,那么这些规则的优先级较高。

    4.9 错误处理

    最后,在词法分析中遇到非法字符时,t_error()用来处理这类错误。这种情况下,t.value包含了余下还未被处理的输入字串,在之前的例子中,错误处理方法是这样的:

    # Error handling rule
    def t_error(t):
        print "Illegal character '%s'" % t.value[0]
        t.lexer.skip(1)
    

    这个例子中,我们只是简单的输出不合法的字符,并且通过调用t.lexer.skip(1)跳过一个字符。

    4.10 构建和使用lexer

    函数lex.lex()使用Python的反射机制读取调用上下文中的正则表达式,来创建lexer。lexer一旦创建好,有两个方法可以用来控制lexer对象:

    lexer.input(data) 重置lexer和输入字串
    lexer.token() 返回下一个LexToken类型的标记实例,如果进行到输入字串的尾部时将返回None
    推荐直接在lex()函数返回的lexer对象上调用上述接口,尽管也可以向下面这样用模块级别的lex.input()和lex.token():

    lex.lex()
    lex.input(sometext)
    while 1:
        tok = lex.token()
        if not tok: break
        print tok
    

    在这个例子中,lex.input()和lex.token()是模块级别的方法,在lex模块中,input()和token()方法绑定到最新创建的lexer对象的对应方法上。最好不要这样用,因为这种接口可能不知道在什么时候就失效(译者注:垃圾回收?)

    4.11 @TOKEN装饰器

    在一些应用中,你可能需要定义一系列辅助的记号来构建复杂的正则表达式,例如:

    digit            = r'([0-9])'
    nondigit         = r'([_A-Za-z])'
    identifier       = r'(' + nondigit + r'(' + digit + r'|' + nondigit + r')*)'        
    
    def t_ID(t):
        # want docstring to be identifier above. ?????
        ...
    

    在这个例子中,我们希望ID的规则引用上面的已有的变量。然而,使用文档字符串无法做到,为了解决这个问题,你可以使用@TOKEN装饰器:

    from ply.lex import TOKEN
    
    @TOKEN(identifier)
    def t_ID(t):
        ...
    

    装饰器可以将identifier关联到t_ID()的文档字符串上以使lex.py正常工作,一种等价的做法是直接给文档字符串赋值:

    def t_ID(t):
        ...
    
    t_ID.__doc__ = identifier
    

    注意:@TOKEN装饰器需要Python-2.4以上的版本。如果你在意老版本Python的兼容性问题,使用上面的等价办法。

    4.12 优化模式

    为了提高性能,你可能希望使用Python的优化模式(比如,使用-o选项执行Python)。然而,这样的话,Python会忽略文档字串,这是lex.py的特殊问题,可以通过在创建lexer的时候使用optimize选项:

    lexer = lex.lex(optimize=1)
    

    接着,用Python常规的模式运行,这样,lex.py会在当前目录下创建一个lextab.py文件,这个文件会包含所有的正则表达式规则和词法分析阶段的分析表。然后,lextab.py可以被导入用来构建lexer。这种方法大大改善了词法分析程序的启动时间,而且可以在Python的优化模式下工作。

    想要更改生成的文件名,使用如下参数:

    lexer = lex.lex(optimize=1,lextab=“footab”)

    在优化模式下执行,需要注意的是lex会被禁用大多数的错误检查。因此,建议只在确保万事俱备准备发布最终代码时使用。

    4.13 调试

    如果想要调试,可以使lex()运行在调试模式:

    lexer = lex.lex(debug=1)
    

    这将打出一些调试信息,包括添加的规则、最终的正则表达式和词法分析过程中得到的标记。

    除此之外,lex.py有一个简单的主函数,不但支持对命令行参数输入的字串进行扫描,还支持命令行参数指定的文件名:

    if __name__ == '__main__':
         lex.runmain()
    

    4.14 其他方式定义词法规则

    上面的例子,词法分析器都是在单个的Python模块中指定的。如果你想将标记的规则放到不同的模块,使用module关键字参数。例如,你可能有一个专有的模块,包含了标记的规则:

    # module: tokrules.py
    # This module just contains the lexing rules
    
    # List of token names.   This is always required
    tokens = (
       'NUMBER',
       'PLUS',
       'MINUS',
       'TIMES',
       'DIVIDE',
       'LPAREN',
       'RPAREN',
    )
    
    # Regular expression rules for simple tokens
    t_PLUS    = r'\+'
    t_MINUS   = r'-'
    t_TIMES   = r'\*'
    t_DIVIDE  = r'/'
    t_LPAREN  = r'\('
    t_RPAREN  = r'\)'
    
    # A regular expression rule with some action code
    def t_NUMBER(t):
        r'\d+'
        t.value = int(t.value)    
        return t
    
    # Define a rule so we can track line numbers
    def t_newline(t):
        r'\n+'
        t.lexer.lineno += len(t.value)
    
    # A string containing ignored characters (spaces and tabs)
    t_ignore  = ' \t'
    
    # Error handling rule
    def t_error(t):
        print "Illegal character '%s'" % t.value[0]
        t.lexer.skip(1)
    

    现在,如果你想要从不同的模块中构建分析器,应该这样(在交互模式下):

    >>> import tokrules
    >>> lexer = lex.lex(module=tokrules)
    >>> lexer.input("3 + 4")
    >>> lexer.token()
    LexToken(NUMBER,3,1,1,0)
    >>> lexer.token()
    LexToken(PLUS,'+',1,2)
    >>> lexer.token()
    LexToken(NUMBER,4,1,4)
    >>> lexer.token()
    None
    

    module选项也可以指定类型的实例,例如:

    import ply.lex as lex
    
    class MyLexer:
        # List of token names.   This is always required
        tokens = (
           'NUMBER',
           'PLUS',
           'MINUS',
           'TIMES',
           'DIVIDE',
           'LPAREN',
           'RPAREN',
        )
    
        # Regular expression rules for simple tokens
        t_PLUS    = r'\+'
        t_MINUS   = r'-'
        t_TIMES   = r'\*'
        t_DIVIDE  = r'/'
        t_LPAREN  = r'\('
        t_RPAREN  = r'\)'
    
        # A regular expression rule with some action code
        # Note addition of self parameter since we're in a class
        def t_NUMBER(self,t):
            r'\d+'
            t.value = int(t.value)    
            return t
    
        # Define a rule so we can track line numbers
        def t_newline(self,t):
            r'\n+'
            t.lexer.lineno += len(t.value)
    
        # A string containing ignored characters (spaces and tabs)
        t_ignore  = ' \t'
    
        # Error handling rule
        def t_error(self,t):
            print "Illegal character '%s'" % t.value[0]
            t.lexer.skip(1)
    
        # Build the lexer
        def build(self,**kwargs):
            self.lexer = lex.lex(module=self, **kwargs)
        
        # Test it output
        def test(self,data):
            self.lexer.input(data)
            while True:
                 tok = lexer.token()
                 if not tok: break
                 print tok
    
    # Build the lexer and try it out
    m = MyLexer()
    m.build()           # Build the lexer
    m.test("3 + 4")     # Test it
    

    当从类中定义lexer,你需要创建类的实例,而不是类本身。这是因为,lexer的方法只有被绑定(bound-methods)对象后才能使PLY正常工作。

    当给lex()方法使用module选项时,PLY使用dir()方法,从对象中获取符号信息,因为不能直接访问对象的__dict__属性。(译者注:可能是因为兼容性原因,__dict__这个方法可能不存在)

    最后,如果你希望保持较好的封装性,但不希望什么东西都写在类里面,lexers可以在闭包中定义,例如:

    import ply.lex as lex
    
    # List of token names.   This is always required
    tokens = (
      'NUMBER',
      'PLUS',
      'MINUS',
      'TIMES',
      'DIVIDE',
      'LPAREN',
      'RPAREN',
    )
    
    def MyLexer():
        # Regular expression rules for simple tokens
        t_PLUS    = r'\+'
        t_MINUS   = r'-'
        t_TIMES   = r'\*'
        t_DIVIDE  = r'/'
        t_LPAREN  = r'\('
        t_RPAREN  = r'\)'
    
        # A regular expression rule with some action code
        def t_NUMBER(t):
            r'\d+'
            t.value = int(t.value)    
            return t
    
        # Define a rule so we can track line numbers
        def t_newline(t):
            r'\n+'
            t.lexer.lineno += len(t.value)
    
        # A string containing ignored characters (spaces and tabs)
        t_ignore  = ' \t'
    
        # Error handling rule
        def t_error(t):
            print "Illegal character '%s'" % t.value[0]
            t.lexer.skip(1)
    
        # Build the lexer from my environment and return it    
        return lex.lex()
    

    4.15 额外状态维护

    在你的词法分析器中,你可能想要维护一些状态。这可能包括模式设置,符号表和其他细节。例如,假设你想要跟踪NUMBER标记的出现个数。

    一种方法是维护一个全局变量:

    num_count = 0
    def t_NUMBER(t):
        r'\d+'
        global num_count
        num_count += 1
        t.value = int(t.value)    
        return t
    

    如果你不喜欢全局变量,另一个记录信息的地方是lexer对象内部。可以通过当前标记的lexer属性访问:

    def t_NUMBER(t):
        r'\d+'
        t.lexer.num_count += 1     # Note use of lexer attribute
        t.value = int(t.value)    
        return t
    
    lexer = lex.lex()
    lexer.num_count = 0            # Set the initial count
    

    上面这样做的优点是当同时存在多个lexer实例的情况下,简单易行。不过这看上去似乎是严重违反了面向对象的封装原则。lexer的内部属性(除了lineno)都是以lex开头命名的(lexdata、lexpos)。因此,只要不以lex开头来命名属性就很安全的。

    如果你不喜欢给lexer对象赋值,你可以自定义你的lexer类型,就像前面看到的那样:

    class MyLexer:
        ...
        def t_NUMBER(self,t):
            r'\d+'
            self.num_count += 1
            t.value = int(t.value)    
            return t
    
        def build(self, **kwargs):
            self.lexer = lex.lex(object=self,**kwargs)
    
        def __init__(self):
            self.num_count = 0
    

    如果你的应用会创建很多lexer的实例,并且需要维护很多状态,上面的类可能是最容易管理的。

    状态也可以用闭包来管理,比如,在Python3中:

    def MyLexer():
        num_count = 0
        ...
        def t_NUMBER(t):
            r'\d+'
            nonlocal num_count
            num_count += 1
            t.value = int(t.value)    
            return t
        ...
    

    4.16 Lexer克隆

    如果有必要的话,lexer对象可以通过clone()方法来复制:

    lexer = lex.lex()
    ...
    newlexer = lexer.clone()
    

    当lexer被克隆后,复制品能够精确的保留输入串和内部状态,不过,新的lexer可以接受一个不同的输出字串,并独立运作起来。这在几种情况下也许有用:当你在编写的解析器或编译器涉及到递归或者回退处理时,你需要扫描先前的部分,你可以clone并使用复制品,或者你在实现某种预编译处理,可以clone一些lexer来处理不同的输入文件。

    创建克隆跟重新调用lex.lex()的不同点在于,PLY不会重新构建任何的内部分析表或者正则式。当lexer是用类或者闭包创建的,需要注意类或闭包本身的的状态。换句话说你要注意新创建的lexer会共享原始lexer的这些状态,比如:

    m = MyLexer()
    a = lex.lex(object=m)      # Create a lexer
    
    b = a.clone()              # Clone the lexer
    

    4.17 Lexer的内部状态

    lexer有一些内部属性在特定情况下有用:

    lexer.lexpos。这是一个表示当前分析点的位置的整型值。如果你修改这个值的话,这会改变下一个token()的调用行为。在标记的规则方法里面,这个值表示紧跟匹配字串后面的第一个字符的位置,如果这个值在规则中修改,下一个返回的标记将从新的位置开始匹配
    lexer.lineno。表示当前行号。PLY只是声明这个属性的存在,却永远不更新这个值。如果你想要跟踪行号的话,你需要自己添加代码( 4.6 行号和位置信息)
    lexer.lexdata。当前lexer的输入字串,这个字符串就是input()方法的输入字串,更改它可能是个糟糕的做法,除非你知道自己在干什么。
    lexer.lexmatch。PLY内部调用Python的re.match()方法得到的当前标记的原始的Match对象,该对象被保存在这个属性中。如果你的正则式中包含分组的话,你可以通过这个对象获得这些分组的值。注意:这个属性只在有标记规则定义的方法中才有效。

    4.18 基于条件的扫描和启动条件

    在高级的分析器应用程序中,使用状态化的词法扫描是很有用的。比如,你想在出现特定标记或句子结构的时候触发开始一个不同的词法分析逻辑。PLY允许lexer在不同的状态之间转换。每个状态可以包含一些自己独特的标记和规则等。这是基于GNU flex的“启动条件”来实现的,关于flex详见http://flex.sourceforge.net/manual/Start-Conditions.html#Start-Conditions

    要使用lex的状态,你必须首先声明。通过在lex模块中声明”states”来做到:

    states = (
       ('foo','exclusive'),
       ('bar','inclusive'),
    )
    

    这个声明中包含有两个状态:’foo’和’bar’。状态可以有两种类型:’排他型’和’包容型’。排他型的状态会使得lexer的行为发生完全的改变:只有能够匹配在这个状态下定义的规则的标记才会返回;包容型状态会将定义在这个状态下的规则添加到默认的规则集中,进而,只要能匹配这个规则集的标记都会返回。

    一旦声明好之后,标记规则的命名需要包含状态名:

    t_foo_NUMBER = r'\d+'                      # Token 'NUMBER' in state 'foo'        
    t_bar_ID     = r'[a-zA-Z_][a-zA-Z0-9_]*'   # Token 'ID' in state 'bar'
    
    def t_foo_newline(t):
        r'\n'
        t.lexer.lineno += 1
    

    一个标记可以用在多个状态中,只要将多个状态名包含在声明中:

    t_foo_bar_NUMBER = r'\d+'         # Defines token 'NUMBER' in both state 'foo' and 'bar'
    

    同样的,在任何状态下都生效的声明可以在命名中使用ANY:

    t_ANY_NUMBER = r'\d+'         # Defines a token 'NUMBER' in all states
    

    不包含状态名的情况下,标记被关联到一个特殊的状态INITIAL,比如,下面两个声明是等价的:

    t_NUMBER = r'\d+'
    t_INITIAL_NUMBER = r'\d+'
    

    特殊的t_ignore()和t_error()也可以用状态关联:

    t_foo_ignore = " \t\n"       # Ignored characters for state 'foo'
    
    def t_bar_error(t):          # Special error handler for state 'bar'
        pass
    

    词法分析默认在INITIAL状态下工作,这个状态下包含了所有默认的标记规则定义。对于不希望使用“状态”的用户来说,这是完全透明的。在分析过程中,如果你想要改变词法分析器的这种的状态,使用begin()方法:

    def t_begin_foo(t):
        r'start_foo'
        t.lexer.begin('foo')             # Starts 'foo' state
    

    使用begin()切换回初始状态:

    def t_foo_end(t):
        r'end_foo'
        t.lexer.begin('INITIAL')        # Back to the initial state
    

    状态的切换可以使用栈:

    def t_begin_foo(t):
        r'start_foo'
        t.lexer.push_state('foo')             # Starts 'foo' state
    
    def t_foo_end(t):
        r'end_foo'
        t.lexer.pop_state()                   # Back to the previous state
    

    当你在面临很多状态可以选择进入,而又仅仅想要回到之前的状态时,状态栈比较有用。

    举个例子会更清晰。假设你在写一个分析器想要从一堆C代码中获取任意匹配的闭合的大括号里面的部分:这意味着,当遇到起始括号’{‘,你需要读取与之匹配的’}’以上的所有部分。并返回字符串。使用通常的正则表达式几乎不可能,这是因为大括号可以嵌套,而且可以有注释,字符串等干扰。因此,试图简单的匹配第一个出现的’}’是不行的。这里你可以用lex的状态来做到:

    # Declare the state
    states = (
      ('ccode','exclusive'),
    )
    
    # Match the first {. Enter ccode state.
    def t_ccode(t):
        r'\{'
        t.lexer.code_start = t.lexer.lexpos        # Record the starting position
        t.lexer.level = 1                          # Initial brace level
        t.lexer.begin('ccode')                     # Enter 'ccode' state
    
    # Rules for the ccode state
    def t_ccode_lbrace(t):     
        r'\{'
        t.lexer.level +=1                
    
    def t_ccode_rbrace(t):
        r'\}'
        t.lexer.level -=1
    
        # If closing brace, return the code fragment
        if t.lexer.level == 0:
             t.value = t.lexer.lexdata[t.lexer.code_start:t.lexer.lexpos+1]
             t.type = "CCODE"
             t.lexer.lineno += t.value.count('\n')
             t.lexer.begin('INITIAL')           
             return t
    
    # C or C++ comment (ignore)    
    def t_ccode_comment(t):
        r'(/\*(.|\n)*?*/)|(//.*)'
        pass
    
    # C string
    def t_ccode_string(t):
       r'\"([^\\\n]|(\\.))*?\"'
    
    # C character literal
    def t_ccode_char(t):
       r'\'([^\\\n]|(\\.))*?\''
    
    # Any sequence of non-whitespace characters (not braces, strings)
    def t_ccode_nonspace(t):
       r'[^\s\{\}\'\"]+'
    
    # Ignored characters (whitespace)
    t_ccode_ignore = " \t\n"
    
    # For bad characters, we just skip over it
    def t_ccode_error(t):
        t.lexer.skip(1)
    

    这个例子中,第一个’{‘使得lexer记录了起始位置,并且进入新的状态’ccode’。一系列规则用来匹配接下来的输入,这些规则只是丢弃掉标记(不返回值),如果遇到闭合右括号,t_ccode_rbrace规则收集其中所有的代码(利用先前记录的开始位置),并保存,返回的标记类型为’CCODE’,与此同时,词法分析的状态退回到初始状态。

    4.19 其他问题

    lexer需要输入的是一个字符串。好在大多数机器都有足够的内存,这很少导致性能的问题。这意味着,lexer现在还不能用来处理文件流或者socket流。这主要是受到re模块的限制。
    lexer支持用Unicode字符描述标记的匹配规则,也支持输入字串包含Unicode
    如果你想要向re.compile()方法提供flag,使用reflags选项:lex.lex(reflags=re.UNICODE)
    由于lexer是全部用Python写的,性能很大程度上取决于Python的re模块,即使已经尽可能的高效了。当接收极其大量的输入文件时表现并不尽人意。如果担忧性能,你可以升级到最新的Python,或者手工创建分析器,或者用C语言写lexer并做成扩展模块。
    如果你要创建一个手写的词法分析器并计划用在yacc.py中,只需要满足下面的要求:

    需要提供一个token()方法来返回下一个标记,如果没有可用的标记了,则返回None。
    token()方法必须返回一个tok对象,具有type和value属性。如果行号需要跟踪的话,标记还需要定义lineno属性。

    5 语法分析基础

    yacc.py用来对语言进行语法分析。在给出例子之前,必须提一些重要的背景知识。首先,‘语法’通常用BNF范式来表达。例如,如果想要分析简单的算术表达式,你应该首先写下无二义的文法:

    expression : expression + term
               | expression - term
               | term
    
    term       : term * factor
               | term / factor
               | factor
    
    factor     : NUMBER
               | ( expression )
    

    在这个文法中,像NUMBER,+,-,*,/的符号被称为终结符,对应原始的输入。类似term,factor等称为非终结符,它们由一系列终结符或其他规则的符号组成,用来指代语法规则。

    通常使用一种叫语法制导翻译的技术来指定某种语言的语义。在语法制导翻译中,符号及其属性出现在每个语法规则后面的动作中。每当一个语法被识别,动作就能够描述需要做什么。比如,对于上面给定的文法,想要实现一个简单的计算器,应该写成下面这样:

    Grammar                             Action
    --------------------------------    -------------------------------------------- 
    expression0 : expression1 + term    expression0.val = expression1.val + term.val
                | expression1 - term    expression0.val = expression1.val - term.val
                | term                  expression0.val = term.val
    
    term0       : term1 * factor        term0.val = term1.val * factor.val
                | term1 / factor        term0.val = term1.val / factor.val
                | factor                term0.val = factor.val
    
    factor      : NUMBER                factor.val = int(NUMBER.lexval)
                | ( expression )        factor.val = expression.val
    

    一种理解语法指导翻译的好方法是将符号看成对象。与符号相关的值代表了符号的“状态”(比如上面的val属性),语义行为用一组操作符号及符号值的函数或者方法来表达。

    Yacc用的分析技术是著名的LR分析法或者叫移进-归约分析法。LR分析法是一种自下而上的技术:首先尝试识别右部的语法规则,每当右部得到满足,相应的行为代码将被触发执行,当前右边的语法符号将被替换为左边的语法符号。(归约)

    LR分析法一般这样实现:将下一个符号进栈,然后结合栈顶的符号和后继符号(译者注:下一个将要输入符号),与文法中的某种规则相比较。具体的算法可以在编译器的手册中查到,下面的例子展现了如果通过上面定义的文法,来分析3 + 5 * ( 10 - 20 )这个表达式,$用来表示输入结束

    Step Symbol Stack           Input Tokens            Action
    ---- ---------------------  ---------------------   -------------------------------
    1                           3 + 5 * ( 10 - 20 )$    Shift 3
    2    3                        + 5 * ( 10 - 20 )$    Reduce factor : NUMBER
    3    factor                   + 5 * ( 10 - 20 )$    Reduce term   : factor
    4    term                     + 5 * ( 10 - 20 )$    Reduce expr : term
    5    expr                     + 5 * ( 10 - 20 )$    Shift +
    6    expr +                     5 * ( 10 - 20 )$    Shift 5
    7    expr + 5                     * ( 10 - 20 )$    Reduce factor : NUMBER
    8    expr + factor                * ( 10 - 20 )$    Reduce term   : factor
    9    expr + term                  * ( 10 - 20 )$    Shift *
    10   expr + term *                  ( 10 - 20 )$    Shift (
    11   expr + term * (                  10 - 20 )$    Shift 10
    12   expr + term * ( 10                  - 20 )$    Reduce factor : NUMBER
    13   expr + term * ( factor              - 20 )$    Reduce term : factor
    14   expr + term * ( term                - 20 )$    Reduce expr : term
    15   expr + term * ( expr                - 20 )$    Shift -
    16   expr + term * ( expr -                20 )$    Shift 20
    17   expr + term * ( expr - 20                )$    Reduce factor : NUMBER
    18   expr + term * ( expr - factor            )$    Reduce term : factor
    19   expr + term * ( expr - term              )$    Reduce expr : expr - term
    20   expr + term * ( expr                     )$    Shift )
    21   expr + term * ( expr )                    $    Reduce factor : (expr)
    22   expr + term * factor                      $    Reduce term : term * factor
    23   expr + term                               $    Reduce expr : expr + term
    24   expr                                      $    Reduce expr
    25                                             $    Success!
    

    (译者注:action里面的Shift就是进栈动作,简称移进;Reduce是归约)

    在分析表达式的过程中,一个相关的自动状态机和后继符号决定了下一步应该做什么。如果下一个标记看起来是一个有效语法(产生式)的一部分(通过栈上的其他项判断这一点),那么这个标记应该进栈。如果栈顶的项可以组成一个完整的右部语法规则,一般就可以进行“归约”,用产生式左边的符号代替这一组符号。当归约发生时,相应的行为动作就会执行。如果输入标记既不能移进也不能归约的话,就会发生语法错误,分析器必须进行相应的错误恢复。分析器直到栈空并且没有另外的输入标记时,才算成功。 需要注意的是,这是基于一个有限自动机实现的,有限自动器被转化成分析表。分析表的构建比较复杂,超出了本文的讨论范围。不过,这构建过程的微妙细节能够解释为什么在上面的例子中,解析器选择在步骤9将标记转移到堆栈中,而不是按照规则expr : expr + term做归约。

    6 Yacc

    ply.yacc模块实现了PLY的分析功能,‘yacc’是‘Yet Another Compiler Compiler’的缩写并保留了其作为Unix工具的名字。

    6.1 一个例子

    假设你希望实现上面的简单算术表达式的语法分析,代码如下:

    # Yacc example
    
    import ply.yacc as yacc
    
    # Get the token map from the lexer.  This is required.
    from calclex import tokens
    
    def p_expression_plus(p):
        'expression : expression PLUS term'
        p[0] = p[1] + p[3]
    
    def p_expression_minus(p):
        'expression : expression MINUS term'
        p[0] = p[1] - p[3]
    
    def p_expression_term(p):
        'expression : term'
        p[0] = p[1]
    
    def p_term_times(p):
        'term : term TIMES factor'
        p[0] = p[1] * p[3]
    
    def p_term_div(p):
        'term : term DIVIDE factor'
        p[0] = p[1] / p[3]
    
    def p_term_factor(p):
        'term : factor'
        p[0] = p[1]
    
    def p_factor_num(p):
        'factor : NUMBER'
        p[0] = p[1]
    
    def p_factor_expr(p):
        'factor : LPAREN expression RPAREN'
        p[0] = p[2]
    
    # Error rule for syntax errors
    def p_error(p):
        print "Syntax error in input!"
    
    # Build the parser
    parser = yacc.yacc()
    
    while True:
       try:
           s = raw_input('calc > ')
       except EOFError:
           break
       if not s: continue
       result = parser.parse(s)
       print result
    

    在这个例子中,每个语法规则被定义成一个Python的方法,方法的文档字符串描述了相应的上下文无关文法,方法的语句实现了对应规则的语义行为。每个方法接受一个单独的p参数,p是一个包含有当前匹配语法的符号的序列,p[i]与语法符号的对应关系如下:

    def p_expression_plus(p):
        'expression : expression PLUS term'
        #   ^            ^        ^    ^
        #  p[0]         p[1]     p[2] p[3]
    
        p[0] = p[1] + p[3]
    

    其中,p[i]的值相当于词法分析模块中对p.value属性赋的值,对于非终结符的值,将在归约时由p[0]的赋值决定,这里的值可以是任何类型,当然,大多数情况下只是Python的简单类型、元组或者类的实例。在这个例子中,我们依赖这样一个事实:NUMBER标记的值保存的是整型值,所有规则的行为都是得到这些整型值的算术运算结果,并传递结果。

    注意:在这里负数的下标有特殊意义–这里的p[-1]不等同于p[3]。详见下面的嵌入式动作部分
    

    在yacc中定义的第一个语法规则被默认为起始规则(这个例子中的第一个出现的expression规则)。一旦起始规则被分析器归约,而且再无其他输入,分析器终止,最后的值将返回(这个值将是起始规则的p[0])。注意:也可以通过在yacc()中使用start关键字参数来指定起始规则

    p_error§规则用于捕获语法错误。详见处理语法错误部分

    为了构建分析器,需要调用yacc.yacc()方法。这个方法查看整个当前模块,然后试图根据你提供的文法构建LR分析表。第一次执行yacc.yacc(),你会得到如下输出:

    $ python calcparse.py
    Generating LALR tables
    calc >
    

    由于分析表的得出相对开销较大(尤其包含大量的语法的情况下),分析表被写入当前目录的一个叫parsetab.py的文件中。除此之外,会生成一个调试文件parser.out。在接下来的执行中,yacc直到发现文法发生变化,才会重新生成分析表和parsetab.py文件,否则yacc会从parsetab.py中加载分析表。注:如果有必要的话这里输出的文件名是可以改的。

    如果在你的文法中有任何错误的话,yacc.py会产生调试信息,而且可能抛出异常。一些可以被检测到的错误如下:

    方法重复定义(在语法文件中具有相同名字的方法)
    二义文法产生的移进-归约和归约-归约冲突
    指定了错误的文法
    不可终止的递归(规则永远无法终结)
    未使用的规则或标记
    未定义的规则或标记
    下面几个部分将更详细的讨论语法规则

    这个例子的最后部分展示了如何执行由yacc()方法创建的分析器。你只需要简单的调用parse(),并将输入字符串作为参数就能运行分析器。它将运行所有的语法规则,并返回整个分析的结果,这个结果就是在起始规则中赋给p[0]的值。

    6.2 将语法规则合并

    如果语法规则类似的话,可以合并到一个方法中。例如,考虑前面例子中的两个规则:

    def p_expression_plus(p):
        'expression : expression PLUS term'
        p[0] = p[1] + p[3]
    
    def p_expression_minus(t):
        'expression : expression MINUS term'
        p[0] = p[1] - p[3]
    

    比起写两个方法,你可以像下面这样写在一个方法里面:

    def p_expression(p):
        '''expression : expression PLUS term
                      | expression MINUS term'''
        if p[2] == '+':
            p[0] = p[1] + p[3]
        elif p[2] == '-':
            p[0] = p[1] - p[3]
    

    总之,方法的文档字符串可以包含多个语法规则。所以,像这样写也是合法的(尽管可能会引起困惑):

    def p_binary_operators(p):
        '''expression : expression PLUS term
                      | expression MINUS term
           term       : term TIMES factor
                      | term DIVIDE factor'''
        if p[2] == '+':
            p[0] = p[1] + p[3]
        elif p[2] == '-':
            p[0] = p[1] - p[3]
        elif p[2] == '*':
            p[0] = p[1] * p[3]
        elif p[2] == '/':
            p[0] = p[1] / p[3]
    

    如果所有的规则都有相似的结构,那么将语法规则合并才是个不错的注意(比如,产生式的项数相同)。不然,语义动作可能会变得复杂。不过,简单情况下,可以使用len()方法区分,比如:

    def p_expressions(p):
        '''expression : expression MINUS expression
                      | MINUS expression'''
        if (len(p) == 4):
            p[0] = p[1] - p[3]
        elif (len(p) == 3):
            p[0] = -p[2]
    

    如果考虑解析的性能,你应该避免像这些例子一样在一个语法规则里面用很多条件来处理。因为,每次检查当前究竟匹配的是哪个语法规则的时候,实际上重复做了分析器已经做过的事(分析器已经准确的知道哪个规则被匹配了)。为每个规则定义单独的方法,可以消除这点开销。

    6.3 字面字符

    如果愿意,可以在语法规则里面使用单个的字面字符,例如:

    def p_binary_operators(p):
        '''expression : expression '+' term
                      | expression '-' term
           term       : term '*' factor
                      | term '/' factor'''
        if p[2] == '+':
            p[0] = p[1] + p[3]
        elif p[2] == '-':
            p[0] = p[1] - p[3]
        elif p[2] == '*':
            p[0] = p[1] * p[3]
        elif p[2] == '/':
            p[0] = p[1] / p[3]
    

    字符必须像’+’那样使用单引号。除此之外,需要将用到的字符定义单独定义在lex文件的literals列表里:

    # Literals.  Should be placed in module given to lex()
    literals = ['+','-','*','/' ]
    

    字面的字符只能是单个字符。因此,像’<=’或者’=’都是不合法的,只能使用一般的词法规则(例如t_EQ = r’==’)。

    6.4 空产生式

    yacc.py可以处理空产生式,像下面这样做:

    def p_empty(p):
        'empty :'
        pass
    

    现在可以使用空匹配,只要将’empty’当成一个符号使用:

    def p_optitem(p):
        'optitem : item'
        '        | empty'
        ...
    

    注意:你可以将产生式保持’空’,来表示空匹配。然而,我发现用一个’empty’规则并用其来替代’空’,更容易表达意图,并有较好的可读性。

    6.5 改变起始符号

    默认情况下,在yacc中的第一条规则是起始语法规则(顶层规则)。可以用start标识来改变这种行为:

    start = 'foo'
    
    def p_bar(p):
        'bar : A B'
    
    # This is the starting rule due to the start specifier above
    def p_foo(p):
        'foo : bar X'
    ...
    

    用start标识有助于在调试的时候将大型的语法规则分成小部分来分析。也可把start符号作为yacc的参数:

    yacc.yacc(start='foo')
    

    作者:天降攻城狮
    链接:https://www.jianshu.com/p/0eaeba15ee68
    来源:简书
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    展开全文
  • LexYacc第二版高清版

    2019-01-30 13:33:26
    LexYacc第二版高清版,扫描版,有目录
  • Lex Yacc句子识别.rar

    2020-07-09 17:14:34
    借助自动生成工具LexYacc实现句子识别。其中输入“cat eat mouse”后,输出“Sentence is valid”,表示可以识别此类语句,而输入“I love you”后,输出“syntax error”,表示不可识别这类语句。
  • PLY——Python Lex Yacc

    2021-07-29 14:39:14
    如果你从事编译器或解析器的开发工作,你可能对lexyacc不会陌生,PLY是David Beazley实现的基于Python的lexyacc。作者最著名的成就可能是其撰写的Python Cookbook, 3rd Edition。一个基于python实现的LexYacc...

    PLY

    你好! 如果你从事编译器或解析器的开发工作,你可能对lex和yacc不会陌生,PLY是David Beazley实现的基于Python的lex和yacc。作者最著名的成就可能是其撰写的Python Cookbook, 3rd Edition。一个基于python实现的Lex和Yacc的编译器构建工具。包括支持LALR(1)分析法、提供丰富的输入验证、错误报告和诊断。因此,如果你曾经在其他编程语言下使用过yacc,你应该能够很容易的迁移到PLY上。

    编译器与解析器

    根据他们的定义,编译器和解释器之间的区别貌似十分明显:

    解释器:直接执行用编程语言编写的指令的程序
    编译器:把源代码转换成(翻译)低级语言的程序

    了解定义之后我们把重点放在编译器上,根据定义简单来说就是把我没写的源代码转换成机器可以识别的机器码(汇编码)

    具体的转换过程如下
    以c代码为案例
    源程序到目标程序执行的四个阶段如图1所示,GCC编译C源代码有四个步骤:预处理—->编译—->汇编—->链接。
    在这里插入图片描述

    预处理

    编译器将C程序的头文件编译进来,还有宏的替换,可以用gcc的参数-E来参看。

    命令:unix>gcc –o hello hello.c
    作用:将hello.c预处理输出hello.i

    编译(.i—.s)转换为汇编语言文件

    这个阶段编译器主要做词法分析、语法分析、语义分析等,在检查无错误后后,把代码翻译成汇编语言。可用gcc的参数-S来参看。
    编译器(ccl)将文本文件hello.i 翻译成文本文件hello.s, 它包含一个汇编语言程序。
    一条低级机器语言指令。
    命令:gcc -S hello.i -o hello.s
    作用:将预处理输出文件hello.i汇编成hello.s文件

    汇编阶段(.s—.o)得到机器语言

    汇编器as 将hello.s 翻译成机器语言保存在hello.o 中(二进制文本形式)。

    链接阶段

    printf函数存在于一个名为printf.o的单独预编译目标文件中。必须得将其并入到hello.o的程序中,链接器就是负责处理这两个的并入,结果得到hello文件,它就是一个可执行的目标文件。

    重点 编译

    Lex

    lex.py通过向外部提供token()方法作为接口,方法每次会从输入中返回下一个有效的标记。yacc.py将会不断的调用这个方法来获取标记并匹配语法规则。yacc.py的的功能通常是生成抽象语法树(AST),不过,这完全取决于用户,如果需要,yacc.py可以直接用来完成简单的翻译。

    lex.py是用来将输入字符串标记化。例如,假设你正在设计一个编程语言,用户的输入字符串如下:

    x = 3 + 42 * (s - t)
    

    标记器将字符串分割成独立的标记:

    'x','=', '3', '+', '42', '*', '(', 's', '-', 't', ')'
    

    标记通常用一组名字来命名和表示:

    'ID','EQUALS','NUMBER','PLUS','NUMBER','TIMES','LPAREN','ID','MINUS','ID','RPAREN'
    

    将标记名和标记值本身组合起来:

    ('ID','x'), ('EQUALS','='), ('NUMBER','3'),('PLUS','+'), ('NUMBER','42), ('TIMES','*'),('LPAREN','('), ('ID','s'),('MINUS','-'),('ID','t'), ('RPAREN',')
    

    正则表达式是描述标记规则的典型方法,下面展示如何用lex.py实现。

    # -----------------------------------------------------------
    # calclex.py
    #
    # tokenizer for a simple expression evaluator for
    # numbers and +,-,*,/
    # ------------------------------------------------------------
    import ply.lex as lex
    
    # List of token names.   This is always required
    tokens = (
       'NUMBER',
       'PLUS',
       'MINUS',
       'TIMES',
       'DIVIDE',
       'LPAREN',
       'RPAREN',
    )
    
    # Regular expression rules for simple tokens
    t_PLUS    = r'\+'
    t_MINUS   = r'-'
    t_TIMES   = r'\*'
    t_DIVIDE  = r'/'
    t_LPAREN  = r'\('
    t_RPAREN  = r'\)'
    
    # A regular expression rule with some action code
    def t_NUMBER(t):
        r'\d+'
        t.value = int(t.value)    
        return t
    
    # Define a rule so we can track line numbers
    def t_newline(t):
        r'\n+'
        t.lexer.lineno += len(t.value)
    
    # A string containing ignored characters (spaces and tabs)
    t_ignore  = ' \t'
    
    # Error handling rule
    def t_error(t):
        print "Illegal character '%s'" % t.value[0]
        t.lexer.skip(1)
    
    # Build the lexer
    lexer = lex.lex()
    

    为了使lexer工作,你需要给定一个输入,并传递给input()方法。然后,重复调用token()方法来获取标记序列,下面的代码展示了这种用法:

    # Test it out
    data = '''
    3 + 4 * 10
      + -20 *2
    '''
    
    # Give the lexer some input
    lexer.input(data)
    
    # Tokenize
    while True:
        tok = lexer.token()
        if not tok: break      # No more input
        print tok
    

    程序执行,将给出如下输出:

    $ python example.py
    LexToken(NUMBER,3,2,1)
    LexToken(PLUS,'+',2,3)
    LexToken(NUMBER,4,2,5)
    LexToken(TIMES,'*',2,7)
    LexToken(NUMBER,10,2,10)
    LexToken(PLUS,'+',3,14)
    LexToken(MINUS,'-',3,16)
    LexToken(NUMBER,20,3,18)
    LexToken(TIMES,'*',3,20)
    LexToken(NUMBER,2,3,21)
    

    结束

    当然这只是PLY的简单功能,后期我们来了解语法部分Yacc
    ANSI C grammar

    展开全文
  • LexYacc集成开发环境,Windows下一键安装!不需要使用VS配置环境!不需要调试配置文件!自带编辑器环境EditPlusPortable,安装完成即可使用。 *1:安装目录不要选择"Program Files"的文件夹 *2:安装完成后点击...
  • LEX/YACC环境安装

    2018-06-09 21:24:11
    压缩包包含两个程序: bison-2.4.1-setup.exe\flex-2.5.4a-1.exe 下载后直接点击安装就可以,接着右键计算机,打开属性->高级系统设置->环境变量,在...之后你就可以在cmd中通过命令编译你的lex\yacc文件了。 绝对可用
  • lex yacc联系与区别

    千次阅读 2017-02-05 11:20:50
    项目中用到了,关于update.c中的parse_string函数,定义在parser.y(yacc),及lexer.l(lexlex yacc 学习 写在前面的几句废话  最近在项目的过程中接触了lexyacc,他们可以帮助我们来实现自己的领域语言...
    项目中用到了,关于update.c中的parse_string函数,定义在parser.y(yacc),及lexer.l(lex)
    lex yacc 学习

    写在前面的几句废话 

    最近在项目的过程中接触了lex 和 yacc,他们可以帮助我们来实现自己的领域语言。最典型的应用就是可以帮助我们来实现自定义测试脚本的执行器。但是,这里也有一个限制,就是测试脚本要做的基本事情必须有现成的C语言库来实现,否则就做不到了;如果基本的操作是用java来做的,那么还可以用Antlr,这里不对Antlr做详细介绍。


    lex是什么?

    教科书上把lex的作用的作用叫做“词法分析 lexical analysis ”,这个中文叫法非常让人看不明白(叫做“符号提取”更合适),其实从它的英文单词lexical上来看他的意思其实是非常清楚的。

    lexical,在webster上的解释是:of or relating to words or the vocabulary of a language as distinguished from its grammar and construction。

    指的是: 一种语言中关于词汇、单词的,与之相对的是这种语言的语法和组织

    这么来看的话 lexical analysis 的作用就应该是语言中的词汇和单词分析。事实上他的作用就是从语言中提取单词。放到编程语言中来说,他要做的事情其实就是提取编程语言占用的各种保留字、操作符等等语言的元素

    所以他的另外一个名字scanner其实更形象一些,就是扫描一个文本中的单词。

    lex把每个扫面出来的单词叫统统叫做token,token可以有很多类。对比自然语言的话,英语中的每个单词都是token,token有很多类,比如non(名词)就是一个类token,apple就是属于这个类型的一个具体token。对于某个编程语言来说,token的个数是很有限的,不像英语这种自然语言中有几十万个单词。

    lex工具会帮我们生成一个yylex函数,yacc通过调用这个函数来得知拿到的token是什么类型的,但是token的类型是在yacc中定义的。

    lex的输入文件一般会被命名成 .l文件,通过lex XX.l 我们得到输出的文件是lex.yy.c


    yacc是什么呢?

    刚才说完lex了,那么yacc呢,教科书上把yacc做的工作叫做syntactic analysis。这次我们翻译没有直译做句法分析,而是叫语法分析,这个翻译能好一点,意思也基本上比较清楚。
    其实我们最开始学习英语的时候老师都会告诉我们英语其实就是“单词+语法”,这个观点放到编程语言中很合适,lex提取了单词,那么是剩下的部分就是如何表达语法。那么yacc做的事情就是这一部分(实际应该说是BNF来做的)。

    yacc会帮我们生成一个yyparse函数,这个函数会不断调用上面的yylex函数来得到token的类型。

    yacc的输入文件一般会被命名成 .y文件,通过yacc -d XX.y我们得到的输出文件是y.tab.h y.tab.c,前者包含了lex需要的token类型定义,需要被include进 .l文件中 

     

    lex和yacc的输入文件格式

     

    Definition section
    %%
    Rules section

    %%
    C code section

     

    .l和.y的文件格式都是分成三段,用%%来分割,三个section的含义是: 

    • Definition Section 

    这块可以放C语言的各种各种include,define等声明语句,但是要用%{ %}括起来。 

    如果是.l文件,可以放预定义的正则表达式:minus "-" 还要放token的定义,方法是:代号 正则表达式。然后到了,Rules Section就可以通过{符号} 来引用正则表达式

    如果是.y文件,可以放token的定义,如:%token INTEGER PLUS ,这里的定一个的每个token都可以在y.tab.h中看到 

    •  Rules section

    .l文件在这里放置的rules就是每个正则表达式要对应的动作,一般是返回一个token

    .y文件在这里放置的rules就是满足一个语法描述时要执行的动作

    不论是.l文件还是.y文件这里的动作都是用{}扩起来的,用C语言来描述,这些代码可以做你任何想要做的事情 

    •  C code Section

    main函数,yyerror函数等的定义   

    lex和yacc能帮我们做什么?

    一句话:解释执行自定义语言。有几点要注意: 

    1. 自定义语言的要做的事情必须可以能通过C语言来实现。其实任何计算机能做的事情都可以用C语言来实现,lex和yacc存在的意义在于简化语言,让使用者能够以一种用比较简单的语言来实现复杂的操作。比如:对于数据库的查询肯定有现成的库可以来完成,但是使用起来比较麻烦,要自己写成语调用API,编译才行。如果我们想实自定义一个简单的语言(比如SQL)来实现操作,这个时候就可以用lex和yacc。
    2. lex和yacc 做的事情只是:用C语言来实现另外一种语言。所以,他没办法实现C语言自己,但是可以实现java、python等。当然你可以通过Antlr来实现C语言的解析和执行,如果你这么做的话,C语言程序首先是通过java来执行,然后java又变成了本地语言(C语言)来执行,谁叫我们的操作系统都是C语言实现的呢。 

    使用lex和yacc我们要做那几件事情? 

    1. 定义各种token类型。他们在.y中定义,这些token既会被lex使用到,也会被.y文件中的BNF使用到。
    2. 写词汇分析代码。这部分代码在.l文件(就是lex的输入文件)中。这块的定义方式是:正则表达式-->对应操作。如果和yacc一起来使用的话,对应的操作通常是返回一个token类型,这个token的类型要在yacc中提前定义好。
    3. 写BNF。这些东西定义了语言的规约方式。

    关于BNF

    是一种context-free grammars,请参考:http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form 摘录:

     <symbol> ::= __expression__ 

     

    1. <symbol> is a nonterminal 
    2.  __expression__ consists of one or more sequences of symbols 
    3. more sequences are separated by the vertical bar, '|' 
    4. Symbols that never appear on a left side are terminals. On the other hand 
    5. symbols that appear on a left side are non-terminals and are always enclosed between the pair <>.  

     

    在yacc中定义的方式其实是:

     <symbol> : __expression__  {operation}

     __expression__  {operation}

    operation 是 满足语法时要执行的C语言代码,这里的C语言代码可以使用一些变量,他们是:$$ $1 $2等等。$$代表规约的结果,就是表达式__expression__的值,$1代表的是前面 __expression__ 中出现的各个word。举个例子:

     

    expr2:
      expr3 { $$ == $ 1; }
    | expr2 PLUS expr3 { $$ = plus($ 1, $ 3); }
    | expr2 MINUS expr3 { $$ = minus($ 1, $ 3); }
    ;
    来自: http://memphis.compilertools.net/interpreter.html 
    1. expr2 expr3都是BNF中定义的non-terminal
    2. PLUS和MINUS都是.y中定义的token类
    3. plus和minus 是事先定义好的C语言函数

    关于yacc中BNF的推导过程引用后面的《lex和yacc简明教程》做一下说明:

    1. yacc 在内部维护着两个堆栈;一个分析栈和一个内容栈。分析栈中保存着终结符和非终结符,并且代表当前剖析状态。内容栈是一个YYSTYPE 元素的数组,对于分析栈中的每一个元素都保存着一个对应的值。例如,当yylex 返回一个INTEGER标记时,y acc 把这个标记移入分析栈。同时,相应的yylval 值将会被移入内容栈中。分析栈和内容栈的内容总是同步的,因此从栈中找到对应于一个标记的值是很容易实现的。
    2. 对expr: expr '+' expr { $$ = $1 + $3; }来说,在分析栈中我们其实用左式替代了右式。在本例中,我们弹出“expr '+' expr” 然后压入“expr”。 我们通过弹出三个成员,压入一个成员缩小的堆栈。在我们的C 代码中可以用通过相对地址访问内容栈中的值,“ $1”代表右式中的第一个成员,“ $2”代表第二个,后面的以此类推。“ $$ ”表示缩小后的堆栈的顶部。在上面的动作中,把对应两个表达式的值相加,弹出内容栈中的三个成员,然后把造得到的和压入堆栈中。这样,分析栈和内容栈中的内容依然是同步的。

    来看一个用lex和yacc实现计算器的例子

    参考了下面链接的lex和yacc文件:http://blog.csdn.net/crond123/article/details/3932014 

    cal.y 

    复制代码
    %{
    #include  < stdio.h >
    #include "lex.yy.c"
    #define YYSTYPE int  
    int yyparse(void);
    %}
    %token INTEGER PLUS MINUS TIMES DIVIDE LP RP
    %%
    command : exp {printf("%d/n",$1);}

    exp: exp PLUS term {$$ = $1 + $3;}
        |exp MINUS term {$$ = $1 - $3;}
        |term {$$ = $1;}
        ;
    term : term TIMES factor {$$ = $1 * $3;}
        |term DIVIDE factor {$$ = $1/$3;}
        |factor {$$ = $1;}
        ;
    factor : INTEGER {$$ = $1;}
        | LP exp RP {$$ = $2;}
        ;
    %%
    int main()
    {
        return yyparse();
    }
    void yyerror(char* s)
    {
        fprintf(stderr,"%s",s);
    }
    int yywrap()
    {
        return 1;
    复制代码

    cal.l

     %{  

    复制代码
    #include < string.h >  
    #include "y.tab.h"  
    extern int yylval;  
    %}  
    numbers ([0-9])+  
    plus "+"  
    minus "-"  
    times "*"  
    divide "/"  
    lp "("  
    rp ")"  
    delim [ /n/t]  
    ws {delim}*  
    %%  
    {numbers} {sscanf(yytext, "%d",  &yylval); return INTEGER;}  
    {plus} {return PLUS;}  
    {minus} {return MINUS;}  
    {times} {return TIMES;}  
    {divide} {return DIVIDE;}  
    {lp} {return LP;}  
    {rp} {return RP;}  
    {ws}       ;   
    . {printf("Error");exit(1);}    
    %% 
    复制代码

     

    使用方式: 

    yacc -d cal.y 

    lex cal.l

    g++ -o cal y.tab.c 

    运行./cal 然后输入3+4 ctrl+D就可以看到结果了 

     

     

    关于lex和yacc中一些预定义的东西 

     

    Lex 变量

    yyin FILE* 类型。 它指向 lexer 正在解析的当前文件。
    yyout FILE* 类型。 它指向记录 lexer 输出的位置。 缺省情况下,yyin 和 yyout 都指向标准输入和输出。
    yytext 匹配模式的文本存储在这一变量中(char*)。
    yyleng 给出匹配模式的长度。
    yylineno 提供当前的行数信息。 (lexer不一定支持。)

     

     Lex 函数

    yylex() 这一函数开始分析。 它由 Lex 自动生成。
    yywrap() 这一函数在文件(或输入)的末尾调用。 如果函数的返回值是1,就停止解析。 因此它可以用来解析多个文件。 代码可以写在第三段,这就能够解析多个文件。 方法是使用 yyin 文件指针(见上表)指向不同的文件,直到所有的文件都被解析。 最后,yywrap() 可以返回 1 来表示解析的结束。
    yyless(int n) 这一函数可以用来送回除了前�n? 个字符外的所有读出标记。
    yymore() 这一函数告诉 Lexer 将下一个标记附加到当前标记后。

    参考资料: 

    首先推荐《lex and yacc tutorial》 http://epaperpress.com/lexandyacc/download/LexAndYaccTutorial.pdf 
    上面pdf的中文版《lex和yacc简明教程》在在:http://ishare.iask.sina.com.cn/f/22266803.html  

    http://memphis.compilertools.net/interpreter.html 

    http://www.ibm.com/developerworks/cn/linux/sdk/lex/ 

    一个老外写的上手教程
    这两个用 lex 和 yacc实现了 c语言解释器

    http://www.ibm.com/developerworks/cn/linux/game/sdl/pirates-4/index.html 


    展开全文
  • 编译原理lexyacc的联合使用实验报告.zip
  • 编译原理lexyacc的联合使用实验报告.pdf
  • lex yacc的介绍文档 学习编译原理不容错过,内有词法分析的一个自动软件 很有名
  • lexYacc简单编译器

    2011-06-17 13:25:01
    lexyacc做的一个简单的带有词法分析 语法分析 语义分析的一个编译器,供大家参考
  • Lex yacc从入门到精通

    2011-10-28 20:25:01
    Lex Yacc语言:语法解析器。用于开发私有脚本的专用工具。类似的JAVA中使用的是Antlr。
  • 一个Lex/Yacc完整的示例(可使用C++)

    热门讨论 2013-04-27 17:56:08
    本框架是一个lex/yacc完整的示例,用于学习lex/yacc程序基本的搭建方法,在linux/cygwin下敲入make就可以编译和执行。 本例子虽小却演示了lex/yacc程序最常见和重要的特征: * lex/yacc文件格式、程序结构。 * 如何...
  • LY是纯粹由Python实现的Lexyacc(流行的编译器构建工具)。PLY的设计目标是尽可能的沿袭传统lexyacc工具的工作方式,包括支持LALR(1)分析法、提供丰富的输入验证、错误报告和诊断。因此,如果你曾经在其他编程...
  • lex yacc使用

    2014-09-30 12:23:15
    lex yacc简单使用,lex词法分析器自动生成,yacc语法分析器自动生成
  • lexyacc.pdf

    2010-03-25 15:29:50
    学习 lexyacc 的入门级教材。 讲解的比较清楚
  • LexYacc

    2006-09-25 22:11:59
    这是一个在Windows环境下面配置好了的LexYacc命令行环境。其特点就是在拥有了LexYacc环境之后不在拥有任何多余的元素,是一个非常精巧的LexYacc环境。发布这个包的目的就是为了能够配合我的博客中的文章的需要...
  • 学习LexYacc 该项目包含许多使用LexYacc样式工具构建解析器的示例。 我以LexYacc的名字命名了这个项目,以纪念经典的UNIX工具。 我确实包含了一个使用Flex和Bison程序的示例项目,但是这里的大多数示例都是...
  • lexyacc.pdf

    2020-08-05 10:27:44
    这是关于编译原理, 词法分析lex, 与语法分析yacc的相关文档,高清版,但是这只有该书的前5章 第一章 lexyacc 第二章 lex使用 第三章 yacc使用 第四章 菜单生成与语言 第五章 SQL分析
  • Win32LexYacc.zip

    2011-01-13 01:06:01
    windows 下的 yacc_lex 工具,和uinx下的用法一样
  • 果冻豆 Jellybean 有两个目的: 教这个该死的傻瓜如何编写基本的元编译器,包括逐步检查和调试词法分析和解析步骤。 提供一个简单的语言设计工作室来处理语法和句法规则以进行快速周转调查。 ...
  • 压缩包包含两个程序: bison-2.4.1-setup.exe\flex-2.5.4a-1...绝对可用,本人亲试,如果编译不成功的可能是你写的lex\yacc文件有问题,用一个好的示例文件进行编译就知道这可以用了(血泪教训啊,当初还以为不能用呢)
  • LexYacc》中文第二版,高清扫描版,包含书中例子的代码实现。
  • 【译】Python-Lex-Yacc手册.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,456
精华内容 4,582
关键字:

lex yacc

友情链接: ansys弯矩.rar