Mac下利用Flex和Bison实现控制台计算器

里克贝斯

发布于 2021-05-21 16:30:06

1.7K0

发布于 2021-05-21 16:30:06

文章被收录于专栏：图灵技术域图灵技术域

简介

我们借助Flex和Bison对给定的表达式进行词法和语法分析，并在语法分析的同时完成相应的计算。

用 Flex 和 Bison 实现一个功能更为强大的计算器，包含以下运算：

a) 加、减、乘、除运算
b) 乘方、开方运算
c) 位运算– 与 & 、或 |、非 ~
d) 阶乘运算 !
e)三角运算sin cos tan

Lex和Yacc是unix系统上面的词法和语法分析的自动化处理工具，http://dinosaur.compilertools.net/上有对两者详细的介绍。后人在此基础之上开发了基本兼容的版本Flex和Bison。

Flex使用手册：http://tinf2.vub.ac.be/~dvermeir/courses/compilers/flex/flex_toc.html

Bison使用手册：http://www.gnu.org/software/bison/manual/index.html

环境配置

环境类Unix系统：macOS 10.14.2

由于Unix系统自带yacc，因此需要配置bison与flex软件包。

在从App Store上下载Xcode后，默认是不会安装Command Line Tools的，Command Line Tools是在Xcode中的一款工具，可以在命令行中运行C程序。为了配置编译原理的环境，我们需要安装Xcode Command Line Tools。

在终端中输入以下命令：xcode-select –install ，按回车；

随后下载完毕，查看Xcode Command Line Tools中的程序,可以看到存在bison和flex两个文件。

接下来就可以进行计算器的编写。

查看bison的信息：

可以看到此时的bison版本为2.3

代码编写

新建一个文件夹用来存放编写的文件。
词法分析flex的使用
定义一个flex的输入文件，描述词法。该文件以.l结尾，可以分成三个部分。

1	%{ 到 }% 标记的部分。此部分会原封不动的复制到flex的生成代码中。文件开头定义了一个YYSTYPE宏。每个TOKEN可以有一个lval值属性， YYSTYPE定义类型就是token的lval的类型。 _EasyTData是我们的web服务层和web页面层公用的通用数据结构。另外包括一些include的头文件
2	从 % } 到 % % 之间的部分，这部分用正则表达式定义了一些数据类型。比如int num string ignore_char identifier等。注意这里使用的正则表达式的形式是ERE而不是BRE。 ERE与BRE比较明显的区别就是， ERE使用+表示字符重复一次以上，*表示字符重复0次以上。 BRE使用{1,}这种方式表示字符重a
3	文件的第三部分，是% % 到% % 的部分。这里定义了词法分析器在解析的处理动作。 yytext是一个flex内部的标识符，表示匹配到的字符串。上文介绍了，lval也是一个内部标识符，表示TOKEN的值。 json2tdata_是标识符的前缀, 在执行flex的时候，用-P指定。

a.l文件代码：

%{
    /*
     *  2018 Calculation
     */
    int yywrap();
    #define YYSTYPE double
    void yyerror(char*);
    #include "a.tab.h"
%}

%%

     /* a-z为变量 */   
[a-z]   {
            yylval = *yytext - 'a';
            return VARIABLE;
        }
    /*16进制数*/
0x\.?[a-f0-9]+|0x[a-f0-9]+\.[a-f0-9]* {
            yylval=atof(yytext);
            return HEXADECIMAL;
        }

    /* 实数部分 */
\.?[0-9]+|[0-9]+\.[0-9]*    {
            yylval = atof(yytext);
            return INTEGER;
        }

    /* 运算符 */
