[Java] Analizzatore lessicale e parser per espressioni aritmetiche

[fra_90]

Salve a tutti,
data la seguente grammatica in EBNF per espressioni aritmetiche intere con la classica precedenza degli operatori:

<espressione>::=<termine>{<addop><termine>}
<termine>::=<fattore>{<mulop><fattore>}
<fattore>::=<costante>|<variabile>|(<espressione>)
<costante>::=<interosenzasegno>
<variabile>::=<identificatore>
<interosenzasegno>::=<cifra>{<cifra>}
<identificatore>::=<lettera>{<lettera>|<cifra>}
<cifra>::=0|…|9
<lettera>::=a|…|z|A|…|Z
<addop>::=+|-
<mulop>::=*|/

dovrei utilizzare un analizzatore lessicale ed un parser a discesa ricorsiva per costruire, a partire da una stringa fornita in ingresso (da un file di testo), l’albero sintattico di un’espressione aritmetica.
Qualcuno ha qualche esempio o può darmi qualche dritta?
grazie a tutti

[Vincenzo1968]

http://www.di.unipi.it/~romani/DIDATTICA/EP/espr.pdf



edit: il parser segnalato nel link precedente non è a discesa ricorsiva. Vedi questo:

Parte I
Parte II
Parte III

[Vincenzo1968]

Ti posto il codice di un parser a discesa ricorsiva che ho scritto in C++. Non dovrebbe essere difficile convertirlo in Java.


file Lexer.h:

#ifndef LEXER_H
#define LEXER_H

typedef enum tagTokenType
{
	T_EOL,
	T_UNKNOWN,
	T_NUMBER,
	T_OPAREN,
	T_CPAREN,
	T_UMINUS,
	T_MULT,
	T_DIV,
	T_PLUS,
	T_MINUS
}TokenTypeEnum;

typedef struct tagToken
{
	TokenTypeEnum Type;
	char str[55];
	double Value;
}Token;

class CLexer
{
public:
	CLexer()
	{
		m_strExpr[0] = '\0';
		m_nNextPos = 0;
		m_PreviousTokenType = T_EOL;
	}

	void SetExpr(const char *strExpr)
	{
		strcpy(m_strExpr, strExpr);
	}

	TokenTypeEnum GetNextToken();

	Token m_currToken;

private:
	char m_strExpr[256];
	int m_nNextPos;
	TokenTypeEnum m_PreviousTokenType;
};

#endif // LEXER_H

file Lexer.cpp:

#include <iostream>
#include <cstdlib>

#include "Lexer.h"

TokenTypeEnum CLexer::GetNextToken()
{
	int i;
	char strToken[255];

	while ( 1 )
	{
		while ( m_strExpr[m_nNextPos++] == ' ' )
			;
		--m_nNextPos;

		if ( m_strExpr[m_nNextPos] == '\0' )
		{
			m_currToken.Type = T_EOL;
			strcpy(m_currToken.str, "\n");
			m_nNextPos = 0;
			m_PreviousTokenType = T_EOL;
			return T_EOL;
		}
		else if ( isdigit(m_strExpr[m_nNextPos]) )
		{
			i = 0;
			while ( isdigit(strToken[i++] = m_strExpr[m_nNextPos++]) )
				;
			if ( m_strExpr[m_nNextPos - 1] == '.' )
			{
				while ( isdigit(strToken[i++] = m_strExpr[m_nNextPos++]) )
					;
				strToken[i - 1] = '\0';
				--m_nNextPos;
				m_PreviousTokenType = m_currToken.Type;
				m_currToken.Type = T_NUMBER;
				strcpy(m_currToken.str, strToken);
				m_currToken.Value = atof(strToken);
				return T_NUMBER;
			}
			else
			{
				strToken[i - 1] = '\0';
				--m_nNextPos;
				m_PreviousTokenType = m_currToken.Type;
				m_currToken.Type = T_NUMBER;
				strcpy(m_currToken.str, strToken);
				m_currToken.Value = atof(strToken);
				return T_NUMBER;
			}
		}
		else if ( m_strExpr[m_nNextPos] == '.' )
		{
			i = 0;
			strToken[i++] = m_strExpr[m_nNextPos++];
			while ( isdigit(strToken[i++] = m_strExpr[m_nNextPos++]) )
				;
			strToken[i - 1] = '\0';
			--m_nNextPos;
			m_PreviousTokenType = m_currToken.Type;
			m_currToken.Type = T_NUMBER;
			strcpy(m_currToken.str, strToken);
			m_currToken.Value = atof(strToken);
			return T_NUMBER;
		}
		else if ( m_strExpr[m_nNextPos] == '(' )
		{
			m_PreviousTokenType = m_currToken.Type;
			m_currToken.Type = T_OPAREN;
			strcpy(m_currToken.str, "(");
			++m_nNextPos;
			return T_OPAREN;
		}
		else if ( m_strExpr[m_nNextPos] == ')' )
		{
			m_PreviousTokenType = m_currToken.Type;
			m_currToken.Type = T_CPAREN;
			strcpy(m_currToken.str, ")");
			++m_nNextPos;
			return T_CPAREN;
		}
		else if ( m_strExpr[m_nNextPos] == '+' )
		{
			m_PreviousTokenType = m_currToken.Type;
			strcpy(m_currToken.str, "+");
			++m_nNextPos;
			m_currToken.Type = T_PLUS;
			return T_PLUS;
		}
		else if ( m_strExpr[m_nNextPos] == '-' )
		{
			strcpy(m_currToken.str, "-");
			++m_nNextPos;
			m_PreviousTokenType = m_currToken.Type;
			if ( m_PreviousTokenType == T_CPAREN || m_PreviousTokenType == T_NUMBER )
			{
				m_currToken.Type = T_MINUS;
				return T_MINUS;
			}
			else
			{
				m_currToken.Type = T_UMINUS;
				return T_UMINUS;
			}
		}
		else if ( m_strExpr[m_nNextPos] == '*' )
		{
			m_PreviousTokenType = m_currToken.Type;
			m_currToken.Type = T_MULT;
			strcpy(m_currToken.str, "*");
			++m_nNextPos;
			return T_MULT;
		}
		else if ( m_strExpr[m_nNextPos] == '/' )
		{
			m_PreviousTokenType = m_currToken.Type;
			m_currToken.Type = T_DIV;
			strcpy(m_currToken.str, "/");
			++m_nNextPos;
			return T_DIV;
		}
		else
		{
			m_PreviousTokenType = m_currToken.Type;
			m_currToken.Type = T_UNKNOWN;
			m_currToken.str[0] = m_strExpr[m_nNextPos];
			m_currToken.str[1] = '\0';
			++m_nNextPos;
			return T_UNKNOWN;
		}
	}

	return T_EOL;
}

