任务描述
相信大家通过flex的实验已经掌握了如何构建一个词法分析器，但是为了创建一个完整的编译程序，我们还需要一个语法分析器。同样的，我们可以使用现有的工具来节省开发的时间，也就是Unix下的YACC和GNU/Linux下的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 ‘^’
本关任务是利用YACC/Bison构建一个逆波兰符号计算器。
编程要求
根据提示，在右侧编辑器补充代码，实现加法(+)、减法(-)、乘法()、除法(/)、乘方(^)以及取负运算(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; }
| exp exp '^' { $$ = pow($1,$2); }
| exp 'n' { $$ = -1 * $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);
}
