编译原理——基于LR分析表编写语法分析器与基于WINDOWS下FLEX与BISON的计算器实现

#include <iostream>
#include <string>
#include <cstring>
#include <stack>


using namespace std;


const char MOVE_IN = 'S';
const char REDUCTION = 'R';

const string ANALYSIS_TABLE[12][9] = {
	{"S4", "", "S3", "", "", "", "", "1", "2"},
	{"", "S8", "", "", "", "", "ACC", "", ""},
	{"", "R2", "", "R2", "", "R2", "R2", "", ""},
	{"S4", "", "S3", "", "", "", "", "5", "2"},
	{"", "R4", "", "R4", "S6", "R4", "R4", "", ""},
	{"", "S8", "", "S9", "", "", "", "", ""},
	{"S4", "", "S3", "", "", "", "", "7", "2"},
	{"", "S8", "", "", "", "S11", "", "", ""},
	{"S4", "", "S3", "", "", "", "", "", "10"},
	{"", "R3", "", "R3", "", "R3", "R3", "", ""},
	{"", "R1", "", "R1", "", "R1", "R1", "", ""},
	{"", "R5", "", "R5", "", "R5", "R5", "", ""},
};

const string GRAMMAR[6] = {
	"S E",
	"E E+T",
	"E T",
	"T (E)",
	"T i",
	"T i[E]"
};


int get_symbol_index(char symbol) {

	int symbol_index = !isalpha(symbol);
	if (symbol_index)
	{
		switch (symbol)
		{
		case '+':
			symbol_index = 1;
			break;
		case '(':
			symbol_index = 2;
			break;
		case ')':
			symbol_index = 3;
			break;
		case '[':
			symbol_index = 4;
			break;
		case ']':
			symbol_index = 5;
			break;
		case '#':
			symbol_index = 6;
			break;
		default:
			symbol_index = -1;
			break;
		}
	}

	return symbol_index;
}


void lexical_analysis(char *input_str) {

	stack<int> state_stack;
	stack<char> symbol_stack;
	int symbol_index, state_stack_top, state;
	string action;
	char action_type;

	
	// init
	state_stack.push(0);
	symbol_stack.push('#');

	while (true) {

		symbol_index = get_symbol_index(*input_str);
		state_stack_top = state_stack.top();
		action = ANALYSIS_TABLE[state_stack_top][symbol_index];

		if (action == "ACC" || !action.length())
			break;

		action_type = action[0];
		state = atoi(action.substr(1).c_str());

		if (action_type == MOVE_IN)
		{
			// S
			state_stack.push(state);

			//input_str++;
			if (isalpha(*input_str))
			{
				symbol_stack.push('i');		// i means id
				while (isalpha(*input_str) || isdigit(*input_str) || *input_str == '_')
					input_str++;
			}
			else
			{
				symbol_stack.push(*input_str);
				input_str++;
			}

			while (isblank(*input_str))
				input_str++;
			
			if (!isalpha(*input_str) && *input_str != '_' && *input_str != '+' &&
				*input_str != '(' &&  *input_str != ')' &&  *input_str != '[' &&  *input_str != ']' &&  *input_str != '#')
				break;
				
		}
		else if (action_type == REDUCTION)
		{
			// R
			string reduction_grammar = GRAMMAR[state];
			char reduction_result = reduction_grammar[0];
			string reduction = reduction_grammar.substr(2);

			for (int i = 0; i < reduction.length(); i++) {
				state_stack.pop();
				symbol_stack.pop();
			}

			state_stack_top = state_stack.top();
			if (reduction_result == 'E')
				state = atoi(ANALYSIS_TABLE[state_stack_top][7].c_str());		// E GOTO
			else if (reduction_result == 'T')
				state = atoi(ANALYSIS_TABLE[state_stack_top][8].c_str());		// T GOTO
			else {
				// err
			}
			state_stack.push(state);
			symbol_stack.push(reduction_result);

		}
		else
		{
			//err
		}

	}
	
	if (action == "ACC")
		cout << "Syntax analysis is right";
	else
		cout << "Error on syntax analysis";
}


