Parsificatore

[sirmsym80]

Ciao a tutti!
Devo creare un analizzatore sintattico a discesa ricorsiva che parsifichi delle semplici espressioni aritmetiche come per esempio: 5+4*(6/2) o cose di questo tipo.
Deve quindi riconoscere le espressioni generate dalla grammatica:
<start> = <expr>
<expr> = <term> <exprp>
<exprp> = + <term> <exprp> | - <term> <exprp> | epsilon
<term> = <fact> <termp>
<termp> = * <fact> <termp> | / <fact> <termp> | epsilon
<fact> = ( <expr> ) | NUM
Per fare ciò il parsificatore utilizza il Lexer che ho fatto in precedenza il quale data una espressione tipo 5+4*(6/2) mi restituisce una serie di token del tipo:
<NUM, 5>
<PIU, +>
<NUM, 4>
<PER, *> ecc

Ho scritto solo parte del codice perchè poi non so come continuare:

public class Parsificatore {

	private Lexer l; 
	private Token lookhaead; 

	public Parserificatore(Lexer lx) {
		l = lx;
		read(); //legge il prossimo carattere in input
	}

	void read() {
		lookhaead = l.scan(); //read() richiama il metodo scan() della classe Lexer che legge il prossimo carattere
	}
	
	void match(Tag t) {
		if(lookhaead.tag == t)
			read();
		else
			error("Errore");
	}

	public void comincia() {
		expr();
		match(Tag.EOF);
	}

	private void expr() {
		System.out.println("<Expr>");
		term();
		exprp();
	}

	private void exprp() {
		System.out.println("<Exprp>");
		switch(lookhaead.tag) {
			case PLUS:
				match(Tag.PLUS);
				term();
				exprp();
				break;
			case MINUS:
				match(Tag.MINUS);
				term();
				exprp();
				break;
			default:
				/* *** */
		}
	}

	private void term() {
		System.out.println("<Term>");
		fact();
		termp();
	}

	private void termp() {
		System.out.println("<Termp>");
		switch(lookhaead.tag) {
			case TIMES:
				match(Tag.TIMES);
				fact();
				termp();
				break;
			case DIVIDE:
				match(Tag.DIVIDE);
				fact();
				termp();
				break;
			default:
				/* *** */
		}
	}

	private void fact() {
		System.out.println("<Factor>");
		switch(lookhaead.tag) {
			case NUM:
				match(Tag.NUM);
			default:
				expr();
		}
	}

	/**
		Main
	*/
	public static void main(String[] args) {
		Lexer l = new Lexer();
		Parserificatore p = new Parserificatore(l);
		p.comincia();
	}
}

Come posso scrivere il caso Epsilon?

Grazie

[Vincenzo1968]

http://forum.html.it/forum/showthrea...readid=1527260

[sirmsym80]

Grazie per la risposta ma non ho capito molto...

[Vincenzo1968]

Qui spiego l'algoritmo:

http://forum.html.it/forum/showthrea...=&pagenumber=4

Se qualcosa non ti è chiara su un aspetto particolare chiedi pure.

[sirmsym80]

Ad essere sinceri non ho capito bene qual'è lo scopo del parser, cosa deve restituirmi?
Il lexer restituisce i vari token ma il parser?

[Vincenzo1968]

Il compito principale del parser è quello di verificare che il codice sia sintatticamente valido. Per esempio, se abbiamo in input:

5 3

il parser, quando incontra il token "3", deve restituire il messaggio d'errore "Espressione non valida. Ci si aspettava un operatore(+,-,*,/); trovato invece operando".

Nel caso di input sintatticamente valido, il parser deve eseguire le azioni semantiche. Per esempio, nel caso dell'espressione

5 + 3

il parser lavora come segue:

- chiama la funzione GetNextToken() che restituisce il token "5". Il token viene piazzato sullo stack degli operandi.
- chiama la funzione GetNextToken() che restituisce il token "+"; il token viene piazzato sullo stack degli operatori.
- chiama la funzione GetNextToken() che restituisce il token "3". Il token viene piazzato sullo stack degli operandi.
- chiama la funzione GetNextToken() che restituisce il token di fine input, EOF;