file Parser.h:

#ifndef PARSER_H
#define PARSER_H

#define MAXSTACK 255

#include "Lexer.h"

class CParser
{
public:
	CParser()
	{
		m_strExpr[0] = '\0';
		m_top = -1;
		m_value = 0;
	}

	bool Parse(const char *strExpr);
	double GetValue()
	{
		return m_value;
	}

private:
	bool expr();
	bool expr1();
	bool expr2();
	bool expr3();

	bool match(TokenTypeEnum ExpectedToken)
	{
		if ( m_Lexer.m_currToken.Type == ExpectedToken )
		{
			m_Lexer.GetNextToken();
			return true;
		}

		return false;
	}

	CLexer m_Lexer;
	char m_strExpr[256];
	int m_top;              
	double m_stack[MAXSTACK];
	double m_value;
};


#endif // PARSER_H

file Parser.cpp:

#include <iostream>
#include <cstdlib>
using namespace std;

#include "Parser.h"

/*
expr  : expr1 {('+' | '-') expr1};
expr1 : expr2 {('*' | '/') expr2};
expr2 : ['-'] expr3;
expr3 : T_NUMBER
		| '(' expr ')'
*/

bool CParser::Parse(const char *strExpr)
{
	bool ret = true;

	strcpy(m_strExpr, strExpr);

	m_Lexer.SetExpr(strExpr);
	m_top = -1;
	m_value = 0;

	m_Lexer.GetNextToken();

	while ( ret && m_Lexer.m_currToken.Type != T_EOL )
	{
		ret = expr();
	}

	if ( m_top >= 0 )
		m_value = m_stack[m_top--];
	m_top = -1;

	return ret;
}


//expr  : expr1 {('+' | '-') expr1};
bool CParser::expr()
{
	double right, left;
	int currToken;

	if ( !expr1() )
		return false;

	while ( m_Lexer.m_currToken.Type == T_PLUS || m_Lexer.m_currToken.Type == T_MINUS )
	{
		currToken = m_Lexer.m_currToken.Type;
		m_Lexer.GetNextToken();

		if ( !expr1() )
			return false;

		right = m_stack[m_top--];
		left  = m_stack[m_top--];

		if ( currToken == T_PLUS )
			m_stack[++m_top] = left + right;
		else if ( currToken == T_MINUS )
			m_stack[++m_top] = left - right;

	}

	return true;
}

//expr1 : expr2 {('*' | '/') expr2};
bool CParser::expr1()
{
	double right, left;
	int currToken;

	if ( !expr2() )
		return false;

	while ( m_Lexer.m_currToken.Type == T_MULT || m_Lexer.m_currToken.Type == T_DIV )
	{
		currToken = m_Lexer.m_currToken.Type;
		m_Lexer.GetNextToken();

		if ( !expr2() )
			return false;

		right = m_stack[m_top--];
		left  = m_stack[m_top--];

		if ( currToken == T_MULT )
			m_stack[++m_top] = left * right;
		else if ( currToken == T_DIV )
		{
			if ( right == 0 )
			{
				cout << "Errore: divisione per zero." << endl;
				return false;
			}
			m_stack[++m_top] = left / right;
		}
	}

	return true;
}

//expr2 : ['-'] expr3;
bool CParser::expr2()
{
	int currToken;
	double dblValue;

	if ( m_Lexer.m_currToken.Type == T_UMINUS )
	{
		currToken = m_Lexer.m_currToken.Type;
		m_Lexer.GetNextToken();
	}

	if ( !expr3() )
		return false;

	if ( currToken == T_UMINUS )
	{
		dblValue = m_stack[m_top--];
		dblValue *= -1;
		m_stack[++m_top] = dblValue;
	}

	return true;
}

