[educoder实训]用YACC(BISON)生成语法分析和翻译器

用Bison构建逆波兰计算器

任务描述

相信大家通过flex的实验已经掌握了如何构建一个词法分析器,但是为了创建一个完整的编译程序,我们还需要一个语法分析器。同样的,我们可以使用现有的工具来节省开发的时间,也就是Unix下的YACC和GNU/Linux下的Bison。

本关任务是利用YACC/Bison构建一个逆波兰符号计算器。

相关知识

逆波兰表达式

逆波兰表达式,它的语法规定,表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。下面是一些例子:

a+b             ---> a b +
a+(b-c)         ---> a b c - +
a+(b-c)*d       ---> a b c - d * +
a+d*(b-c)       ---> a d b c - * +
a=1+3           ---> a 1 3 + =

逆波兰表达式的逻辑实现是通过栈来完成的,如果当前字符为变量或者为数字,则压栈,如果是运算符,则将栈顶两个(一个)元素弹出作相应运算,结果再入栈,最后当表达式扫描完后,栈里的就是结果。

BNF范式

由于Bison中使用的是BNF范式来描述产生式,这里先简单介绍一下BNF范式。 BNF规定是推导规则(产生式)的集合,写为: <符号> ::= <使用符号的表达式> 这里的 <符号> 是非终结符,而表达式由一个符号序列,或用指示选择的竖杠’|’分隔的多个符号序列构成,每个符号序列整体都是左端的符号的一种可能的替代。从未在左端出现的符号叫做终结符。

BNF类似一种数学游戏:从一个符号开始(叫做起始标志,实例中常用S表示),然后给出替换前面符号的规则。BNF语法定义的语言只不过是一个字符串集合,你可以按照下述规则书写,这些规则叫做书写规范(生产式规则),形式如下: symbol := alternative1 | alternative2 ...

Bison语法结构

Bison的语法结构和lex/flex类似,也是分为三个部分

/* 定义段 */
%{
C/C++头文件、全局文件、全局变量、类型定义
词法分析器yylex(采用lex进行词法分析)和错误打印函数
%}
Bison声明区间。定义之后用到的终结符、非终结符、操作符优先级
%%
/* 规则段 */
Bison语法规则定义
%%
/* 用户子程序段 */
C/C++代码 需要定义prologue区域函数,或者其他代码,生成的c/c++文件会完全拷贝这份代码。

终结符、非终结符定义 Token用于定义终结符,type定义非终结符,操作符也属于终结符,left表示左关联运算符,right表示右关联运算符,下面是一些例子:

%token NUM
%nonassoc ‘<’ /*表示该终结符无结合性 不能出现a<b<c*/
%left ‘+’ ‘-’ /*左结合 后面接操作符 下方的操作符比上方的优先级高*/
%left ‘*’ ‘/’
%right NEG  NEG表示非
%right ‘^’

编程要求

根据提示,在右侧编辑器补充代码,实现加法(+)、减法(-)、乘法(*)、除法(/)、乘方(^)以及取负运算(n)!

测试说明

平台会对你编写的代码进行测试:

测试输入:4 5 +3 4 ^2 7 + 3 /16 4 / 12 * n; 预期输出: 9 81 3 -48

 /* 逆波兰符号计算器 */
 /* 功能:能够计算出合法的后缀表达式的值,包括加法、减法、乘法、除法、乘方、取反等运算 */
 /* 说明:在下面的begin和end之间添加代码,加油吧! */
 /* 提示: */

%{
  #include <ctype.h>
  #include <stdio.h>
  #include <math.h>
  int yylex (void);
  void yyerror (char const *);
%}


%define api.value.type {double}
%token NUM

%% 

/* Grammar rules and actions follow.  */

input:
  %empty
| input line
;


line:
  '\n'
| exp '\n'      { printf ("%.10g\n", $1); }
;


exp:
  NUM           { $$ = $1;           }
 /* begin */
    | exp exp '+'   { $$ = $1 + $2;      } 
    | exp exp '-'   { $$ = $1 - $2;      } 
    | exp exp '*'   { $$ = $1 * $2;      } 
    | exp exp '/'   { $$ = $1 / $2;      } 
    /* Exponentiation */ 
    | exp exp '^'   { $$ = pow ($1, $2); } 
    /* Unary minus    */ 
    | exp 'n'       { $$ = -$1;          } 





 /* end */
;

%%

/* The lexical analyzer returns a double floating point
   number on the stack and the token NUM, or the numeric code
   of the character read if not a number.  It skips all blanks
   and tabs, and returns 0 for end-of-input.  */


int yylex (void)
{
  int c;

  /* Skip white space.  */
  while ((c = getchar ()) == ' ' || c == '\t')
    continue;

  /* Process numbers.  */
  if (c == '.' || isdigit (c))
    {
      ungetc (c, stdin);
      scanf ("%lf", &yylval);
      return NUM;
    }

  /* Return end-of-input.  */
  if (c == EOF)
    return 0;
  if (c == '!')
  	return 0;
  /* Return a single char.  */
  return c;
}

int main (int argc, char** argv)
{
  return yyparse();
}


/* Called by yyparse on error.  */
void yyerror (char const *s)
{
  fprintf (stderr, "%s\n", s);
}

参考链接:

© 版权声明
THE END
喜欢就支持以下吧
点赞1赞赏
分享
评论 抢沙发

请登录后发表评论