L'azione finale consiste nel prelevare un operatore dallo stack degli operatori e due(o uno, se l'operatore è unario) operandi dallo stack degli operandi, eseguire l'operazione e piazzare il risultato in cima allo stack degli operatori.
Nel nostro esempio preleviamo l'operatore "+" dallo stack degli operandi e due operandi dallo stack degli operandi: il primo operando prelevato, "3" è l'operando destro. Il secondo operando prelevato, "5" è l'operando sinistro. Eseguimo l'operazione, 5 + 3 e piazziamo il risultato, 8, in cima allo stack degli operandi. Poiché lo stack degli operatori non contiene altri operandi, abbiamo terminato e lo stack degli operandi, contiene, in cima, il risultato dell'espressione, 8.

[sirmsym80]

Originariamente inviato da Vincenzo1968
Il compito principale del parser è quello di verificare che il codice sia sintatticamente valido. Per esempio, se abbiamo in input:

5 3

il parser, quando incontra il token "3", deve restituire il messaggio d'errore "Espressione non valida. Ci si aspettava un operatore(+,-,*,/); trovato invece operando".

Nel caso di input sintatticamente valido, il parser deve eseguire le azioni semantiche. Per esempio, nel caso dell'espressione

5 + 3

il parser lavora come segue:

- chiama la funzione GetNextToken() che restituisce il token "5". Il token viene piazzato sullo stack degli operandi.
- chiama la funzione GetNextToken() che restituisce il token "+"; il token viene piazzato sullo stack degli operatori.
- chiama la funzione GetNextToken() che restituisce il token "3". Il token viene piazzato sullo stack degli operandi.
- chiama la funzione GetNextToken() che restituisce il token di fine input, EOF;

L'azione finale consiste nel prelevare un operatore dallo stack degli operatori e due(o uno, se l'operatore è unario) operandi dallo stack degli operandi, eseguire l'operazione e piazzare il risultato in cima allo stack degli operatori.
Nel nostro esempio preleviamo l'operatore "+" dallo stack degli operandi e due operandi dallo stack degli operandi: il primo operando prelevato, "3" è l'operando destro. Il secondo operando prelevato, "5" è l'operando sinistro. Eseguimo l'operazione, 5 + 3 e piazziamo il risultato, 8, in cima allo stack degli operandi. Poiché lo stack degli operatori non contiene altri operandi, abbiamo terminato e lo stack degli operandi, contiene, in cima, il risultato dell'espressione, 8.

Sei stato chiarissimo, ti ringrazio!

[sirmsym80]

Non riesco a risolvere.. Non capisco come finire il codice, come interpretare l'epsilon...

[Vincenzo1968]

In sostanza bisogna calcolare il follow set. Epsilon si gestisce semplicemente matchando i token contenuti nel follow set e non facendo null'altro.

Nel caso della nostra grammatica:

<start> = <expr>
<expr> = <term> <exprp>
<exprp> = + <term> <exprp> | - <term> <exprp> | epsilon
<term> = <fact> <termp>
<termp> = * <fact> <termp> | / <fact> <termp> | epsilon
<fact> = ( <expr> ) | NUM

abbiamo:

Nullable Set:
exprp
termp

First Set:
FIRST(start) = { NUM ( }
FIRST(expr) = { NUM ( }
FIRST(exprp) = { - + epsilon }
FIRST(term) = { NUM ( }
FIRST(termp) = { / * epsilon }
FIRST(fact) = { NUM ( }

Follow Set:
FOLLOW(start) = { $ }
FOLLOW(expr) = { ) $ }
FOLLOW(exprp) = { ) $ }
FOLLOW(term) = { - + ) $ }
FOLLOW(termp) = { - + ) $ }
FOLLOW(fact) = { / * - + ) $ }