//expr3 : T_NUMBER
//		| '(' expr ')'
bool CParser::expr3()
{
	switch( m_Lexer.m_currToken.Type )
	{
	case T_NUMBER:
		m_stack[++m_top] = m_Lexer.m_currToken.Value;
		m_Lexer.GetNextToken();
		break;
	case T_OPAREN:
		m_Lexer.GetNextToken();
		if ( !expr() )
			return false;
		if ( !match(T_CPAREN) )
		{
			cout << "Errore: parentesi non bilanciate." << endl;
			return false;
		}
		break;
	default:
		cout << "Errore: atteso numero, meno unario o parentesi aperta." << endl;
		cout << "Trovato invece " << m_Lexer.m_currToken.str << endl;
		return false;
	}

	return true;
}

file ParseExpr.cpp:

#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

#include "Parser.h"
#include "Lexer.h"

int main()
{
	char strExpr[255];
	string str;
	CParser parser;

	while( true )
	{
		cout << "Inserisci un'espressione aritmetica: ";
		getline(cin, str);

		if ( strlen(str.c_str()) == 0 )
			break;

		strcpy(strExpr, str.c_str());

		if ( parser.Parse(strExpr) )
			cout << endl << "Il risultato e': " << parser.GetValue() << endl << endl;
	}

	return 0;
}

/*
int main()
{
	char strExpr[255];
	string str;
	CLexer lex;
	Token tok;

	while( true )
	{
		cout << "Inserisci un'espressione aritmetica: ";
		getline(cin, str);

		if ( strlen(str.c_str()) == 0 )
			break;

		strcpy(strExpr, str.c_str());

		cout << "Lista Token:" << endl;

		lex.GetNextToken(strExpr, &tok);
		while ( tok.Type != T_EOL )
		{
			if ( tok.Type == T_PLUS )
				cout << "PLUS" << endl;
			if ( tok.Type == T_MINUS )
				cout << "MINUS" << endl;
			if ( tok.Type == T_MULT )
				cout << "MULT" << endl;
			if ( tok.Type == T_DIV )
				cout << "DIV" << endl;
			if ( tok.Type == T_UMINUS )
				cout << "UMINUS" << endl;
			if ( tok.Type == T_CPAREN )
				cout << "CPAREN" << endl;
			if ( tok.Type == T_OPAREN )
				cout << "OPAREN" << endl;
			if ( tok.Type == T_NUMBER )
				cout << "NUMBER" << endl;
			if ( tok.Type == T_UNKNOWN )
				cout << "UNKNOWN" << endl;

			cout << "Token: <" << tok.str << ">" << endl;
			lex.GetNextToken(strExpr, &tok);
			if ( tok.Type == T_EOL )
				cout << "EOL" << endl;
		}
	} 
	
	return 0;
}
*/

[fra_90]

