`

递归下降分析的计算算术表达式的解释器

递归下降分析算术表达式编译原理 
阅读更多 
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <map>
#include <iostream>
using namespace std;
#define ID 1
#define ERROR 255

enum TYPE{
	INT=1,
	FLOAT,
	CHAR,
};
struct Value{
	TYPE type;
	union {
		int v1;
		double v2;
		char *v3;
	};
	template<typename T>

	void setValue(T v){
		if(type == FLOAT){
			v2 =v;
		}
		else if(type==INT){
			v1=v;
		}
	}
	template<typename T>
	T getValue(T x){
		if(type == FLOAT){
			return v2;
		}
		else if(type==INT){
			return v1;
		}
	}
};
struct Expression{
	enum{

		NUM_INT =2,
		NUM_FLOAT
		, PLUS 
		, MINUS // ‘-‘
		, TIMERS // ‘*’
		, OVER // ‘/’
		, LPAREN // ‘(‘
		, RPAREN // ‘)’
		, MOD,
		NOT,
		LOGIC_NOT,
		LOGIC_AND,
		LOGIC_OR,
		LOGIC_XOR,
		ASSIGN,
		LT,
		GT,
		//占2个字符
		AND,
		OR,
		LE,
		GE,
		EQ,
		NE,

	}

	;

	char *nextchar;
	string token;
	void settoken( char* expr){
		token=expr;
		nextchar=expr;
	}

	int gettoken()
	{

		while(isspace(*nextchar)){
			nextchar++;
		}
		switch(*nextchar)
		{
		case '+': nextchar++; return PLUS;
		case '-': nextchar++; return MINUS;
		case '*': nextchar++; return TIMERS;
		case '/': nextchar++; return OVER;
		case '%': nextchar++; return MOD;
		case '(': nextchar++; return LPAREN;
		case ')': nextchar++; return RPAREN;

		case '&':nextchar++;
			if(*nextchar=='&'){nextchar++;return AND;}
			else {
				return LOGIC_AND;
			}

		case '!':nextchar++; 
			if(*nextchar=='='){
				nextchar++;return NE;}
			else {
				return NOT;
			}

		case '|':nextchar++; 
			if(*nextchar=='|'){
				nextchar++;return OR;}
			else {
				return LOGIC_OR;
			}
		case '<':nextchar++; 
			if(*nextchar=='='){
				nextchar++;return LE;}
			else {
				return LT;
			}

		case '>':nextchar++; 
			if(*nextchar=='='){
				nextchar++;return GE;}
			else {
				return GT;
			}
		case '=':nextchar++; 
			if(*nextchar=='='){
				nextchar++;return EQ;}
			else {
				return ASSIGN;
			}


		default: break;
		}
		if(isalpha(*nextchar))
		{
			char *beg = nextchar;
			char *end= nextchar;
			while(isalpha(*nextchar) || isdigit(*nextchar))
			{
				nextchar++;
			}
			PRINT_TOKEN(beg,end);
			token=(beg,end);
			return ID;
		}
		// NUM 的词法识别分析
		// NUM := 0(X|x)[digit|A-F|a-f]+
		// NUM := [digit]+
		// NUM := [digit]* \.[digit]+
		char *last = nextchar;
		if(isdigit(*nextchar))
		{
			char *beg = nextchar;
			char *end= nextchar;
			int digitType=0;

			//是16进制么
			if(*nextchar=='0'&& (*(1+nextchar)=='x'||*(1+nextchar)=='X'))
			{
				nextchar +=2;
				//beg=nextchar;
				while(isdigit(*nextchar) ||(*nextchar>='a'&& *nextchar<='f')||(*nextchar>='A'&& *nextchar<='F')){
					nextchar++;
					end++;
				}
			}

			else{
				if(*nextchar=='0' && *(nextchar+1)!=NULL && (*(1+nextchar)!='x'||*(1+nextchar)!='X')){
					fprintf(stderr,"not support 8 decimal,%s ",nextchar);
				}
				int dotOccur=0;
				while(isdigit(*nextchar) ||(*nextchar=='.'&&dotOccur==0))
				{
					if(*nextchar=='.')
					{
						dotOccur=1;
					}
					nextchar++;
					end++;
				}
				if(dotOccur==0){
					digitType= INT;
				}
				else{
					digitType=FLOAT;
				}
			}
			PRINT_TOKEN(beg,end);
			if(beg==end){
				fprintf(stderr,"parse error: %s",beg);
			}
			token= string(beg,end);
			if(digitType==INT){
				return NUM_INT;
			}
			else{
				return NUM_FLOAT;
			}
		}
		return ERROR;
	}
	//E := T+E |T
	//T := F*T | F
	//F := (E)|(!E)|ID

	void Statements(){
		//Statements = [statement]+
	}
	void Statement(){
		//S :=;|{}
		//IF_STATEMENT='if'S;
		//ELSE_STATEMENT='else'S;
		//EXPR_STATEMENT=E;
		//BLOCK_STATEMENT ={S}

	}
	Value Assign(){
		// id=E();
		char *last = nextchar;
		int leftType = gettoken();
		bool flag=false;

		string id;
		if(leftType==ID){
			id = token;
			int opType = gettoken();
			if(opType == ASSIGN){
				flag=true;
			}
		}
		if(flag){
			Value val = Assign();
			symTable[id]=val;
			return val;
		}
		else{
			nextchar = last;
			return E();
		}
		
	}
	Value E()
	{
		//bug:二元运算符的字符个数 ^=,^,赋值运算符=和==
		Value left = T(); // 对应文法中的第一个Term
		Value r;
		int tokentype;
		while(*nextchar == '+' || *nextchar == '-' ||
			*nextchar == '|' || *nextchar == '^'
			|| *nextchar=='<' || *nextchar=='>' ||
			*nextchar == '='||
			(*nextchar == '!'&&*(nextchar+1)=='=')
			)
		{
			tokentype = gettoken();
			switch(tokentype)
			{
			case PLUS:
				//printf("PLUS");
				r = T();
				{
					Value result;
					result.type = (r.type ==FLOAT||left.type == FLOAT)?FLOAT:INT;
					result.setValue(left.getValue(left.type==INT?1:0.1) + r.getValue(r.type==INT?1:0.1));
					left = result;
				}
				break;
			case MINUS:
				//printf("MINUS");
				r = T();
				{
					Value result;
					result.type = (r.type ==FLOAT||left.type == FLOAT)?FLOAT:INT;
					result.setValue(left.getValue(left.type==INT?1:0.1) - r.getValue(r.type==INT?1:0.1));
					left = result;
				}
				break;
			case LOGIC_OR:
				//printf("LOGIC_OR");
				r = T();
				if(r.type ==FLOAT||left.type == FLOAT){
					fprintf(stderr,"error, not support float LOGIC_OR");
				}
				{
					Value result;
					result.type = INT;
					result.setValue((int)left.getValue(left.type==INT?1:0.1) | (int)r.getValue(r.type==INT?1:0.1));
					left = result;
				}
				break;
			case LOGIC_XOR:
				r = T();
				if(r.type ==FLOAT||left.type == FLOAT){
					fprintf(stderr,"error, not support Float XOR");
				}
				{
					Value result;
					result.type = INT;
					result.setValue((int)left.getValue(left.type==INT?1:0.1) ^(int) r.getValue(r.type==INT?1:0.1));
					left = result;
				}
				break;
			case OR:
				r = T();
				if(r.type ==FLOAT||left.type == FLOAT){
					fprintf(stderr,"error, not support Float OR");
				}
				{
					Value result;
					result.type = INT;
					result.setValue((int)left.getValue(left.type==INT?1:0.1) || (int)r.getValue(r.type==INT?1:0.1));
					left = result;
				}				
				break;
			case LT:
				//printf("LT");

				r = T();
				{
					Value result;
					result.type = INT;
					result.setValue(left.getValue(left.type==INT?1:0.1) < r.getValue(r.type==INT?1:0.1));
					left = result;
				}
				break;
			case LE:
				r = T();
				//printf("LE");
				{
					Value result;
					result.type = INT;
					result.setValue(left.getValue(left.type==INT?1:0.1) <= r.getValue(r.type==INT?1:0.1));
					left = result;
				}
				break;
			case GT:
				r = T();
				//printf("GT");
				{
					Value result;
					result.type = INT;
					result.setValue(left.getValue(left.type==INT?1:0.1) > r.getValue(r.type==INT?1:0.1));
					left = result;
				}
				break;
			case GE:
				r= T();
				{
					Value result;
					result.type = INT;
					result.setValue(left.getValue(left.type==INT?1:0.1) >= r.getValue(r.type==INT?1:0.1));
					left = result;
				}
				break;
			case NE:
				r = T();
				{
					Value result;
					result.type = INT;
					result.setValue(left.getValue(left.type==INT?1:0.1) != r.getValue(r.type==INT?1:0.1));
					left = result;
				}
				break;
			default:
				break;
			}
		}
		return left;
	}
	Value T()
	{
		Value left;
		int tokentype;
		left = F(); 
		Value r;
		while(*nextchar == '*' || *nextchar == '/' ||  *nextchar == '%' || *nextchar == '&' ) 
		{
			tokentype =gettoken();

			switch(tokentype)
			{
			case TIMERS:
				//printf("TIMERS");
				r = T();
				{
					Value result;
					result.type = (r.type ==FLOAT||left.type == FLOAT)?FLOAT:INT;
					result.setValue(left.getValue(left.type==INT?1:0.1) * r.getValue(r.type==INT?1:0.1));
					left = result;
				}

				break;
			case OVER:
				r = T();
				{								
					Value result;
					result.type = (r.type ==FLOAT||left.type == FLOAT)?FLOAT:INT;
					result.setValue(left.getValue(left.type==INT?1:0.1) / r.getValue(r.type==INT?1:0.1));
					left = result;
				}

				break;
			case MOD:
				r = T();
				if(r.type ==FLOAT||left.type == FLOAT){
					fprintf(stderr,"not support float % operator");
					//left.type == FLOAT;
					//left.setValue(left.getValue() %r.getValue());
				}
				{
					Value result;
					result.type = INT;
					result.setValue((int)left.getValue(left.type==INT?1:0.1) %(int) r.getValue(r.type==INT?1:0.1));
					left = result;
				}

				break;
			case LOGIC_AND:
				r = T();
				if(r.type ==FLOAT||left.type == FLOAT){
					fprintf(stderr,"not support float & operator");
					//left.type == FLOAT;
					//left.setValue(left.getValue() %r.getValue());
				}
				{
					Value result;
					result.type = INT;
					result.setValue((int)left.getValue(left.type==INT?1:0.1) &(int) r.getValue(r.type==INT?1:0.1));
					left = result;
				}
				break;
			case AND:
				//printf("AND");
				r = T();
				{
					Value result;
					result.type = INT;
					result.setValue((int)left.getValue(left.type==INT?1:0.1) &&(int) r.getValue(r.type==INT?1:0.1));
					left = result;
				}

				break;
			default:
				break;
			}
		}
		return left;
	}

	Value F()
	{
		Value number;
		switch(gettoken())
		{
		case ID: 
			//printf("ID");
			//number《-- 赋值id
			number = symTable[token];
			break;
		case NUM_INT:
			//printf("NUM");
			if(token[0]=='0' && token.size()>3 && (token[1]=='X'||token[1]=='x'))
			{
				number.type = INT;
				int v;
				sscanf(token.c_str(),"%x",&v);
				number.setValue(v);

			}else
			{
				number.type=INT;
				number.setValue(atoi(token.c_str()));
			}

			break;
		case NUM_FLOAT:
			number.type=FLOAT;
			number.setValue(atof(token.c_str()));
			break;
		case LPAREN:
			//printf("LPAREN");
			number = E();
			if(gettoken()
				!= RPAREN){
					printf("lost ')' in the expression \n");
			}
			break;
		case NOT:
			//printf("NOT");
			number = F();			
			
			number.setValue(!(int)number.getValue(1));
			number.type = INT;
			break;
		case LOGIC_NOT:
			//printf("LOGIC_NOT");
			number =E();
			if(number.type!=INT){
				fprintf(stderr,"not suport FLOAT !");
			}
			number.setValue(~(int)number.getValue(1));
			number.type = INT;
			break;
		case MINUS:
			number =E();
			if(number.type==INT)
			{
				number.setValue(-number.getValue(1));
			}
			else{
				number.setValue(-number.getValue(0.1));
			}
		default:
			break;
		}
		return number;
	}
	void PRINT_TOKEN(const char *beg,const char*end){
		for(const char* p=beg;p!=end;p++){
			//printf("%c",*p);
		}


	}
	map<string,Value> symTable;
};
using namespace std;

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

	Expression e;
	e.settoken("3+5*(7+2)");

	Value v ;

	v= e.E();
	if(v.type==INT){
		cout<<"TYPE=INT"<<endl;
	}
	else{
		cout<<"TYPE=FLOAT"<<endl;
	}
	cout<< ((v.type==INT)?v.getValue(1):v.getValue(0.1))<<endl;

	e.settoken("3+5<(7+1.0)");
	v=e.E();
	cout<< ((v.type==INT)?v.getValue(1):v.getValue(0.1))<<endl;
	e.settoken("3+(5.0<(7+1.0))||0");
	v=e.E();
	cout<<"expect:"<<(3+(5.0<(7+1.0))||0)<<"--real:"<< ((v.type==INT)?v.getValue(1):v.getValue(0.1))<<endl;


	e.settoken("3+5.0<=(7+1.0))&&(-7/6.0)<0");
	v=e.E();
	cout<<"expect:"<<(3+5.0<=(7+1.0)&&(-7/6.0)<0)<<"--real:"<<((v.type==INT)?v.getValue(1):v.getValue(0.1))<<endl;
	//printf("\n%d",e.E());

	//单元运算符出错，因为是右结合的，递归下降分析比较复杂
	e.settoken("(-7/6.0)");
	v=e.E();
	cout<<"expect:"<<(-7/6.0)<<"--real:"<<((v.type==INT)?v.getValue(1):v.getValue(0.1))<<endl;

	e.settoken("-(7/6.0)");
	v=e.E();
	cout<<"expect:"<<-(7/6.0)<<"--real:"<<((v.type==INT)?v.getValue(1):v.getValue(0.1))<<endl;


	e.settoken("-3+5");
	v=e.E();
	cout<<"expect:"<<-3+5<<"--real:"<<((v.type==INT)?v.getValue(1):v.getValue(0.1))<<endl;


	e.settoken("!3+9");
	v=e.E();
	cout<<"expect:"<<!3+9<<"--real:"<<((v.type==INT)?v.getValue(1):v.getValue(0.1))<<endl;


	e.settoken("!(3+9)");
	v=e.E();
	cout<<"expect:"<<!(3+9)<<"--real:"<<((v.type==INT)?v.getValue(1):v.getValue(0.1))<<endl;

	//e.settoken("3+6==(7+2)");
	//printf("\n%d",e.E());

	getchar();
	return 0;
}

 

上周五闲着无事，重新写了算术表达式，采用C/C++表达，目前支持 +，-，* 、%，()括号，运算符优先级

，同时支持整形和浮点型。

 

思路：

（1）递归下降分析，属性制导翻译（没有完全实现，但实现了部分，继承属性，综合属性）

E=T|T+E

T=T*F

F=id|(E)|-E|!E

（2）其实也支持其他很多运算符，如：比较运算符，（但没有特别处理运算符优先级，因此会出错，比如3<5+7,会翻译成(3<5)+7；逻辑运算符

（3）调用E()函数得到的是算术表达式的值，有机会的话，改造成，支持多个语句，以及语句块，嗯，用YacC和Lex试试。

 

 

分享到：
| eclipselink，MOXy，JAXB，Json工具类
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    递归下降语法分析器 算术表达式 C语言

    本项目聚焦于使用递归下降分析法来解析C语言中的算术表达式。递归下降分析是一种自顶向下的解析策略，它通过递归调用来解析输入的语法结构。 首先，我们要理解什么是算术表达式。在编程语言中，算术表达式通常包含...

    算术表达式递归下降分析程序设计

    在计算机科学中，递归下降分析（Recursive Descent Parsing）是一种自顶向下的解析方法，常用于编译器和解释器的设计中。本项目的目标是设计一个C++源程序，用于解析给定的算术表达式。根据描述，提供的算术表达式...

    递归下降分析法模拟c++

    本实验旨在通过C++编程语言，让学生深入理解和应用递归下降分析法来解析和计算表达式。 递归下降分析法，也称为递归下降解析或自顶向下解析，是基于上下文无关文法（Context-Free Grammar, CFG）的一种解析策略。在...

    编译原理实验报告-算术表达式解释器的设计与实现

    在本篇《编译原理》课程的实验报告中，学生黄小燕设计并实现了一个算术表达式解释器。实验的主要目标是理解并运用自顶向下语法分析的原理，熟悉递归下降子程序分析法，以及掌握语法制导翻译方法。实验要求编写一个...

    java解释算术表达式

    在实现Java算术表达式解释器时，可以使用递归下降解析（Recursive Descent Parsing）方法，这是一种基于上下文无关文法的解析技术。例如，可以定义一个`Parser`类，包含一系列方法来匹配不同的算术表达式部分，如`...

    数据结构算术表达式

    理解并正确处理优先级是解析和计算算术表达式的关键。 5. **数据结构的应用**： 在处理算术表达式时，可以使用多种数据结构，如栈、队列、链表和树。栈用于后缀表达式的计算，队列可用于广度优先搜索（BFS）来构建...

    数据结构试验 算术表达式

    在这个实验中，我们将用C语言来编写代码，解析和计算算术表达式。这通常涉及以下几个步骤： 1. **词法分析**：将输入的字符串分解为一个个有意义的单元，称为标记（tokens），如数字、运算符和括号。这是通过创建一...

    yufa.rar_用递归下降法分析表达式实验_递归下降实验

    在编程语言处理领域，语法分析是编译器或解释器设计中的关键步骤，它将源代码转换为中间形式，以便进一步处理。递归下降分析法（Recursive Descent Parsing）是一种常用的自顶向下语法分析方法，尤其适用于上下文...

    算术表达式

    算术表达式求值广泛应用于各种编程语言的编译器、解释器以及脚本引擎中，是实现表达式计算的基础。例如，计算器应用、编程语言的表达式计算、数据库查询中的SQL语句等，都需要对算术表达式进行求值。 总之，理解和...

    算术表达式计算(有文档）

    1. **解析算法**：如何将字符串形式的算术表达式转化为可计算的形式，如使用递归下降解析器，它能处理复杂的运算符优先级和括号。 2. **中间表示**：在计算前，可能需要将原始表达式转换为一种中间表示，如后缀...

    C语言 算术表达式 计算器

    这个计算器并不依赖于栈来解析和求解表达式，而是采用了另一种实现方式，这可能涉及到自底向上的语法分析或者递归下降解析等技术。 在C语言中，实现一个算术表达式计算器首先要理解基础的数据类型，如int、float等...

    算术表达式（利用后缀表达式）

    在计算机科学中，算术表达式的处理是一项基本任务，它涉及到计算、解析和评估复杂的数学公式。本主题主要关注一种高效...在实际的编程项目中，特别是在编译器设计、解释器实现以及各种计算任务中，这一方法被广泛应用。

    语法分析程序（递归下降）

    在本资源中，我们关注的是递归下降语法分析方法，这是一种基于解析器构造的解析技术，尤其适用于上下文无关文法。下面我们将详细探讨递归下降分析的工作原理、Java实现以及其在实际编程中的应用。 递归下降分析是...

    VC算术表达式文法分析

    文法分析器，也称为解析器，根据这些文法规则来判断输入的字符串（在这里是算术表达式）是否合法，并构建出抽象语法树（Abstract Syntax Tree, AST），以便后续的编译或解释阶段使用。 在VC环境下，我们通常会使用...

    计算机编译原理—试验指导书—递归下降语法分析

    实验的核心在于构建递归下降分析程序，它主要针对四种基本的语句类型：赋值语句、算术表达式运算、while循环语句以及if分支语句。这些语句构成了高级语言的基础构建块，因此它们的正确解析至关重要。 1. 赋值语句：...

    递归梯度下降分析C语言.docx

    递归下降语法分析是编译器设计中一种重要的语法分析技术，主要应用于处理上下文无关文法。...通过灵活调整和优化，递归下降解析器可以适应多种不同的上下文无关文法，为编译器和解释器提供强大的语法分析功能。

    赋值语句的递归下降翻译程序设计2 课程设计

    在编程语言的编译器或解释器中，这种方法被广泛用于语法分析阶段，通过构建一系列与文法规则相对应的子程序，对输入的源代码进行解析。在本课程设计中，我们将关注于赋值语句的翻译，特别是如何将其转换为逆波兰式...

    数据结构 算术表达式求值

    算术表达式求值是编译器设计和解释器实现的基础，它可以处理加法、减法、乘法和除法等运算。在这个问题中，我们特别关注的是如何使用栈来处理运算符和操作数。 **二、栈的应用** 栈是一种“后进先出”（LIFO）的...

    算术表达 式求值

    解析的方法有多种，包括递归下降解析、LR分析、LL分析等。 2. **求值策略**： - **前缀（ polish notation）**：也称为逆波兰表示法，操作符位于其操作数之前，如 "+ 2 3 * 4"。 - **后缀（postfix notation）**...

    表达式分析器

    表达式分析器广泛应用于各种领域，如编程语言解释器、脚本引擎、科学计算软件，甚至是游戏中的动态事件系统。一个自定义的表达式分析器可能更适合特定的需求，例如在某些性能敏感的应用中，或者在需要特殊语法支持...

Magicbox
Global site tag (gtag.js) - Google Analytics