int main() {

	char input_str[100];
	cin.getline(input_str, 100);
	int len = strlen(input_str);
	input_str[len+1] = input_str[len];
	input_str[len] = '#';
	//char str[] = {'i','+','(','i','+','i' ,')','#'};

	lexical_analysis(input_str);
	
	system("pause");
	return 0;
}

2.4 测试样例

（1）输入：a1 + a2
输出：Syntax analysis is right

（2）输入：a1 + (a2)
输出：Syntax analysis is right

（3）输入：a1++a2
输出：Error on syntax analysis

（4）输入a1[a2 + a3] + a4 + a5
输出：Syntax analysis is right

（5）输入：a1 + a2[a3] + a4 + (a5 + a6)
输出：Syntax analysis is right

三、基于WINDOWS下FLEX与BISON的计算器实现

3.1 需求描述

【问题描述】 基于词法分析程序自动构造工具Flex与语法分析程序自动构造工具Bison，编制简单的计算器程序。用Flex和Bison实现一个功能更为强大的计算器，尽可能多的包含以下运算（支持浮点数）：

a) 加、减、乘、除运算

b) 乘方power、开方sqrt运算

c) 位运算 – 与、或、非…（不做）

d) 三角函数运算 – sin、cos…

e) 求阶乘

f) 求模（不做）

g) 求log以e为底的对数（不做）

h) 求log以10为底的对数

【输入形式】 数学表达式
【输出形式】 表达式的计算结果
【样例输入】 3+5*2
【样例输出】 13

3.2 Flex 源码

// fb1-5.l

%option noyywrap
%{
#define YYSTYPE double
#include"fb1-5.tab.h"
%}
 
%%
"+"     { return ADD; }
"-"     { return SUB; }
"*"     { return MUL; }
"/"     { return DIV; }
"|"     { return ABS; }
"("     { return OP; }
")"     { return CP; }
","     { return SEG; }
"!"		{ return FAC;}
"pow"	{ return POW; }
"sin"	{ return SIN; }
"cos"	{ return COS; }
"tan"	{ return TAN; }
"log"	{ return LOG; }
"sqrt"	{ return SQRT; }
""
([0-9]*\.?[0-9]+|[0-9]+\.)  { yylval = atof(yytext); return NUMBER;}
\n      { return EOL; }
<<EOF>> { return END; }
"//".* 
[ \t]   { /* ignore white space */ }
.      { yyerror("Mystery character%c\n", *yytext); }
%%

3.3 Bison 源码

// fb1-5.y

%{

#define YYSTYPE double
#include<stdio.h>
#include<math.h>
#define PI 3.14159265

%}

/* declare tokens*/
%token NUMBER
%left ADD SUB 
%left MUL DIV ABS
%left SQRT POW COS SIN TAN LOG FAC
%token OP CP SEG
%token EOL END

%%

calclist: /*nothing */
 | calclist exp EOL { printf("%g", $2); }
 | calclist exp END { printf("%g", $2); YYACCEPT;}
 | calclist EOL { printf(""); }/* blank line or a comment */
 ;

exp: factor
 | exp ADD exp { $$ = $1 + $3; }
 | exp SUB factor { $$ = $1 - $3; }
 ;

factor: term
 | factor MUL term { $$ = $1 * $3; }
 | factor DIV term { $$ = $1 / $3; } 
 ;

term: NUMBER
 | term FAC { 
	for(int i=1;i<$1;i++)
		$$ *= i;
 }
 | ABS term { $$ = $2 >= 0? $2 : - $2; }
 | SQRT OP exp CP { $$ = sqrt($3); }
 | COS OP exp CP { $$ = cos($3*PI/180); }
 | SIN OP exp CP { $$ = sin($3*PI/180); }
 | TAN OP exp CP { $$ = tan($3*PI/180); }
 | LOG OP exp CP { $$ = log10($3); } 
 | OP exp CP { $$ = $2; }
 | POW OP exp SEG exp CP { $$ = pow($3, $5); }
 ;

%%

main()
{
  yyparse();
}

yyerror(char *s)
{
  fprintf(stderr, "error: %s\n", s);
}