grazie mille per la risposta
il codice in C++ non mi è molto chiaro ad essere sincero.
In pratica ho creato una classe per ogni produzione della grammatica di cui sopra (poichè c'è da utilizzare il pattern INTERPRETER).
In pratica l'analizzatore lessicale suddivide la stringa letta dal file di testo e passa ciascun token al parser, il quale dovrebbe costruire l'albero o sbaglio?

[Vincenzo1968]

Esatto. Si può costruire l'albero e successivamente attraversarlo per valutare l'espressione come abbiamo fatto nel Contest 6.
Ma si può anche valutare direttamente l'espressione senza costruire l'albero come faccio nel codice di cui sopra. Lo sto convertendo in Java. Ma devi darmi un po' di tempo; me lo sto studiando(Java dico) qui:

http://docs.oracle.com/javase/tutori...ybigindex.html

[Vincenzo1968]

edit.

[Vincenzo1968]

Ecco il Parser(e il lexer) a discesa ricorsiva in Java:


file CLexer.java:

import java.lang.String;
import java.lang.StringBuilder;

public class CLexer
{
	static public enum TokenTypeEnum
	{
		T_EOL,
		T_UNKNOWN,
		T_NUMBER,
		T_OPAREN,
		T_CPAREN,
		T_UMINUS,
		T_MULT,
		T_DIV,
		T_PLUS,
		T_MINUS
	}

	static public class Token
	{
		TokenTypeEnum Type;
		String str;
		double Value;
	}
	public CLexer()
	{
		m_nNextPos = 0;
		m_PreviousTokenType = TokenTypeEnum.T_EOL;
		m_currToken = new Token();
	}

	public void SetExpr(String str)
	{
		m_strExpr = new String(str);
	}

	public TokenTypeEnum GetNextToken()
	{	
		StringBuilder strToken = new StringBuilder();
		
		StringBuilder str = new StringBuilder();		
		str.append(m_strExpr);	
				
		if ( m_nNextPos >= str.length() )						
		{
			m_currToken = new Token();			
			m_currToken.Type = TokenTypeEnum.T_EOL;
			m_currToken.str = new String("EOL");
			m_nNextPos = 0;
			m_PreviousTokenType = TokenTypeEnum.T_EOL;
			return TokenTypeEnum.T_EOL;
		}		
			
		while ( true )
		{
			while ( m_nNextPos < str.length() && str.charAt(m_nNextPos++) == ' ' )
				;
			--m_nNextPos;

			if ( m_nNextPos >= str.length() )						
			{
				m_currToken = new Token();						
				m_currToken.Type = TokenTypeEnum.T_EOL;
				m_currToken.str = new String("EOL");
				m_nNextPos = 0;
				m_PreviousTokenType = TokenTypeEnum.T_EOL;
				return TokenTypeEnum.T_EOL;
			}
			else if ( isdigit(str.charAt(m_nNextPos)) )					
			{			
				while ( m_nNextPos < str.length() && isdigit(str.charAt(m_nNextPos)) )
				{
					strToken.append(str.charAt(m_nNextPos));					
					m_nNextPos++;
				}
				if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == '.' )				
				{
					str.setCharAt(m_nNextPos, '.');
					m_nNextPos++;					
					while ( m_nNextPos < str.length() && isdigit(str.charAt(m_nNextPos)) )
					{
						strToken.append(str.charAt(m_nNextPos));
						m_nNextPos++;						
					}
					m_PreviousTokenType = m_currToken.Type;
					m_currToken.Type = TokenTypeEnum.T_NUMBER;
					m_currToken.str = new String(strToken.toString());
					m_currToken.Value = Double.valueOf(m_currToken.str).doubleValue();
					return TokenTypeEnum.T_NUMBER;
				}
				else
				{
					m_PreviousTokenType = m_currToken.Type;
					m_currToken.Type = TokenTypeEnum.T_NUMBER;
					m_currToken.str = new String(strToken.toString());				
					m_currToken.Value = Double.valueOf(m_currToken.str).doubleValue();				
					return TokenTypeEnum.T_NUMBER;
				}
			}
			else if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == '.' )
			{			
				str.setCharAt(m_nNextPos, '.');
				m_nNextPos++;				
				while ( m_nNextPos < str.length() && isdigit(str.charAt(m_nNextPos)) )
				{
					strToken.append(str.charAt(m_nNextPos));
					m_nNextPos++;					
				}					
				m_PreviousTokenType = m_currToken.Type;
				m_currToken.Type = TokenTypeEnum.T_NUMBER;
				m_currToken.str = new String(strToken);			
				m_currToken.Value = Double.valueOf(m_currToken.str).doubleValue();				
				return TokenTypeEnum.T_NUMBER;
			}
			else if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == '(' )
			{			
				m_PreviousTokenType = m_currToken.Type;
				m_currToken.Type = TokenTypeEnum.T_OPAREN;
				m_currToken.str = new String("(");							
				++m_nNextPos;
				return TokenTypeEnum.T_OPAREN;
			}
			else if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == ')' )
			{
				m_PreviousTokenType = m_currToken.Type;
				m_currToken.Type = TokenTypeEnum.T_CPAREN;
				m_currToken.str = new String(")");							
				++m_nNextPos;
				return TokenTypeEnum.T_CPAREN;
			}
			else if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == '+' )
			{
				m_PreviousTokenType = m_currToken.Type;
				m_currToken.str = new String("+");							
				++m_nNextPos;
				m_currToken.Type = TokenTypeEnum.T_PLUS;
				return TokenTypeEnum.T_PLUS;
			}
			else if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == '-' )
			{
				m_currToken.str = new String("-");
				++m_nNextPos;
				m_PreviousTokenType = m_currToken.Type;
				if ( m_PreviousTokenType == TokenTypeEnum.T_CPAREN || 
					m_PreviousTokenType == TokenTypeEnum.T_NUMBER )
				{
					m_currToken.Type = TokenTypeEnum.T_MINUS;
					return TokenTypeEnum.T_MINUS;
				}
				else
				{
					m_currToken.Type = TokenTypeEnum.T_UMINUS;
					return TokenTypeEnum.T_UMINUS;
				}
			}
			else if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == '*' )
			{
				m_PreviousTokenType = m_currToken.Type;
				m_currToken.Type = TokenTypeEnum.T_MULT;
				m_currToken.str = new String("*");
				++m_nNextPos;
				return TokenTypeEnum.T_MULT;
			}
			else if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == '/' )
			{
				m_PreviousTokenType = m_currToken.Type;
				m_currToken.Type = TokenTypeEnum.T_DIV;
				m_currToken.str = new String("/");
				++m_nNextPos;
				return TokenTypeEnum.T_DIV;
			}
			else
			{
				m_PreviousTokenType = m_currToken.Type;
				m_currToken.Type = TokenTypeEnum.T_UNKNOWN;
				m_currToken.str = new String(str);								
				++m_nNextPos;
				return TokenTypeEnum.T_UNKNOWN;
			}
		}
	}
	
	private boolean isdigit(char c)
	{
		return (c >= '0' && c <= '9');
	}

	public Token m_currToken;
	private String m_strExpr;
	private int m_nNextPos;
	private TokenTypeEnum m_PreviousTokenType;
}