$ indica la fine della stringa di input(T_EOL).

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,
		T_EXP		
	}

	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) == '.' )				
				{
					strToken.append(str.charAt(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 if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == '^' )
			{
				m_PreviousTokenType = m_currToken.Type;
				m_currToken.Type = TokenTypeEnum.T_EXP;
				m_currToken.str = new String("^");
				++m_nNextPos;
				return TokenTypeEnum.T_EXP;
			}			
			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;
}

CParser.java:

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

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 = start();
		}

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

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

	//<start> = <expr>
	private boolean start()
	{
		return expr();
	}

	//<expr> = <term> <exprp>	
	private boolean expr()
	{
		if ( !term() )
			return false;
			
		if ( !exprp() )
			return false;
			
		return true;
	}
	
	//<exprp> = + <term> <exprp> | - <term> <exprp> | epsilon
	private boolean exprp()
	{
		double right, left;
			
		switch ( m_Lexer.m_currToken.Type )
		{
			case T_PLUS:	
				m_Lexer.GetNextToken();
				if ( !term() )
					return false;
				right = m_stack[m_top--];
				left  = m_stack[m_top--];
				m_stack[++m_top] = left + right;
				if ( !exprp() )
					return false;
				break;
			case T_MINUS:
				m_Lexer.GetNextToken();			
				if ( !term() )
					return false;
				right = m_stack[m_top--];
				left  = m_stack[m_top--];
				m_stack[++m_top] = left - right;
				if ( !exprp() )
					return false;			
				break;
			case T_CPAREN: // epsilon
				break;
			case T_EOL:    // epsilon						
				break;
			default:
				System.out.println("Errore di sintassi.");
				return false;			
		}
		
		return true;
	}	

	//<term> = <fact> <termp>
	private boolean term()
	{
		if ( !fact() )
			return false;
			
		if ( !termp() )
			return false;
			
		return true;
	}
	
	//<termp> = * <fact> <termp> | / <fact> <termp> | epsilon
	private boolean termp()
	{
		double right, left;
			
		switch ( m_Lexer.m_currToken.Type )
		{
			case T_MULT:	
				m_Lexer.GetNextToken();
				if ( !fact() )
					return false;
				right = m_stack[m_top--];
				left  = m_stack[m_top--];
				m_stack[++m_top] = left * right;
				if ( !termp() )
					return false;
				break;
			case T_DIV:
				m_Lexer.GetNextToken();			
				if ( !fact() )
					return false;
				right = m_stack[m_top--];
				if ( right == 0 )
				{
					System.out.println("Errore: divisione per zero.");
					return false;					
				}
				left  = m_stack[m_top--];
				m_stack[++m_top] = left / right;
				if ( !termp() )
					return false;			
				break;
			case T_PLUS:   // epsilon
				break;
			case T_MINUS:  // epsilon				
				break;			
			case T_CPAREN: // epsilon
				break;			
			case T_EOL:    // epsilon			
				break;
			default:
				System.out.println("Errore di sintassi.");
				return false;							
		}
		
		return true;		
	}
	
	//<fact> = ( <expr> ) | NUM 
	private boolean fact()
	{
		switch( m_Lexer.m_currToken.Type )
		{
		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;
		case T_NUMBER:
			m_stack[++m_top] = m_Lexer.m_currToken.Value;
			m_Lexer.GetNextToken();
			break;			
		default:
			System.out.println("Errore: atteso numero o parentesi aperta.");
			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;
}

[Vincenzo1968]

ExprJava.java:

import java.io.Console;

// javac CLexer.java CParser.java ExprJava.java
// java ExprJava

public class ExprJava
{
    public static void main(String[] args)
	{
		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.SetExpr(strExpr);
			lex.GetNextToken();
			
			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();
				if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_EOL )
					System.out.println("EOL");													
					
				System.out.println();													
					
					
				x++;
				if ( x >= 21 )
					break;
			}
			
			System.out.println();												
		}
		*/
    }
}