Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Grammatica LL per Parser
Forum - Algoritmi - Grammatica LL per Parser

Avatar
macco_cl (Normal User)
Rookie


Messaggi: 34
Iscritto: 27/02/2007

Segnala al moderatore
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:








PM Quote
Avatar
dmr (Normal User)
Pro


Messaggi: 141
Iscritto: 04/01/2012

Segnala al moderatore
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
PM Quote
Avatar
macco_cl (Normal User)
Rookie


Messaggi: 34
Iscritto: 27/02/2007

Segnala al moderatore
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.

PM Quote
Avatar
dmr (Normal User)
Pro


Messaggi: 141
Iscritto: 04/01/2012

Segnala al moderatore
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
PM Quote
Avatar
macco_cl (Normal User)
Rookie


Messaggi: 34
Iscritto: 27/02/2007

Segnala al moderatore
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
PM Quote
Avatar
dmr (Normal User)
Pro


Messaggi: 141
Iscritto: 04/01/2012

Segnala al moderatore
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
PM Quote
Avatar
macco_cl (Normal User)
Rookie


Messaggi: 34
Iscritto: 27/02/2007

Segnala al moderatore
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
PM Quote
Avatar
dmr (Normal User)
Pro


Messaggi: 141
Iscritto: 04/01/2012

Segnala al moderatore
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
PM Quote