file CParser.java:

import java.lang.String;
import java.lang.StringBuilder;

/*
expr  : expr1 {('+' | '-') expr1};
expr1 : expr2 {('*' | '/') expr2};
expr2 : ['-'] expr3;
expr3 : T_NUMBER | '(' expr ')'
*/

public class CParser
{
	public CParser()
	{
		m_Lexer = new CLexer();	
		m_top = -1;
		m_value = 0;
		m_stack = new double[255];
	}

	public boolean Parse(String strExpr)
	{
		boolean ret = true;

		m_strExpr = new String(strExpr);
		m_top = -1;
		m_value = 0;		

		m_Lexer.SetExpr(strExpr);

		m_Lexer.GetNextToken();

		while ( ret && m_Lexer.m_currToken.Type != CLexer.TokenTypeEnum.T_EOL )
		{
			ret = expr();
		}

		if ( m_top >= 0 )
			m_value = m_stack[m_top--];
		m_top = -1;

		return ret;	
	}
	
	public double GetValue()
	{
		return m_value;
	}

	//expr  : expr1 {('+' | '-') expr1};
	private boolean expr()
	{
		double right, left;
		CLexer.TokenTypeEnum currToken;

		if ( !expr1() )
			return false;

		while ( m_Lexer.m_currToken.Type == CLexer.TokenTypeEnum.T_PLUS ||
				m_Lexer.m_currToken.Type == CLexer.TokenTypeEnum.T_MINUS )
		{
			currToken = m_Lexer.m_currToken.Type;
			m_Lexer.GetNextToken();

			if ( !expr1() )
				return false;

			right = m_stack[m_top--];
			left  = m_stack[m_top--];

			if ( currToken == CLexer.TokenTypeEnum.T_PLUS )
				m_stack[++m_top] = left + right;
			else if ( currToken == CLexer.TokenTypeEnum.T_MINUS )
				m_stack[++m_top] = left - right;

		}

		return true;		
	}
	
	//expr1 : expr2 {('*' | '/') expr2};
	private boolean expr1()
	{
		double right, left;
		CLexer.TokenTypeEnum currToken;

		if ( !expr2() )
			return false;

		while ( m_Lexer.m_currToken.Type == CLexer.TokenTypeEnum.T_MULT ||
				m_Lexer.m_currToken.Type == CLexer.TokenTypeEnum.T_DIV )
		{
			currToken = m_Lexer.m_currToken.Type;
			m_Lexer.GetNextToken();

			if ( !expr2() )
				return false;

			right = m_stack[m_top--];
			left  = m_stack[m_top--];

			if ( currToken == CLexer.TokenTypeEnum.T_MULT )
				m_stack[++m_top] = left * right;
			else if ( currToken == CLexer.TokenTypeEnum.T_DIV )
			{
				if ( right == 0 )
				{
					System.out.println("Errore: divisione per zero.");
					return false;
				}
				m_stack[++m_top] = left / right;
			}
		}

		return true;	
	}
	
	//expr2 : ['-'] expr3;
	private boolean expr2()
	{
		CLexer.TokenTypeEnum currToken;
		double dblValue;
		currToken = CLexer.TokenTypeEnum.T_EOL;

		if ( m_Lexer.m_currToken.Type == CLexer.TokenTypeEnum.T_UMINUS )
		{
			currToken = m_Lexer.m_currToken.Type;
			m_Lexer.GetNextToken();
		}

		if ( !expr3() )
			return false;

		if ( currToken == CLexer.TokenTypeEnum.T_UMINUS )
		{
			dblValue = m_stack[m_top--];
			dblValue *= -1;
			m_stack[++m_top] = dblValue;
		}

		return true;	
	}
	
	//expr3 : T_NUMBER
	//		| '(' expr ')'
	private boolean expr3()
	{	
		switch( m_Lexer.m_currToken.Type )
		{
		case T_NUMBER:
			m_stack[++m_top] = m_Lexer.m_currToken.Value;
			m_Lexer.GetNextToken();
			break;
		case T_OPAREN:
			m_Lexer.GetNextToken();
			if ( !expr() )
				return false;
			if ( !match(CLexer.TokenTypeEnum.T_CPAREN) )
			{
				System.out.println("Errore: parentesi non bilanciate.");				
				return false;
			}
			break;
		default:
			System.out.println("Errore: atteso numero, meno unario o parentesi aperta.");							
			System.out.print("Trovato invece ");										
			System.out.println(m_Lexer.m_currToken.str);
			return false;
		}

		return true;	
	}

	private boolean match(CLexer.TokenTypeEnum ExpectedToken)
	{
		if ( m_Lexer.m_currToken.Type == ExpectedToken )
		{
			m_Lexer.GetNextToken();
			return true;
		}

		return false;
	}
	
	private CLexer m_Lexer;
	private String m_strExpr;	
	private int m_top;              
	private double[] m_stack;
	private double m_value;
}

file ExprJava.java:

import java.io.Console;
//import java.util.Arrays;
//import java.io.IOException;

// C:\Programmi\Java\jdk1.6.0_14\bin\javac CLexer.java CParser.java ExprJava.java
// C:\Programmi\Java\jdk1.6.0_14\bin\java ExprJava

