[JAVA] programma riconoscimento stringhe

[s1m092]

Ciao a tutti volevo un aiuto su un programma che sto realizzando per il progetto di programmazione. Le basi della programmazione ad oggetti credo di possederle. Qualcuno sa darmi una mano?
Questo è il testo:


Realizzare il tipo Pila con elementi di tipo Object e le operazioni push, pop
ed empty. Utilizzando il tipo Pila, realizzare un automa a pila non deterministico
che accetti grammatiche nella Forma Normale di Greibach. La specifica
della grammatica è memorizzato in un file il cui formato in BNF é il seguente:
<Grammatica> ::= {<Produzione>n}*
<Produzione> ::= <NonTerminale>b->b<Terminale>b{<NonTerminale>b}*
<NonTerminale> ::= <Carattere><Carattere>
<Carattere> ::= A | ... | Z
<Terminale> ::= <Stringa>
Le stringhe di terminali (token) devono essere tutte distinte. La stringa (token)
ha lunghezza minima pari a 1 e non contiene spazi. I caratteri ’n’ e ’b’ sono
rispettivamente il carattere di nuova riga e lo spazio. Le stringhe di terminali
(token) non possono essere tra di loro sottrostringhe. E’ desiderabile che venga
effettuato un’analisi sintattica del file contenente la grammatica per verificarne
la congruitá. Il generatore di parser di nome GNF ha come parametri sulla riga
di comando un file con la specifica della grammatica e un file con il testo da
analizzare e produce come risultato l’accettazione o il rifiuto. Nel caso del rifiuto
produce il numero di riga dove si è verificato l’errore di riconoscimento. Ogni
modulo di programma deve avere il commento documentale /** author */ con
gli autori del progetto.

Avevo pensato di realizzare 4 classi: il main, la pila, un'altra pila per il controllo dell'errore e infine uno per la gestione dell'input di stringhe.
Datemi una mano anche se non so proprio come iniziare...

Grazie in anticipo per la considerazione. Un saluto.

[s1m092]

Ho sbagliato sezione?

[valia]

Originariamente inviato da s1m092
Ho sbagliato sezione?

no, hai sbagliato domanda.

Non è compito del forum risolvere gli esercizi al tuo posto.
Hai detto che pensavi di realizzare 4 classi, motiva la tua scelta, presenta un approccio risolutivo e ti si può consigliare.
Ad occhio e croce a mio parere la tua scelta è errata (non stai ragionando ad oggetti)

[s1m092]

Non mi sembra di aver chiesto di risolvermi l'esercizio.

La pila è la seguente:

import java.util.Vector;
public class Pila

{ 
   private Vector p;
   private int top;
   
   Pila(){p= new Vector(); top = 0;} 
   
   public void push(Double e) {p.add(top++,e);}
   
   public Double pop () throws Errore{
      if (p.isEmpty()) throw new Errore("Pila vuota");
           else {              
               return (Double) p.elementAt(--top);
           }
   }
    
   public boolean empty () {
      if (p.isEmpty()) return true;
      else return false;
   }
}

Solo che non capisco come gestire le grammatiche che do in input. Ad esempio leggevo di un metodo streamtokenizer mi sembra ma non mi è chiaro l'utilizzo.

[MItaly]

Il codice va specificato tra tag [CODE] ... [/CODE], altrimenti perde l'indentazione. Ora correggo io, in futuro ricordatene.

[Vincenzo1968]

Originariamente inviato da s1m092
Ciao a tutti volevo un aiuto su un programma che sto realizzando per il progetto di programmazione. Le basi della programmazione ad oggetti credo di possederle. Qualcuno sa darmi una mano?
Questo è il testo:


