Algoritmi - Grammatica LL per Parser

Ciao a tutti, da qualche giorno mi sono interessato a definire la grammatica di tipo LL per un Parser , il problema è che non riesco a capire se sto procedendo nel modo corretto oppure no,potreste propormi una grammatica corretta su cui posso iniziare a ragionare e capire il modo corretto di lavorare.

Il problema per cui vorrei realizzare la grammatica è il seguente:

Vorrei prendere un testo contenente lettere e numeri e in questo testo dovrei andare ad individuare la corretta apertura e chiusura di parentesi, nel caso fossero errate vorrei segnalare il problema.

Faccio un esempio nella speranza di essere più chiaro:

Input corretto: ciao9(prova)(123(r54))
Input errato: ciao)(

io vorrei Parsare un input della tipologia sopra descritta.

Vi ringrazio in anticipo per il vostro aiuto, spero di essere stato chiaro nella spiegazione.

Grazie

La grammatica per le parentesi bilanciate puo' essere:
P-> ( P ) P | epsilon


Dato che nel tuo esempio ci sono anche caratteri diversi dalle parentesi, per evitare di andare inutilmente a complicare la grammatica, ti consiglio di far scartare dall'analizzatore lessicale tali caratteri(visto che a te serve solo sapere se ci sono problemi di parentesi).

ti ringrazio per l'aiuto, con e intendi un carattere terminale o elemento vuoto?

Ma ammettendo di non scartare nulla dall'input come verrebbe la grammatica?

Perché vorrei capire il ragionamento da seguire in modo da poter affrontare anche diversi problemi.

Se non vuoi scartare niente:

P-> ( P ) P|text P|text|epsilon.

epsilon: elemento vuoto.
text: sarebbero caratteri diversi dalle parentesi.

Una cosa che evidentemente non mi è molto chiara è l'eliminazione delle ricorsioni a sinistra nella grammatica LL, nella grammatica che mi hai suggerito trovo P sia a destra che a sinistra della freccia ( -> ) non è una ricorsione a sinistra?

Non e' ricorsiva sinistra altrimenti, non era LL(1). Come vedi, nella prima produzione c'e':

P->( P ) P

che non e' ricorsiva sinistra, poiche' prima di P c'e' '('. Una grammatica e' ricorsiva sinistra, se la produzione di un non terminale, inizia con il non terminale stesso che ha il nome di quella produzione(direttamente, o indirettamente). Esempio:

E-> E a | epsilon

Questa e' ricorsiva sinistra, poiche' la produzione del non terminale E inizia a sua volta con E.

Prova a fare la tabella di parsing LL(1) della grammatica che ti avevo scritto, vedrai che non ci sarà nessun conflitto. Se invece provi a fare la tabella di parsing della grammatica: E-> E a | epsilon , trovi un conflitto, poiche' il parser LL(1) non e' in grado di parsarla.

Ho provato a fare la tabella delle regole come mi avevi suggerito, te la posto almeno mi dici se è corretta o no:


G -> P$
    P -> (P)P | aP | empty

    
     ==================================================
         'a' '(' ')' '$'
        -------------------------------------------------
        G| G->P$ | G->P$ | | |
        -------------------------------------------------
        P| P->aP | P->(P)P | P-> | P-> |
        -------------------------------------------------
    
     ===================================================

Considero G perché sto provando a fare un programma in java che funzioni da parser e come carattere finale prende '$',
intendo con 'a' quello che prima tu avevi nominato con Text e 'aP' quello che mi avevi indicato con 'TP', la tabella è corretta?

Ho rimosso però 'a' dalla grammatica è sbagliato? (quello che avevi chiamato Text)

Perché facendo girare il Parser mi sono accorto che tutto funziona, ma nel caso dessi un input contenente una parentesi tonda aperta (in qualsiasi posizione dell'input) senza la corrispettiva parentesi tonda chiusa, non mi da errore e in teoria dovrebbe darmelo...giusto?
Mentre se metto una tonda chiusa senza la corrispettiva aperta mi da errore come è giusto che sia.

Hai sbagliato la grammatica. La grammatica su cui devi fare la tabella di parsing e'(la 'a' non centra niente):

P-> ( P ) P|text P|epsilon.
(Ho fatto una modifica alla grammatica precedente per evitare ambiguità

Invece questa grammatica:

E-> E a | epsilon

l'ho usata per farti un esempio di ricorsione sinistra.

Ok??