public class ExprJava
{
    public static void main(String[] args) /* throws IOException */
	{
		String str;
		CParser parser = new CParser();

		Console c = System.console();
		
		System.out.println();																
		
		while( true )
		{		
			String strExpr = c.readLine("Inserisci un'espressione aritmetica: ");		
			
			System.out.println();															
			
			
			if ( strExpr.length() == 0 )
				break;

			System.out.println();															

			if ( parser.Parse(strExpr) )
			{
				System.out.print("Il risultato e': ");
				System.out.println(parser.GetValue());				
				System.out.println();					
			}
		}
	
		/*
		CLexer lex = new CLexer();
		
		Console c = System.console();
					
		while( true )
		{
			System.out.println();									
		
			String strExpr = c.readLine("Inserisci un'espressione aritmetica: ");		
			
			if ( strExpr.length() == 0 )
				break;

			System.out.println();													
			System.out.println("Lista Token:");
					
			lex.GetNextToken(strExpr);
			
			int x = 0;
				
			while ( lex.m_currToken.Type != CLexer.TokenTypeEnum.T_EOL)
			{
				System.out.println();													
							
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_PLUS )
					System.out.println("PLUS");					
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_MINUS )
					System.out.println("MINUS");										
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_MULT )
					System.out.println("MULT");									
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_DIV )
					System.out.println("DIV");									
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_UMINUS )
					System.out.println("UMINUS");									
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_CPAREN )
					System.out.println("CPAREN");									
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_OPAREN )
					System.out.println("OPAREN");									
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_NUMBER )
					System.out.println("NUMBER");									
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_UNKNOWN )
					System.out.println("UNKNOWN");									

				System.out.print("Token: <");
				System.out.print(lex.m_currToken.str);
				System.out.print(">");
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_NUMBER )
				{
					System.out.print(" Value: ");
					System.out.print(lex.m_currToken.Value);					
				}
				System.out.println();				
				
				lex.GetNextToken(strExpr);
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_EOL )
					System.out.println("EOL");													
					
				System.out.println();													
					
					
				x++;
				if ( x >= 21 )
					break;
			}
			
			System.out.println();												
		}
		*/		
    }
}

[Vincenzo1968]

Versione C#:

file Lexer.cs:

using System;
//using System.Collections.Generic;
//using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;

namespace ExprCS
{
    public enum TokenType
    {
        T_EOL,
        T_UNKNOWN,
        T_NUMBER,
        T_OPAREN,
        T_CPAREN,
        T_UMINUS,
        T_MULT,
        T_DIV,
        T_PLUS,
        T_MINUS
    }

    public struct Token
    {
        public TokenType Type;
        public string str;
        public double Value;
    }

    public class CLexer
    {
        public CLexer()
        {
            m_strExpr = "";
            m_nNextPos = 0;
            m_PreviousTokenType = TokenType.T_EOL;
            m_currToken = new Token();
        }

        public void SetExpr(string strExpr)
        {
            m_strExpr = strExpr;
        }

        private bool isdigit(char c)
        {
            return (c >= '0' && c <= '9');
        }