Realizzare il tipo Pila con elementi di tipo Object e le operazioni push, pop
ed empty. Utilizzando il tipo Pila, realizzare un automa a pila non deterministico
che accetti grammatiche nella Forma Normale di Greibach. La specifica
della grammatica è memorizzato in un file il cui formato in BNF é il seguente:
<Grammatica> ::= {<Produzione>n}*
<Produzione> ::= <NonTerminale>b->b<Terminale>b{<NonTerminale>b}*
<NonTerminale> ::= <Carattere><Carattere>
<Carattere> ::= A | ... | Z
<Terminale> ::= <Stringa>
Le stringhe di terminali (token) devono essere tutte distinte. La stringa (token)
ha lunghezza minima pari a 1 e non contiene spazi. I caratteri ’n’ e ’b’ sono
rispettivamente il carattere di nuova riga e lo spazio. Le stringhe di terminali
(token) non possono essere tra di loro sottrostringhe. E’ desiderabile che venga
effettuato un’analisi sintattica del file contenente la grammatica per verificarne
la congruitá. Il generatore di parser di nome GNF ha come parametri sulla riga
di comando un file con la specifica della grammatica e un file con il testo da
analizzare e produce come risultato l’accettazione o il rifiuto. Nel caso del rifiuto
produce il numero di riga dove si è verificato l’errore di riconoscimento. Ogni
modulo di programma deve avere il commento documentale /** author */ con
gli autori del progetto.

Avevo pensato di realizzare 4 classi: il main, la pila, un'altra pila per il controllo dell'errore e infine uno per la gestione dell'input di stringhe.
Datemi una mano anche se non so proprio come iniziare...

Grazie in anticipo per la considerazione. Un saluto.

L'esercizio non è affatto banale. Si tratta di costruire al volo un parser LL(1) table-driven. E, dunque, bisogna costruire, sempre al volo, la tabella LL(1).

In buona sostanza la grammatica specifica che i simboli non terminali debbano essere costituiti da una coppia di caratteri alfabetici maiuscoli. Per esempio: AB FX CS AW UY SK sono esempi di non terminali validi.
I simboli terminali sono costituiti da stringhe di caratteri: a ab Ab aB ABC kdjhsha sono esempi di terminali validi.
La grammatica è costituita da zero o una o più regole di produzione.
Ogni regola di produzione è nella forma:

non-terminale seguito da spazio seguito dall'operatore freccia -> seguito da spazio seguito da terminale seguito da zero o uno o più non-terminali (tutti separati da uno [i]spazio[i]).

Per creare la tabella LL(1) dobbiamo precalcolare gli insiemi: nullable, first e follow.

Una volta creata la tabella LL(1) possiamo utilizzare il seguente algoritmo per il parsing:

(in pseudocode):

Parser()
{
   /* Push the start symbol S onto the stack */
   Push(S, stack);
   /* Initialize lookahead symbol */
   currentToken = GetNextToken();
   while ( not Empty(stack) )
   {
      top = Top(stack);
      if (top is a nonterminal )
      {
         action = LL1_Table[top, currentToken];
         if ( action > 0 )
         {
            /* Pop top symbol */
            Pop(stack);
            /* Push RHS of production */
            for each symbol on RHS do
            {
               /* start with last symbol, from right to left: */
               Push(symbol, stack); 
            }
         }
         else
            print("syntax error");
      }
      else if ( currentToken == top )
      {
         /* Match terminal symbol in input */
         Pop(stack);
         /* Get next terminal symbol in input */
         currentToken = GetNextToken();  	       
      }
      else
         print("syntax error");
   }
}

Per questa parte dell'esercizio:

E’ desiderabile che venga
effettuato un’analisi sintattica del file contenente la grammatica per verificarne
la congruitá.

ti consiglierei di utilizzare un parser a discesa ricorsiva che ha il vantaggio di essere facilmente implementabile a mano.

[s1m092]

Grazie mille per l'aiuto. La classe che hai creato è di tipo pila e serve per la gestione dell'errore ovvero il parser che riconosce le stringhe/grammatiche giusto?? Ora però devo gestire l'input secondo te come devo comportarmi? Cioè devo in sostanza creare una classe che mi permette di dare in pasto al parser un file giusto? Se si come lo scriveresti? E poi scusa ma sono molto inesperto la tabella LL(1) cos'è?

