精华内容
下载资源
问答
  • 前言本系列的文章的宗旨是让大家能够写出自己的编译器,解释器或者脚本引擎,所以每到理论介绍到一个程度后,我都会来讨论实践问题.理论方面,编译原理的教材已经是够多了,而实践的问题却很少讨论.前几节文章只讨论到了...

    前言

    本系列的文章的宗旨是让大家能够写出自己的编译器,解释器或者脚本引擎,所以每到理论介绍到一个程度后,我都会来讨论实践问题.理论方面,编译原理的教材已经是够多了,而实践的问题却很少讨论.

    前几节文章只讨论到了词法分析和LL文法分析,关键的LR文法分析这里却还没有讲,我们先不要管复杂的LR文法和算法,让我们使用LL算法来实际做一些东西后再说.本文将介绍一个在JAVA上广泛使用的LL算法分析工具Javacc.(这是我唯一能找到的使用LL算法的语法分析器构造工具).这一节的文章并非只针对JAVA开发者,如果你是C/C++开发者,那么也请你来看看这个JAVA下的优秀工具,或许你将来也用得着它.

    Lex和yacc这两个工具是经典的词法分析和语法分析工具,但是它们都是基于C语言下面的工具,而使用JAVA的朋友们就用不上了.但是JAVA下已经有了lex和yacc的替代品javacc(

    Java Compiler Compiler )

    .同时javacc也是使用LL算法的工具,我们也可以实践一下前面学的LL算法.

    首先声明我不是一个JAVA专家,我也是刚刚才接触JAVA.Java里面或许有很多类似javacc一样的工具,但是据我所知,javacc还是最广泛,最标准的JAVA下的词法语法分析器.

    Javacc的获取

    同lex和yacc一样,javacc也是一个免费可以获取的通用工具,它可以在很多JAVA相关的工具下载网站下载,当然,javacc所占的磁盘空间比起lex和yacc更大一些,里面有标准的文档和examples.相对lex和yacc来说,javacc做得更人性化,更容易一些.如果你实在找不到javacc,还是可以联系我,我这里有.现在最新的就是javacc 3.2版本.

    Javacc的原理

    Javacc可以同时完成对text的词法分析和语法分析的工作,使用起来相当方便.同样,它和lex和yacc一样,先输入一个按照它规定的格式的文件,然后javacc根据你输入的文件来生成相应的词法分析于语法分析程序.同时,新版本的Javacc除了常规的词法分析和语法分析以外,还提供JJTree等工具来帮助我们建立语法树.总之,Javacc在很多地方做得都比lex和yacc要人性化,这个在后面的输入文件格式中也能体现出来.

    Javacc的输入文件

    Javacc的输入文件格式做得比较简单.每个非终结符产生式对应一个Class中的函数,函数中可以嵌入相应的识别出该终结符文法时候的处理代码(也叫动作).这个与YACC中是一致的.

    Javacc的输入文件中,有一系列的系统参数,比如其中lookahead可以设置成大于1的整数,那么就是说,它可以为我们生成LL(k)算法(k>=1),而不是简单的递归下降那样的LL(1)算法了.要知道,LL(2)文法比起前面讨论的LL(1)文法判断每个非终结符时候需要看前面两个记号而不是一个,那么对于文法形式的限制就更少.不过LL(2)的算法当然也比LL(1)算法慢了不少.作为一般的计算机程序设计语言,LL(1)算法已经是足够了.就算不是LL(1)算法,我们也可以通过前面讲的左提公因式把它变成一个LL(1)文法来处理.不过既然javacc都把lookahead选择做出来了,那么在某些特定的情况下,我们可以直接调整一个lookahead的参数就可以,而不必纠正我们的文法.

    下面我们来看看Javacc中自带的example中的例子.

    例5.1

    这个例子可以在javacc-3.2/doc/examples/SimpleExamples/Simple1.jj看到

    PARSER_BEGIN(Simple1)

    public class Simple1 {

    public static void main(String args[]) throws ParseException {

    Simple1 parser = new Simple1(System.in);

    parser.Input();

    }

    }

    PARSER_END(Simple1)

    void Input() :

    {}

    {

    MatchedBraces() ("\n"|"\r")*

    }

    void MatchedBraces() :

    {}

    {

    "{" [ MatchedBraces() ] "}"

    }

    设置好javacc的bin目录后,在命令提示符下输入

    javacc Simple1.jj

    然后

    javacc

    就会为你生成下面几个

    java

    源代码文件

    Simple1.java

    Simple1TokenManager.java

    Simple1Constants.java

    SimpleCharStream.java

    Token.java

    TokenMgrError.java

    其中Simple1就是你的语法分析器的对象,它的构造函数参数就是要分析的输入流,这里的是System.in.

    class Simple1就定义在标记

    PARSER_BEGIN(Simple1)

    PARSER_END(Simple1)之间.

    但是必须清楚的是,PARSER_BEGIN和PARSER_END中的名字必须是词法分析器的名字(这里是Simple1).

    PARSER_END下面的定义就是文法非终结符号的定义了.

    Simple1的文法基本就是:

    Input ->

    MatchedBraces ("\n"|"\r")*

    MatchedBraces ->

    {

    MatchedBraces

    }

    从它的定义我们可以看到

    ,

    每个非终结符号对于一个过程

    .

    比如

    Input

    的过程

    void Input() :

    {}

    {

    MatchedBraces() ("\n"|"\r")*

    }

    在定义

    void Input

    后面记住需要加上一个冒号

    ”:”,

    然后接下来是两个块

    {}

    的定义

    .

    第一个

    {}

    中的代码是定义数据

    ,

    初试化数据的代码

    .

    第二个

    {}

    中的部分就是真正定义

    Input

    的产生式了

    .

    每个产生式之间用

    ”|”

    符号连接

    .

    注意

    :

    这里的产生式并非需要严格

    BNF

    范式文法

    ,

    它的文法既可以是

    BNF,

    同时还可以是混合了正则表达式中的定义方法

    .

    比如上面的

    Input ->

    MatchedBraces ("\n"|"\r")*

    (“\n”|”\r”)*

    就是个正则表达式

    ,

    表示的是

    \n

    或者

    \r

    0

    个到无限个的重复的记号

    .

    javacc

    系统定义的记号

    (TOKEN),

    表示文件结束符号

    .

    除了

    ,

    无论是系统定义的

    TOKEN,

    还是自定义的

    TOKEN,

    里面的

    TOKEN

    都是以

    的方式表示

    .

    每个非终结符号

    (Input

    MatchedBraces)

    都会在

    javacc

    生成的

    Simple1.java

    中形成

    Class Simple1

    的成员函数

    .

    当你在外部调用

    Simple1

    Input,

    那么语法分析器就会开始进行语法分析了

    .

    5.2

    javacc

    提供的

    example

    里面没有

    .javacc

    提供的

    example

    里面提供的例子中

    SimpleExamples

    过于简单

    ,

    而其它例子又过于庞大

    .

    下面我以我们最常见的数学四则混合运算的文法来构造一个

    javacc

    的文法识别器

    .

    这个例子是我自己写的

    ,

    十分简单

    ,.

    其中还包括了文法识别同时嵌入的构建语法树

    Parse-Tree

    的代码

    .

    不过由于篇幅的原因

    ,

    我并没有给出全部的代码

    ,

    这里只给了

    javacc

    输入部分相关的代码

    .

    Parse-tree

    就是一个普通的

    4

    叉树

    ,3

    child,1

    next(

    平行结点

    ),

    相信大家在学习数据结构的时候应该都是学过的

    .

    所以这里就省略过去了

    .

    在大家看这些输入代码之前

    ,

    我先给出它所使用的文法定义

    ,

    好让大家有个清楚的框架

    .

    Expression

    -> Term{ Addop Term }

    Addop -> "+" | "-"

    Term->Factor { Mulop Factor }

    Mulop -> "*" | "/"

    Factor -> ID | NUM | "("Expression")"

    这里的文法可能和BNF范式有点不同.{}的意思就是0次到无限次重复,它跟我们在学习正则表达式的时候的”*”符号相同,所以,在Javacc中的文法表示的时候,{…}部分的就是用(…)*来表示.

    为了让词法分析做得更简单

    ,

    我们通常都不会在文法分析的时候

    ,

    使用

    ”(”,”)“

    等字符号串来表示终结符号

    ,

    而需要转而使用

    LPAREN

    ,

    RPAREN

    这样的整型符号来表示

    .

    PARSER_BEGIN(Grammar)

    public class Grammar implements NodeType {

    public ParseTreeNode GetParseTree(InputStream in) throws ParseException

    {

    Grammar parser =new Grammar(in);

    return parser.Expression();

    }

    }

    PARSER_END(Grammar)

    SKIP :

    {

    " " | "\t" | "\n" | "\r"

    }

    TOKEN :

    {

    < ID: ["a"-"z","A"-"Z","_"] ( ["a"-"z","A"-"Z","_","0"-"9"] )* >

    |< NUM: ( ["0"-"9"] )+ >

    | < PLUS:"+" >

    | < MINUS:"-" >

    | < TIMERS: "*" >

    | < OVER:"/" >

    | < LPAREN: "(" >

    | < RPAREN: ")" >

    }

    ParseTreeNode Expression() :

    {

    ParseTreeNode ParseTree = null;

    ParseTreeNode node;

    }

    {

    ( node=Simple_Expression()

    {

    if(ParseTree == null)

    ParseTree =node;

    else

    {

    ParseTreeNode t;

    t= ParseTree;

    while(t.next != null)

    t=t.next;

    t.next = node;

    }

    }

    )*

    { return ParseTree;}

    }

    ParseTreeNode Simple_Expression() :

    {

    ParseTreeNode node;

    ParseTreeNode t;

    int op;

    }

    {

    node=Term(){}

    (

    op=addop() t=Term()

    {

    ParseTreeNode newNode = new ParseTreeNode();

    newNode.nodetype = op;

    newNode.child[0] = node;

    newNode.child[1] = t;

    switch(op)

    展开全文
  •  本工作目标是让lex和yacc合作,替代scan.c和parse.c,从而可以构建出灵活可扩展的编译器。  假定所有源码均未被修改。  需修改文件:TINY.L和TINY.Y.  在TINY.L文件的最后,添加函数 yywrap()  ...

               注:工作环境不变。

              本工作目标是让lex和yacc合作,替代scan.c和parse.c,从而可以构建出灵活可扩展的编译器。

               假定所有源码均未被修改。

               需修改文件:TINY.L和TINY.Y.

               在TINY.L文件的最后,添加函数 yywrap()

               int  yywrap()

               {

                    return 1;

               }

             在ITNY.Y文件中将函数 static int yylex()注释掉(或删除掉)。

             文件修改即到此为止。

              使用命令:yacc -d TINY.Y生成y.tab.c和y.tab.h文件。

              使用命令:lex  TINY.L生成lex.yy.c文件。

              将此三个文件和其他源码文件(不包含scan.c和parse.c)加入到一新建工程中。编译即可。

             可以发现编译成功。

             拷贝出可执行文件,尝试执行,却发现程序如下异常:

          程序卡在标准输入界面。正常情况下应同不使用lex和yacc的源码执行一样,生成.tm文件。

           当输入两行字符时,出现:

       

         

         不解!

          我调试了很久,却始终如此。

          我在想,是不是我修改了TINY.L文件,确切的说,是不是我加入的yywrap()函数问题。

         希望各位指教!

    展开全文
  • lex&yacc说到编译器(6.数学表达式)

    千次阅读 2003-12-07 22:41:00
    lex&yacc说到编译器(6.数学表达式) 前言文法分析中最重要算法是LL自顶向下LR自底向上算法.前面几篇文章主要讲解的是LL算法的理论一个LL算法的文法分析器javacc.本文以LL(1)算法中最简单的一种形式递归下降...

    lex&yacc说到编译器(6.数学表达式)<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

     

    前言

    文法分析中最重要算法是LL自顶向下和LR自底向上算法.前面几篇文章主要讲解的是LL算法的理论和一个LL算法的文法分析器javacc.本文以LL(1)算法中最简单的一种形式递归下降算法来分析常规算法问题中的数学表达式问题.同时,本文也介绍手工构造EBNF文法的分析器代码普遍方法.希望本文的实践能对大家实现自己的语法分析器带来帮助.

     

    数学表达式问题

    在学习算法的时候,四则混合运算的表达式处理是个很经典的算法问题.

    比如这里有个数学表达式”122+2*(11-1)/(3-(2-0))”.我们需要根据这个字符串的描述,然后计算出其结果.

     

    Input:

    122+2*(11-1)/(3-(2-0))

    Output:

    142

     

    四则混合运算中还需要考虑到括号,乘除号与加减号的优先运算问题,通常的解决办法就是使用堆栈.那种常规的算法和LL算法有异曲同工之处,更或者说,那么的算法其实是一样的.

     

     

    传统数学表达式处理算法简介

    这个传统算法其实不知不觉地使用LL(1)算法的精髓.它就是主要依靠栈式的数据结构分别保存数和符号,然后根据运算符号的优先级别进行数学计算,并将结果保存在栈里面.

    传统算法中使用了两个栈.一个是保存数值,暂时就叫值栈. 另一个是保存符号的,叫符号栈.我们规定一个记号#,来表示栈底.下面我们就来看看如何计算一个简单的表达式11+2-8*(5-3).

    为了显示整个计算过程,我们以下面这个栈的变化图来表示.

    <?xml:namespace prefix = v ns = "urn:schemas-microsoft-com:vml" />CSDN_Dev_Image_2003-12-7134320.png

    符号栈和值栈的变化是根据输入串来进行的.基本上栈的操作可以简单用下面几句话来说.
    Start:

    1.     如果当前输入串中得到的是数字,则直接压入值栈.然后转到Start.

    2.     如果当前输入串中得到的是符号,那么对符号进行判断.
    1)如果符号是’+’或者’-‘,则依次弹出符号栈的符号,计算栈中数值,直到弹出的符号不是*,/,+,-.
    2)如果符号是’*’或者’/’,则压入符号栈
    3)如果符号是’(‘,则直接压’(‘入符号栈
    4)如果符号是’)’,则依照符号栈的顺序弹出符号,计算栈中数值,把结果压入值栈,直到符号栈顶是’(‘,最后再弹出’(‘ .
    最后转到Start.

    3.     如果当前输入串得到的是EOF(字符串结束符号),则计算栈中数值,知道符号栈没有符号.

     

     

    语法分析数学表达式

    或者可能你以前运用过自己的办法来解决过这个程序问题,不过下面我们将通过编译原理建立的一套文法分析理论,来十分精彩地解决这个算法问题.

    首先是建立数学表达式的文法EBNF.EBNF文法可以更灵活地表示BNF,是BNF范式文法的一种扩展.下面是上一篇javacc的介绍中使用到的计算表达式的文法.

    Expression -> Term { Addop Term }
    Addop -> "+" | "-"
    Term -> Factor { Mulop Factor }
    Mulop -> "*" | "/"
    Factor -> ID | NUM | "(" Expression ")"

     

    我们来看看如何根据这个EBNF文法实现一个递归下降的分析程序.大致上来说要分那么几步来实现.(注意,下面的几个步骤不光是针对本节的数学表达式问题,而是包含所有通常的递归下降文法分析器的实现)

     

     

    语法分析实现

    1.    Step 建立词法分析

    本系列文章开篇第一节就是讲的词法分析相关问题.因为词法分析是语法分析的前提,那么我们在实现递归下降算法的时候,同样应该把词法分析的实现考虑进去.

    本文要处理只是个数学表达式的问题,那么通过上面的文法,可以看到需要识别的词法无非就是2个ID,NUM和4个运算符号’+’’-‘‘*’’/’以及2个括号’(‘‘(‘.本文没有对词法分析的自动机原理进行讲解,这部分内容应该在编译原理中讲得比较透彻.所谓自动机,就是按一定步骤识别每个字符的算法.可以用下面的几个图来表示ID和NUM的识别自动机(识别步骤或算法)

     

    NUM:

    CSDN_Dev_Image_2003-12-7134322.gif

    基本算法就是,如果输入的字符是digit(‘0’-‘9’),那么进入check循环,如果输入还是digit,那么再跳回循环查看,如果输入是other(不是’0’-‘9’),那么就直接accept,接收这个串为NUM类型的TOKEN.

     

    ID:

    CSDN_Dev_Image_2003-12-7134324.gif

    NUM一样,当输入的是letter,那么进入ID的有限自动机.只是在进入check循环后,有两种可能都继续留在循环,那就是digit和letter(‘a’-‘Z’).当输入既不是digit,也不是letter的时候,就跳出check循环,进入accept,把接收到的字符归结成ID类型的TOKEN.

     

    通过这个有限自动机的图示,我们就很容易写出词法分析程序.

     

    不过在此之前,我们得写出识别letter和digit的代码.我们建立两个函数IsLetter和IsDigit来完成这个功能.

     

    int IsLetter(char ch)

    {

        if(ch >= 'A' && ch <= 'Z')

            return 1;

        if(ch >='a' && ch <='z')

            return 1;

        return 0;

    }

     

    int IsDigit(char ch)

    {

        if(ch >= '0' && ch <='9')

            return 1;

        return 0;

    }

     

    有个这两个辅助函数,那么接下来,我们就直接写gettoken词法分析函数,它的功能就是从输入中分析,得到一个一个的token.我们首先定义token的类型.

     

    #define ID  1

    #define NUM 2

    #define PLUS   3 // ‘+’

    #define MINUS  4 // ‘-‘

    #define TIMERS 5 // ‘*’

    #define OVER   6 // ‘/’

    #define LPAREN 7 // ‘(‘

    #define RPAREN 8 // ‘)’

    #define ERROR 255

     

    上面注释已经说符号token代表的意思,我也不再多说.不过需要注意的是,这里我们定义了个ERROR的常量,但是我们这里并没有ERROR的token,它只是为我们后面处理结果时候的一个错误处理信息的定义.

     

    char token[10];

    char *nextchar;

    const char g_strCalculate[]="122+2*(11-1)/(3-(2-0))";

    我们需要定义token记号和一个指到输入串的指针.token记录的就是当前gettoken()得到的token的text(字符串).nextchar是当前指到输入串的指针.最后,我们随便定义一个要分析的数学表达式的输入串g_strCalculate.

     

    int gettoken()

    {

        char *ptoken =token;

        while(*nextchar == ' ' || *nextchar=='/n' || *nextchar=='/t')

            nextchar++;

        switch(*nextchar)

        {

        case '+': nextchar++; return PLUS;

        case '-': nextchar++; return MINUS;

        case '*': nextchar++; return TIMERS;

        case '/': nextchar++; return OVER;

        case '(': nextchar++; return LPAREN;

        case ')': nextchar++; return RPAREN;

        default: break;

        }

        // ID的词法识别分析

        if(IsLetter(*nextchar))

        {

             while(IsLetter(*nextchar) || IsDigit(*nextchar))

             {

                      *ptoken = *nextchar;

                      nextchar++;

                      ptoken++;

             }

             *ptoken ='/0';

             printf("gettoken: token = %s/n",token);

             return ID;

    }

    // NUM的词法识别分析

        if(IsDigit(*nextchar))

        {

            while(IsDigit(*nextchar))

            {

                   *ptoken = *nextchar;

                   nextchar++;

                   ptoken++;

            }

            *ptoken ='/0';

            printf("gettoken: token = %s/n",token);

            return NUM;

        }

        return ERROR;

    }

    代码很简单,我没有写多少任何注释.函数中,首先使用了char *ptoken记录token的首地址,它为后面的字符串复制(构造token)所用.同时,在处理代码的第一部分是过滤掉空格,制表符和换行符.然后是计算符号的词法分析.计算符号就是一个固定的字符号,所以它的识别很简单,直接用switch来判断*nextchar.而后面的ID,NUM的识别就是完全按照前面的有限自动机表示图表来进行编写的.以ID的图表来说,ID的自动机首先是要识别出第一个字符是letter,那么我就写了第一行if(IsLetter(*nextchar)),如果满足,则进入check循环,也就是while(IsLetter(*nextchar) || IsDigit(*nextchar))循环.循环中我们记录了*nextchar到token符号中.最后跳出check循环,进入accept,在代码中return ID.对于NUM的词法识别也是如此的,我就不多说了.

     

    2.    根据EBNF文法建立文法识别函数

    首先看到第一条非终结产生式

    Expression -> Term { Addop Term }

    Expression也是我们总的输入结果函数.我们先定义函数int Expression(),其返回值就是我们要处理的表达式的值.右边的产生式中,第一个是Term,我们就直接调用Term函数完成.然后是0到无限次的Addop Term,那么用一个循环即可.文法中使用非终结符号Addop.程序代码中我没有特别为此非终结符号创建函数.我们直接在代码以’+’ || ‘-‘代替Addop. 代码如下.

    int expression()

    {

        int temp = term(); // 对应文法中的第一个Term

    int tokentype;

        while(*nextchar == '+' || *nextchar == '-') // 对应文法中的{ Addop Term }

        {

            tokentype = gettoken();

            switch(tokentype)

            {

            case PLUS:

                    temp +=term();

                    break;

            case MINUS:

                    temp -=term();

                    break;

            default:

                    break;

            }

        }

        return temp;

    }

    然后是第二条文法.同样,我也没有特别为Mulop特别写一个文法函数,而是直接以’*’|| ‘/’代替.

    Term -> Factor { Mulop Factor }
    同理,建立如下函数

    int term()

    {

        int temp;

        int tokentype;

        temp = factor(); // 对应文法中的Factor

        while(*nextchar == '*' || *nextchar == '//') // 对应文法中的 {Mulop Factor}

        {

            tokentype =gettoken();

            switch(tokentype)

            {

            case TIMERS:

              temp *= factor();

              break;

            case OVER:

              temp /= factor();

              break;

            default:

              break;

            }

        }

        return temp;

    }

    最后是Factor文法 Factor -> ID | NUM | "(" Expression ")"

    这个文法涉及到文法中的产生式的选择.由LL(1)文法的理论我们可以知道,这完全可以是通过ID,NUM, “(“Expression”)”三个产生式的第一个终结符的不同来判断的.ID的第一个字符号肯定是letter.而NUM第一个字符号肯定是digit. "(" Expression ")"第一个字符号肯定是”(“.而ID,NUM的判断我们已经在词法分析的时候做好了(int gettoken()函数中).下面列出Factor文法函数的代码.

    int factor()

    {

        int number;

        switch(gettoken())

        {

        case ID: break;

        case NUM:

            number = atoi(token);

            break;

        case LPAREN:

            number = expression();

            if(gettoken() != RPAREN)

             printf("lost ')' in the expression /n");

            break;

        default:

            break;

        }

        return number;

    }

     

    好了,把上面出现的函数都写到程序文件中,加上个main函数,就可以编译运行了.

    int main(int argc, char *argv[])

    {

      nextchar = g_strCalculate;

      printf("result = %d/n",expression());

      system("PAUSE"); 

      return 0;

    }

     

    整个数学表达式的源程序大家可以在这里下载.

    http://member.netease.com/~qinj/tangl_99/my doc/calculate/main.c

     

    3.    总结

     

    从上面三个EBNF文法实现我们可以容易得出一些机械性规律出来.

    1.     对于EBNF文法中的非终结符都可以写成了一个单独的文法函数出来,比如前面Expression(),Term(),Factor().

    2.     文法中的产生式的选择可以根据第一个字符号来进行识别,这就是LL(1)算法中提到的First集合.比如上面的Factor是直接通过gettoken得到下一个token的类型,然后根据类型的不同的token来switch处理不同产生式的代码.

    3.     文法中的{}(0到无限次循环),比如{Addop Term},{ Mulop Factor}可以直接通过循环语句完成.不过循环的条件还是需要判断下一token是不是Addop或者Mulop的First集合的元素.比如上面的代码中,Addop就是’+’和’-‘,Mulop无非就是’*’和’/’,所以判断很容易,直接通过*nextchar也可以判断.如果下一个token不是Addop或者Mulop的First集合元素,那么就应该跳出循环.返回文法函数.

     

    虽然EBNF文法构造递归下降文法分析器代码是如此的简单,但是正如<<编译原理及实践>>书上提到的,它有它的特殊性.很多时候,仅仅是把BNF文法转换成EBNF文法本身就是一件十分困难的事情.这就需要我们前面提到的LL(1)文法的消除左递归和提取左因式的问题.

     

    与传统算法的比较

     

    当我们明白了EBNF文法和递归下降的分析后,构造的数学表达式处理代码比传统算法要简单,要容易.原因前面也提到过,首先种东西的EBNF文法十分容易写,其次,从EBNF文法到代码的创建也十分机械化,也十分容易,最后,递归下降算法没有接触到栈的操作,利用了程序语言本身的递归本身特性,让程序语言去处理栈的操作(并不是说递归下降的算法一点都没有接触到栈,可以说数据结构中递归处理就等于栈处理).

    递归下降的算法也和容易扩展表达式的计算操作.比如说,我们想把函数(如sin,cos)加进去,而且是加到所有运算的最高级别.那么我们修改Factor文法即可

    Factor -> ID | NUM | "(" Expression ")"

    | “sin””(“ Expression “)”

    | “cos””)” Expression “)”

    至于代码的实现,我们也只需要在int Factor函数中的switch中增加几个case语句就可以了.

     

     

     

     

    2003-12-06

    作者:唐良 tangl_99

    QQ:8664220

    msn:tangl_99@hotmail.com

    email:tangl_99@sohu.com

    成都,四川大学,计算机学院

     

    展开全文
  • 【PLY】Lex和Yacc简单示例

    千次阅读 2019-07-29 23:57:23
    PLY是流行的编译器构造工具lex和yacc的纯python实现。 PLY官方文档:http://www.dabeaz.com/ply/ PLY文档翻译:https://qyliang.blog.csdn.net/article/details/97686897 PLY由两个单独的模块组成lex.py和 yacc . py...

    PLY是流行的编译器构造工具lex和yacc的纯python实现
    PLY官方文档:http://www.dabeaz.com/ply/
    PLY文档翻译:https://qyliang.blog.csdn.net/article/details/97686897

    PLY由两个单独的模块组成lex.py和 yacc . py 。都可以在名为ply的Python包中找到。

    lex.py模块用于将输入的文本通过正则表达式转化成一系列特定的token。

    yacc.py用于识别以上下文无关语法形式指定的语言语法。

    lex示例

    # ------------------------------------------------------------
    # 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()
    
    
    # =============================================================================
    # Test it out
    # =============================================================================
    # 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)
    

    最终打印结果:
    在这里插入图片描述

    YACC示例

    # Yacc example
     
    import ply.yacc as yacc
     
    # Get the token map from the lexer.  This is required.
    from LexExample 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 = input('calc > ')
           #s = '3 + 5 * (10 - 20)'
       except EOFError:
           break
       if not s: continue
       result = parser.parse(s)
       print(result)
    

    打印结果为:
    在这里插入图片描述

    对于结果的解释和跟多的细节在文档中有介绍。

    展开全文
  • 文法分析中最重要算法是LL自顶向下LR自底向上算法.前面几篇文章主要讲解的是LL算法的理论一个LL算法的文法分析器javacc....希望本文的实践能对大家实现自己的语法分析器带来帮助. 数学表达式问题 在学
  • LEX和YACC的PDF文件

    2009-03-07 16:55:08
    本书将教会你如何使用lex&yacc构造一个编译器lex&yacc是两个用来生成词汇分析器剖析器的工具。我假设你能够运用C 语言编程,并且理解数据结构的含义,例如“链表”“树”。导言部分描写了构建编译器所需的基本...
  • Lex & Yacc

    2014-09-25 09:41:42
    笔者实现了一个类似于Lex & Yacc编译器前端构造工具,该工具基于LALR(1)分析法,支持二义性文法,支持语法制导翻译,支持错误恢复机制,使用它我们可以构造指定词法文法的编译器前端,并且构造的分析器是线程安全...
  • Lex/Yacc 初识Lex

    千次阅读 2016-06-10 23:32:28
    因工作需要接触了一下Lex和Yacc,个人感觉挺有趣的,所以就写下来了。 Lex是Lexical的缩写,大概就可以理解为词汇提取。...Lex和Yacc是一种标准,当然会有很多的实现了,其中有2个是免费的(好像还有商业版本),那
  • 完整介绍Lex和Yacc Windows 上的使用

    热门讨论 2009-05-12 15:34:14
    完整介绍Lex和Yacc Windows 上的使用 及工具的按装, 及环境变量的设置, GNU Bison实际上是使用最广泛的Yacc-like分析器生成器,使用它可以生成解释器,编译器,协议实现等多种程序. 它不但与Yacc兼容还具有许多Yacc不...
  • C语言编译器lex和yacc编写的c语言编译器实现了C语言除了struct和指针几乎所有的语法。运行环境要求:flex bison g++11 python3中间代码生成windows命令行输入:flex compiler.lbison -vdty compiler.yg++ -std=c++11...
  • lex与yacc(二)计算器的实现 2011年09月24日 18:44:24ecbtnrt阅读数 4311 构建一个c语言的编译器并不是一件容易的事,我想每个人在学习编译原理的时候并不会常见得它非常简单. ...yacc实现有gun的bison...
  • delphi版lexyacc源码包

    2013-04-03 12:18:28
    lexyacc的pascal代码实现,词法分析语法分析,做编译器的好东西
  • lex和yacc编写的c语言编译器 词法分析与语法分析的原始文件扩展: ://www.quut.com/c/ANSI-C-grammar-l-1998.html和 实现了C语言除了struct和指针几乎所有的语法。 运行 环境要求:flex bison g ++ 11 python3 中间...
  • 利用lex和yacc做词法、语法分析

    千次阅读 2016-03-25 21:48:27
    设计一种脚本语言,再写一个翻译器,将这种脚本语言翻译成avr-gcc可以执行的C语言程序,再将得到的C语言程序利用avr-gcc编译器编译成Intel的hex文件格式,再写一个类似bootloader的东西,将这个hex文件以无线的方式...
  • 译者按:打算翻译一份lex& yacc教程,每天一点点,这个是原文的第一部分,介绍。 1. 介绍 ...lex和yacc实现细节可以在 Aho[1986]里找到。 Lex和Yacc可以在以下地方找到 1. Mor...
  • lex yacc 文献 资料

    2009-04-28 13:52:48
    利用LEX和YACC实现对SQL查询语句的语法分析.pdf 应用YACC实现MicroC编译器.pdf 对语法分析程序自动生成器YACC的改进.pdf 使用YACC生成的语法分析程序.pdf 一种可用于yacc的自动错误恢复方法.pdf 软件开发有力工具_...
  • Python Lex Yacc手册

    千次阅读 2020-02-23 22:22:46
    如果你从事编译器或解析器的开发工作,你可能对lex和yacc不会陌生,PLY是David Beazley实现的基于Python的lex和yacc。作者最著名的成就可能是其撰写的Python Cookbook, 3rd Edition。我因为偶然的原因接触了PLY,...
  • LY是纯粹由Python实现Lex和yacc(流行的编译器构建工具)。PLY的设计目标是尽可能的沿袭传统lex和yacc工具的工作方式,包括支持LALR(1)分析法、提供丰富的输入验证、错误报告和诊断。因此,如果你曾经在其他编程...
  • lex是词法分析语法分析器,本来以为这东西只有c++的呢,没想到也有delphi的 大家可以学习一下lex算法,想搞编译器的可以学习下yacc 非常不错的东西
  • 如果你从事编译器或解析器的开发工作,你可能对lex和yacc不会陌生,PLY是David Beazley实现的基于Python的lex和yacc。作者最著名的成就可能是其撰写的Python Cookbook, 3rd Edition。我因为偶然的原因接触了PLY,...
  • ply[python lex yacc]-3.2

    2009-05-23 20:04:29
    在python实现lex&yacc 词法分析语法分析,是你可以轻轻松松的构造一个编译器
  • 本项目是基于flex,bisonLLVM,使用c ++ 11实现的类C语法编译器,使用flexbindingyacc对源代码进行词法,语法分析;在语法分析阶段生成整个源代码相应的抽象语法树后,根据LLVM IR(中间表示)模块中定义的中间...
  • 编译原理 Tiny编译器和TM虚拟机

    千次阅读 2019-10-24 09:14:06
    首先,lex和yacc是开源工具,帮助开发者实现语法,词法分析。如果作为一个开发者去使用它们,就需要阅读它们的说明书,直到你会用,一句话,就是个工具而已。当然,如果你对编译原理很清楚,可以更好地理解它,甚至...
  • 装不了yacc,后面才发现原来lex和yacc是unix下的词法分析器和语法分析器,而在现在的linux系统中词法分析器和语法分析器早已经发展为了flex和bison,因此这一节我们通过flex和bison来实现一个简单编译器的功能。...
  • 1、程序功能描述 ... 文件说明:编译器本体,将PL/0代码编译为可汇编的汇编代码(asm)、并输出中间代码规约过程 开发环境:VC++2008、Parser Generator 2(LEX&&YACC集成环境) 运行...
  • 引言最近刚刚用python写完了一个解析protobuf文件的简单编译器,深感ply实现词法分析和语法分析的简洁方便。...ply是基于python的lex和yacc,而它的作者就是大名鼎鼎Python Cookbook, 3rd Edition的...
  • 本书介绍的SCC编译器,没有借助LexYacc这些编译器自动生成工具,纯手工编写而成,更便于学习理解。为了生成可以直接运行EXE文件,本书还实现了一个链接器。读完本书读者将知道一门全新的语言如何定义,一个真实...

空空如也

空空如也

1 2 3 4 5
收藏数 83
精华内容 33
关键字:

lex和yacc实现编译器