        public TokenType GetNextToken()
        {
            StringBuilder strToken = new StringBuilder("", 256);

            if (m_nNextPos >= m_strExpr.Length)
            {
                m_currToken.Type = TokenType.T_EOL;
                m_currToken.str = "EOL";
                m_nNextPos = 0;
                m_PreviousTokenType = TokenType.T_EOL;
                return TokenType.T_EOL;
            }

            char[] strExpr = new char[1024];
            strExpr = m_strExpr.ToCharArray();

            while (true)
            {
                while (m_nNextPos < m_strExpr.Length && strExpr[m_nNextPos++] == ' ')
                    ;
                --m_nNextPos;

                if (m_nNextPos >= m_strExpr.Length)
                {
                    m_currToken.Type = TokenType.T_EOL;
                    m_currToken.str = "EOL";
                    m_nNextPos = 0;
                    m_PreviousTokenType = TokenType.T_EOL;
                    return TokenType.T_EOL;
                }
                else if (isdigit(strExpr[m_nNextPos]))
                {
                    while (m_nNextPos < m_strExpr.Length && isdigit(strExpr[m_nNextPos]))
                    {
                        strToken.Append(strExpr[m_nNextPos]);
                        m_nNextPos++;
                    }

                    if (m_nNextPos < m_strExpr.Length && (strExpr[m_nNextPos] == '.' || strExpr[m_nNextPos] == ','))
                    {
                        strToken.Append(',');
                        m_nNextPos++;
                        while (m_nNextPos < m_strExpr.Length && isdigit(strExpr[m_nNextPos]))
                        {
                            strToken.Append(strExpr[m_nNextPos]);
                            m_nNextPos++;
                        }
                        m_PreviousTokenType = m_currToken.Type;
                        m_currToken.Type = TokenType.T_NUMBER;
                        m_currToken.str = strToken.ToString();
                        m_currToken.Value = Convert.ToDouble(strToken.ToString());
                        return TokenType.T_NUMBER;
                    }
                    else
                    {
                        m_PreviousTokenType = m_currToken.Type;
                        m_currToken.Type = TokenType.T_NUMBER;
                        m_currToken.str = strToken.ToString();
                        m_currToken.Value = Convert.ToDouble(strToken.ToString());
                        return TokenType.T_NUMBER;
                    }
                }
                else if (m_nNextPos < m_strExpr.Length && (strExpr[m_nNextPos] == '.' || strExpr[m_nNextPos] == ','))
                {
                    strToken.Append(',');
                    m_nNextPos++;
                    while (m_nNextPos < m_strExpr.Length && isdigit(strExpr[m_nNextPos]))
                    {
                        strToken.Append(strExpr[m_nNextPos]);
                        m_nNextPos++;
                    }
                    m_PreviousTokenType = m_currToken.Type;
                    m_currToken.Type = TokenType.T_NUMBER;
                    m_currToken.str = strToken.ToString();
                    m_currToken.Value = Convert.ToDouble(strToken.ToString());
                    return TokenType.T_NUMBER;
                }
                else if (m_nNextPos < m_strExpr.Length && strExpr[m_nNextPos] == '(')
                {
                    m_PreviousTokenType = m_currToken.Type;
                    m_currToken.Type = TokenType.T_OPAREN;
                    m_currToken.str = "(";
                    ++m_nNextPos;
                    return TokenType.T_OPAREN;
                }
                else if (m_nNextPos < m_strExpr.Length && strExpr[m_nNextPos] == ')')
                {
                    m_PreviousTokenType = m_currToken.Type;
                    m_currToken.Type = TokenType.T_CPAREN;
                    m_currToken.str = ")";
                    ++m_nNextPos;
                    return TokenType.T_CPAREN;
                }
                else if (m_nNextPos < m_strExpr.Length && strExpr[m_nNextPos] == '+')
                {
                    m_PreviousTokenType = m_currToken.Type;
                    m_currToken.str = "+";
                    ++m_nNextPos;
                    m_currToken.Type = TokenType.T_PLUS;
                    return TokenType.T_PLUS;
                }
                else if (m_nNextPos < m_strExpr.Length && strExpr[m_nNextPos] == '-')
                {
                    m_currToken.str = "-";
                    ++m_nNextPos;
                    m_PreviousTokenType = m_currToken.Type;
                    if (m_PreviousTokenType == TokenType.T_CPAREN || m_PreviousTokenType == TokenType.T_NUMBER)
                    {
                        m_currToken.Type = TokenType.T_MINUS;
                        return TokenType.T_MINUS;
                    }
                    else
                    {
                        m_currToken.Type = TokenType.T_UMINUS;
                        return TokenType.T_UMINUS;
                    }
                }
                else if (m_nNextPos < m_strExpr.Length && strExpr[m_nNextPos] == '*')
                {
                    m_PreviousTokenType = m_currToken.Type;
                    m_currToken.Type = TokenType.T_MULT;
                    m_currToken.str = "*";
                    ++m_nNextPos;
                    return TokenType.T_MULT;
                }
                else if (m_nNextPos < m_strExpr.Length && strExpr[m_nNextPos] == '/')
                {
                    m_PreviousTokenType = m_currToken.Type;
                    m_currToken.Type = TokenType.T_DIV;
                    m_currToken.str = "/";
                    ++m_nNextPos;
                    return TokenType.T_DIV;
                }
                else
                {
                    m_PreviousTokenType = m_currToken.Type;
                    m_currToken.Type = TokenType.T_UNKNOWN;
                    m_currToken.str = strExpr[m_nNextPos].ToString();
                    ++m_nNextPos;
                    return TokenType.T_UNKNOWN;
                }
            }
        }

        public Token m_currToken;
        private string m_strExpr;
        private int m_nNextPos;
        private TokenType m_PreviousTokenType;
    }
}

file Parser.cs:

using System;
//using System.Collections.Generic;
//using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;

using ExprCS;

namespace ExprCS
{
    public class CParser
    {
        public CParser()
        {
            m_top = -1;
            m_value = 0;
            m_stack = new double[255];
            m_Lexer = new CLexer();
        }

        public bool Parse(string strExpr)
        {
            bool ret = true;

            m_strExpr = strExpr;
            m_top = -1;
            m_value = 0;

            m_Lexer.SetExpr(strExpr);

            m_Lexer.GetNextToken();

            while (ret && m_Lexer.m_currToken.Type != TokenType.T_EOL)
            {
                ret = expr();
            }

            if (m_top >= 0)
                m_value = m_stack[m_top--];
            m_top = -1;

            return ret;
        }

        public double GetValue()
        {
            return m_value;
        }

        private bool expr()
        {
            double right, left;
            TokenType currToken;

            if (!expr1())
                return false;

            while (m_Lexer.m_currToken.Type == TokenType.T_PLUS || m_Lexer.m_currToken.Type == TokenType.T_MINUS)
            {
                currToken = m_Lexer.m_currToken.Type;
                m_Lexer.GetNextToken();

                if (!expr1())
                    return false;

                right = m_stack[m_top--];
                left = m_stack[m_top--];

                if (currToken == TokenType.T_PLUS)
                    m_stack[++m_top] = left + right;
                else if (currToken == TokenType.T_MINUS)
                    m_stack[++m_top] = left - right;

            }

            return true;
        }