P.S. scusa le molte domande ma sono molto inesperto...

[Vincenzo1968]

La tabella LL(1) viene utilizzata dal parser per scegliere l'azione da intraprendere(la produzione della grammatica da applicare) in base al token corrente nella stringa di input(il cosiddetto token di lookahead).
In sostanza si tratta di un array bidimensionale che contiene i simboli non terminali nelle righe e i simboli terminali nelle colonne. Gli elementi dell'array sono le regole grammaticali da applicare.
Il cuore dell'algoritmo suesposto è nella seguente riga:

   action = LL1_Table[top, currentToken];

Se in cima allo stack(top) abbiamo un non terminale, applichiamo la regola grammaticale corrispondente al token di lookahead(currentToken). Se in corrispondenza a top, currentToken non c'è nessuna regola grammaticale, riportiamo un errore di sintassi.

La prima cosa da fare è, dunque, scrivere un analizzatore lessicale(lexer o tokenizer) che legga la stringa in input e la suddivida in token. Per esempio così:

CLexer.java:

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

public class CLexer
{
	static public enum TokenTypeEnum
	{
		T_TERMINAL(0),
		T_NONTERMINAL(1),
		T_SPACE(2),
		T_NEWLINE(3),	
		T_ARROW(4),	
		T_EOL(5),	
		T_UNKNOWN(6);
		
		private final int value;
		
		private TokenTypeEnum(int value)
		{
			this.value = value;
		}

		public int getValue()
		{
			return value;
		}
	}

	static public class Token
	{
		TokenTypeEnum Type;
		String str;
		int row;
	}
	
