Algoritmi - Grammatica LL per Parser

Forum - Algoritmi - Grammatica LL per Parser

macco_cl (Normal User)
Rookie

Messaggi: 34
Iscritto: 27/02/2007

Postato alle 19:44
Giovedì, 02/04/2015

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 :hail:

dmr (Normal User)
Pro

Messaggi: 141
Iscritto: 04/01/2012

Postato alle 20:36
Giovedì, 02/04/2015

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).

Ultima modifica effettuata da dmr il 02/04/2015 alle 20:37

macco_cl (Normal User)
Rookie

Messaggi: 34
Iscritto: 27/02/2007

Postato alle 20:40
Giovedì, 02/04/2015

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.

dmr (Normal User)
Pro

Messaggi: 141
Iscritto: 04/01/2012

Postato alle 21:22
Giovedì, 02/04/2015

Se non vuoi scartare niente:

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

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

Ultima modifica effettuata da dmr il 02/04/2015 alle 21:29

macco_cl (Normal User)
Rookie

Messaggi: 34
Iscritto: 27/02/2007

Postato alle 22:03
Giovedì, 02/04/2015

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?

Ultima modifica effettuata da macco_cl il 02/04/2015 alle 22:04

dmr (Normal User)
Pro

Messaggi: 141
Iscritto: 04/01/2012

Postato alle 7:12
Venerdì, 03/04/2015

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.

Ultima modifica effettuata da dmr il 03/04/2015 alle 7:17

macco_cl (Normal User)
Rookie

Messaggi: 34
Iscritto: 27/02/2007

Postato alle 16:46
Venerdì, 03/04/2015

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.

Ultima modifica effettuata da macco_cl il 03/04/2015 alle 16:47

dmr (Normal User)
Pro

Messaggi: 141
Iscritto: 04/01/2012

Postato alle 18:46
Venerdì, 03/04/2015

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??

Ultima modifica effettuata da dmr il 03/04/2015 alle 19:37