        private bool expr1()
        {
            double right, left;
            TokenType currToken;

            if (!expr2())
                return false;

            while (m_Lexer.m_currToken.Type == TokenType.T_MULT || m_Lexer.m_currToken.Type == TokenType.T_DIV)
            {
                currToken = m_Lexer.m_currToken.Type;
                m_Lexer.GetNextToken();

                if (!expr2())
                    return false;

                right = m_stack[m_top--];
                left = m_stack[m_top--];

                if (currToken == TokenType.T_MULT)
                    m_stack[++m_top] = left * right;
                else if (currToken == TokenType.T_DIV)
                {
                    if (right == 0)
                    {
                        Console.WriteLine("Errore: divisione per zero.");
                        return false;
                    }
                    m_stack[++m_top] = left / right;
                }
            }

            return true;
        }
        private bool expr2()
        {
            TokenType currToken;
            double dblValue;

            currToken = TokenType.T_EOL;

            if (m_Lexer.m_currToken.Type == TokenType.T_UMINUS)
            {
                currToken = m_Lexer.m_currToken.Type;
                m_Lexer.GetNextToken();
            }

            if (!expr3())
                return false;

            if (currToken == TokenType.T_UMINUS)
            {
                dblValue = m_stack[m_top--];
                dblValue *= -1;
                m_stack[++m_top] = dblValue;
            }

            return true;
        }
        private bool expr3()
        {
            switch (m_Lexer.m_currToken.Type)
            {
                case TokenType.T_NUMBER:
                    m_stack[++m_top] = m_Lexer.m_currToken.Value;
                    m_Lexer.GetNextToken();
                    break;
                case TokenType.T_OPAREN:
                    m_Lexer.GetNextToken();
                    if (!expr())
                        return false;
                    if (!match(TokenType.T_CPAREN))
                    {
                        Console.WriteLine("Errore: parentesi non bilanciate.");
                        return false;
                    }
                    break;
                default:
                    Console.WriteLine("Errore: atteso numero, meno unario o parentesi aperta.");
                    Console.WriteLine("Trovato invece {0}", m_Lexer.m_currToken.str);
                    return false;
            }

            return true;
        }

        private bool match(TokenType ExpectedToken)
        {
            if (m_Lexer.m_currToken.Type == ExpectedToken)
            {
                m_Lexer.GetNextToken();
                return true;
            }

            return false;
        }

        private CLexer m_Lexer;
        private string m_strExpr;
        private int m_top;
        private double[] m_stack;
        private double m_value;
    }
}

file program.cs:

using System;
//using System.Collections.Generic;
//using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;

using ExprCS;

namespace ExprCS
{
    class Program
    {
        static void Main(string[] args)
        {
	        string strExpr;
            CParser parser = new CParser();

            while (true)
            {
                Console.Write("Inserisci un'espressione aritmetica: ");
                strExpr = Console.ReadLine();

                if (strExpr.Length == 0)
                    break;

                if (parser.Parse(strExpr))
                    Console.WriteLine("Il risultato e': {0}", parser.GetValue());

                Console.WriteLine();
            }


            /*
	        string strExpr;
	        CLexer lex;
	        Token tok;

            lex = new CLexer();
	        while( true )
	        {
                Console.Write("Inserisci un'espressione aritmetica: ");
                strExpr = Console.ReadLine();

                if (strExpr.Length == 0)
                    break;

                lex.SetExpr(strExpr);

                Console.WriteLine();

                Console.WriteLine("Lista Token:");

		        lex.GetNextToken();
                tok = lex.m_currToken;
                while ( tok.Type != TokenType.T_EOL )
	    {
                    if (tok.Type == TokenType.T_PLUS)
                        Console.WriteLine("PLUS");
                    if (tok.Type == TokenType.T_MINUS)
                        Console.WriteLine("MINUS");
                    if (tok.Type == TokenType.T_MULT)
                        Console.WriteLine("MULT");
                    if (tok.Type == TokenType.T_DIV)
                        Console.WriteLine("DIV");
                    if (tok.Type == TokenType.T_UMINUS)
                        Console.WriteLine("UMINUS");
                    if (tok.Type == TokenType.T_CPAREN)
                        Console.WriteLine("CPAREN");
                    if (tok.Type == TokenType.T_OPAREN)
				        Console.WriteLine("OPAREN");
                    if (tok.Type == TokenType.T_NUMBER)
                        Console.WriteLine("NUMBER");
                    if (tok.Type == TokenType.T_UNKNOWN)
				        Console.WriteLine("UNKNOWN");

                    if ( tok.Type == TokenType.T_NUMBER )
                        Console.WriteLine("Token: <{0}> Value: {1}", tok.str, tok.Value);
                    else
                        Console.WriteLine("Token: <{0}>", tok.str);
			        lex.GetNextToken();
                    tok = lex.m_currToken;
                    if (tok.Type == TokenType.T_EOL)
                        Console.WriteLine("EOL");

		        }
	        }
            */
        }
    }
}