	public CLexer()
	{
		m_nNextPos = 0;
		m_currToken = new Token();
		m_currToken.row = 1;
	}

	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;
			return TokenTypeEnum.T_EOL;
		}		
			
		while ( true )
		{
			if ( m_nNextPos >= str.length() )						
			{
				m_currToken = new Token();						
				m_currToken.Type = TokenTypeEnum.T_EOL;
				m_currToken.str = new String("EOL");
				m_nNextPos = 0;
				return TokenTypeEnum.T_EOL;
			}
			else if ( isAlpha(str.charAt(m_nNextPos)) )					
			{
				while ( m_nNextPos < str.length() && isAlpha(str.charAt(m_nNextPos)) )
				{
					strToken.append(str.charAt(m_nNextPos));					
					m_nNextPos++;
				}
				if ( strToken.length() == 2 )
				{
					if ( isUpper(strToken.charAt(0)) && isUpper(strToken.charAt(1)) )
						m_currToken.Type = TokenTypeEnum.T_NONTERMINAL;
					else
						m_currToken.Type = TokenTypeEnum.T_TERMINAL;
				}
				else
				{
					m_currToken.Type = TokenTypeEnum.T_TERMINAL;					
				}
				m_currToken.str = new String(strToken.toString());
				return m_currToken.Type;
			}
			else if ( m_nNextPos < str.length() && 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_currToken.Type = TokenTypeEnum.T_ARROW;
					m_currToken.str = new String(strToken);			
					++m_nNextPos;
					return m_currToken.Type;
				}
			}
			else if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == ' ' )
			{			
				m_currToken.Type = TokenTypeEnum.T_SPACE;
				m_currToken.str = new String("b");
				++m_nNextPos;
				return m_currToken.Type;
			}
			else if ( m_nNextPos < str.length() && str.charAt(m_nNextPos) == '\n' )
			{
				m_currToken.Type = TokenTypeEnum.T_NEWLINE;
				m_currToken.str = new String("n");
				++m_nNextPos;
				m_currToken.row++;
				return m_currToken.Type;
			}
			else
			{
				m_currToken.Type = TokenTypeEnum.T_UNKNOWN;
				m_currToken.str = new String(str);								
				++m_nNextPos;
				return m_currToken.Type;
			}
		}
	}
	
	private boolean isAlpha(char c)
	{
		return ( (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') );
	}

	private boolean isUpper(char c)
	{
		return ( c >= 'A' && c <= 'Z' );
	}

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

ProvaLexer.java:

import java.io.*;
import java.io.Console;

// javac ProvaLexer.java CLexer.java
// java ProvaLexer

public class ProvaLexer
{
	public static String readFile(String strFileName)
	{
		StringBuffer buffer = new StringBuffer();
		
		File name = new File(strFileName);
		
		if ( name.isFile() )
		{
			try
			{
				BufferedReader input = new BufferedReader(new FileReader(name));
				String text;
				while ( (text = input.readLine()) != null )
					buffer.append(text + "\n");
				input.close();
			}
			catch (IOException ioException)
			{
				return null;
			}
		}
		
		return buffer.toString();		
	}	
	
    public static void main(String[] args)
	{
		if ( args.length < 2 )
		{
			System.out.println("Uso: java ProvaLexer file1 file2");
			return;			
		}
		
		String strFileName1 = args[0];
		String strFileName2 = args[1];		
		
		CParser parser = new CParser();
		
		System.out.println();																
		
		String strFile1 = readFile(strFileName1);
		if ( strFile1 == null )
		{
			System.out.print("Errore nella lettura del file ");
			System.out.println(strFileName1);
			return;
		}
		
		String strFile2 = readFile(strFileName2);
		if ( strFile2 == null )
		{
			System.out.print("Errore nella lettura del file ");
			System.out.println(strFileName1);
			return;			
		}	
		
					
		CLexer lex = new CLexer();
							
		System.out.println();									
		
		System.out.println();													
		System.out.println("Lista Token:");
		
		lex.setExpr(strFile1);		
					
		lex.getNextToken();
						
		while ( lex.m_currToken.Type != CLexer.TokenTypeEnum.T_EOL)
		{						
			if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_TERMINAL )
				System.out.println("TERMINAL");					
			if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_NONTERMINAL )
				System.out.println("NON-TERMINAL");										
			if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_SPACE )
				System.out.println("SPACE");									
			if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_NEWLINE )
				System.out.println("NEWLINE");									
			if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_ARROW )
				System.out.println("ARROW");									
			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("'");
			System.out.println();				
				
			lex.getNextToken();
			if ( lex.m_currToken.Type == CLexer.TokenTypeEnum.T_EOL )
				System.out.println("EOL");																		
			System.out.println();								
		}
    }
}

[Alex'87]

Penso che scrivere un parser LL1 vada oltre lo scopo dell'esercizio. Da quel che ho capito è per un progetto di programmazione, non di linguaggi e compilatori.

s1m092, ci dai un po' di contesto?
Qual è il programma del tuo corso di programmazione?

[s1m092]

Originariamente inviato da Alex'87
Penso che scrivere un parser LL1 vada oltre lo scopo dell'esercizio. Da quel che ho capito è per un progetto di programmazione, non di linguaggi e compilatori.

s1m092, ci dai un po' di contesto?
Qual è il programma del tuo corso di programmazione?

Vorrei anzitutto ringraziarvi per l'aiuto e la considerazione. Nel corso abbiamo affrontato le basi della programmazione ad oggetti, con l'INTRODUZIONE a Java. Purtroppo però il progetto è questo e nessuno degli studenti, che ha seguito il corso, ha le conoscenze necessarie per affrontare un progetto simile...ora il problema però resta e il progetto deve essere fatto. Io personalmente credo che realizzare una pila con la gestione di errori non sia difficile, ma in tutta sincerità non so nemmeno da dove iniziare per un parser con tanto di tabella. Come ha detto Vincenzo (se posso darti del tu) non è affatto banale; è un corso universitario (laurea triennale) il programma è il seguente:

vi do il link del professore e accedete al file chiamato "Linguaggio di programmazione Java"

http://www.cs.unicam.it/culmone/?Cor...Programmazione