[-+()=/*&|~!^@\n]  {return *yytext;}

    /* 三角函数 */
sin {
    return SIN;
    }

cos {
    return COS;
    }
tan {
    return TAN;
    }
    /* 空白被忽略 */
[ \t]    ;

    /* 其他字符都是非法的 */
.    yyerror("警告！输入无效ERROR！");

%%
int yywrap()
{return 1;}

用flex程序处理这个文件，生成对应的C语言源代码文件yy.c

处理命令：flex a.l

该文件较长，在此便不再贴出内容。

语法分析器bison的使用
写bison文件，以.y作为后缀名结尾，和flex的词法分析输入文件类似，bison的输入文件也是分成3部分（不是巧合）

1	第一部分% {和% }之间，是原封不动拷贝到输出的C语言源文件中的。 json2tdata_lex这个函数是flex生成的。 json2tdata_error是用来处理错误信息的函数。通过定义和实现这个函数你可以把错误信息写到任何地方。与flex类似，json2tdata也是自定义的前缀。
2	%token INT NUM STRING R_BRACKET COLON SEMICOLON COMMA IDENTIFIER TRUE FALSE NIL这一行，这一行的作用就是声明在flex中定义的那些TOKEN。
3	% % % %包围的部分。这部分就是语法的推导过程。可以比较轻松的看出，这部分主要就是采用BNF对语法进行描述。比如Array，它有两种形式。第一种是 L_BRACKET ELEMENTS R_BRACKET, 第二种则是L_BRACKET R_BRACKET，这表示一个空的Array。 Bison能够完全支持LR(1)文法。这种文法的特点是只要多向前看一个TOKEN，就能够决定如何解析。因此如果bison告诉你语法ambiguous的时候，可以想一想如何把自己的文法改成LR(1)型文法。另外，每一条规则的后面可以用{}来定义解析的动作 bison用$$表示规则左边的对象，用$1 $2 $3 等依次表示规则右边的对象。

第一部分% {和% }之间，是原封不动拷贝到输出的C语言源文件中的。 json2tdata_lex这个函数是flex生成的。 json2tdata_error是用来处理错误信息的函数。通过定义和实现这个函数你可以把错误信息写到任何地方。与flex类似，json2tdata也是自定义的前缀。

%token INT NUM STRING R_BRACKET COLON SEMICOLON COMMA IDENTIFIER TRUE FALSE NIL这一行，这一行的作用就是声明在flex中定义的那些TOKEN。

% % % %包围的部分。这部分就是语法的推导过程。可以比较轻松的看出，这部分主要就是采用BNF对语法进行描述。比如Array，它有两种形式。第一种是 L_BRACKET ELEMENTS R_BRACKET, 第二种则是L_BRACKET R_BRACKET，这表示一个空的Array。 Bison能够完全支持LR(1)文法。这种文法的特点是只要多向前看一个TOKEN，就能够决定如何解析。因此如果bison告诉你语法ambiguous的时候，可以想一想如何把自己的文法改成LR(1)型文法。另外，每一条规则的后面可以用{}来定义解析的动作 bison用$$表示规则左边的对象，用$1 $2 $3 等依次表示规则右边的对象。

a.y代码：

%token   HEXADECIMAL INTEGER VARIABLE SIN COS TAN
%left    '+' '-'
%left    '*' '/'
%left    '&'
%left    '|'
%left    '^'
%right   '@''~'
%left    '!'

%{

/*for Xcode */
/*  #define  __STDC__   0   */   

    #include <stdio.h>   
    #include <math.h>
    #define YYSTYPE double
    #define pi 3.1415926 
    void yyerror(char*);
    int yylex(void);

    double sym[26];
%}

%%
program:
    program statement '\n'
    |
    ;
statement:
     expr    {printf("=%lf\n[calculation]:$ ", $1);}
     |VARIABLE '=' expr    {sym[(int)$1] = $3;}
     ;
expr:
    INTEGER
    |HEXADECIMAL
    |VARIABLE{$$ = sym[(int)$1];}
    |expr '+' expr    {$$ = $1 + $3;}
    |expr '-' expr    {$$ = $1 - $3;}
    |expr '*' expr    {$$ = $1 * $3;}
    |expr '/' expr    {$$ = $1 / $3;}
    |expr '&' expr    {$$ = (int)$1 & (int)$3;}
    |expr '|' expr    {$$ = (int)$1 | (int)$3;}
    |'~' expr         {$$ = ~(int)$2;}
    |'@' expr         {$$ = sqrt($2);}
    |expr '@' expr    {$$ = $1*sqrt($3);}
    |expr '!'         {int i=1,s=1;for(;i<=$2;i++)s*=i;$$=s;}
    |expr '^' expr    {$$=pow($1,$3);}
    |'('expr')'       {$$ = $2;}
    |SIN'('expr')'       {$$ = sin($3*pi/180.0);}
    |COS'('expr')'       {$$ = cos($3*pi/180.0);}
    |TAN'('expr')'       {$$ = tan($3*pi/180.0);}
    ;

%%

void yyerror(char* s)
{
    fprintf(stderr, "---%s\n", s);
}

int main(void)
{
    printf("计算器\n支持的运算符：+-*/&|~!^@ \n");
    printf("+: 加法 2+3 \n");
    printf("-: 减法 2-3 \n");
    printf("*: 乘法 2*3 \n");
    printf("/: 除法 2/3 \n");
    printf("！: 阶乘 2！\n");
    printf("^: 乘方  2^3 \n");
    printf("^: 开方  2@3 \n");
    printf("&: 与 2&3 结果为二进制转化的十进制数\n");
    printf("|: 或 2|3 结果为二进制转化的十进制数\n");
    printf("~: 非 2|3 结果为二进制转化的十进制数\n");
    printf("sin: 正弦值  sin(30) 单位为rad \n");
    printf("sin: 余弦值  cos(30) 单位为rad \n");
    printf("tan: 正切值  tan(30) 单位为rad \n");
    yyparse();
    return 0;
}