Algoritmi - Implementare una SDT con parser LR(1)

Forum - Algoritmi - Implementare una SDT con parser LR(1)

dmr (Normal User)
Pro

Messaggi: 141
Iscritto: 04/01/2012

Postato alle 9:24
Domenica, 22/12/2013

Ciao a tutti, dovrei implementare una SDT(syntax directed translation) per una grammatica, utilizzando il parser LR(1).Durante il normale svolgimento del parsing, e' proprio il parser LR(1) a svolgere le azioni di pop dello stack infatti l'algoritmo del parser LR(1) e':

Codice sorgente - presumibilmente VB.NET

let a be the first symbol of w$; 
while(1) 
{ 
  let s be the state on top of the stack; 
  if ( ACTION[s, a] = shift t ) 
  { 
    push t onto the stack; 
    let a be the next input symbol; 
  } 
  else if ( ACTION [s, a] = reduce A  ) 
  { 
    pop n symbols off the stack; 
    let state t now be on top of the stack; 
    push GOTO[t, A] onto the stack; 
  } 
  else if ( ACTION[s,a] = accept ) break; 
  else call error-recovery routine; 
}

Infatti, nel caso di una riduzione si occupa proprio lui a levare i simboli dallo stack. La mia domanda ora e' questa: nel caso in cui bisogna implementare una SDT, durante una riduzione, i simboli dello stack devono essere gestiti(push/pop) dalle azioni semantiche della grammatica in esame ??

Grazie in anticipo, spero di essere stato chiaro !

Ultima modifica effettuata da dmr il 22/12/2013 alle 9:28

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

Postato alle 21:22
Lunedì, 23/12/2013

Mm, sara' che non ho mai toccato quest'argomento in dettaglio, ma non riesco a capire la domanda.

Il mio blog: https://piero.dev

dmr (Normal User)
Pro

Messaggi: 141
Iscritto: 04/01/2012

Postato alle 10:13
Martedì, 24/12/2013

Di sicuro mi sono spiegato male io. In pratica vorrei implementare con un parser LR(1) questa SDD:

Codice sorgente - presumibilmente Algoritmi

G-> B
B-> B A
B-> A
A-> print F { print(F.val) }
F-> F1,id { F.val= F1.val + id.lexVal() } -> semplice concatenazione di caratteri: Se F1.val= 'a' e id.lexVal()='b' allora F.val="ab"
F-> id { F.val= id }

La grammatica accetta input del tipo:

print a$ , infatti: print a -> print F -> A -> B -> G

oppure:

print a,b print a$

Ora pero' per implementarla con il parser LR(1), la gestione dello stack non deve essere fatta dalla SDD ??
Chiedo questo perche', nel caso in cui il parser si trovi a fare una riduzione, levando n simboli dallo stack,
potrebbe eliminare informazioni che dovrebbero servire all'azione semantica di tale riduzione.

In pratica, se il parser deve fare per esempio la riduzione: A-> print F , dovrebbe eliminare 2 simboli dallo stack,
ma eliminando i 2 simboli dallo stack perdera' il dato di F.val, cosi' durante l'esecuzione dell'azione semantica
della riduzione ci saranno problemi.

Ultima modifica effettuata da dmr il 24/12/2013 alle 10:13

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

Postato alle 16:33
Martedì, 24/12/2013

Penso che in questo caso il parser e le azioni semantiche utilizzino due stack diversi (non condividono lo stack di runtime, ma usano due strutture stack separate).

Il mio blog: https://piero.dev

dmr (Normal User)
Pro

Messaggi: 141
Iscritto: 04/01/2012

Postato alle 9:03
Mercoledì, 25/12/2013

Ok, grazie, provero' così.

dmr (Normal User)
Pro

Messaggi: 141
Iscritto: 04/01/2012

Postato alle 22:03
Giovedì, 26/12/2013

Sono ancora io, alla fine sono riuscito ad implementare la SDT ,usando lo stack del parser. La SDT completa e':

G-> A

A-> A P {
          Stack.removeElem(1);
          Stack.state=GOTO(Stack.size()-2.state,r1);
        }

A-> P {
        Stack.state=GOTO(Stack.size()-2.state,r2);
      }

P-> print F {
              print(Stack.code);
              print("call print");
              Stack.removeElem(1);
              Stack.state=GOTO(Stack.size()-2.state,r3);
            }

F-> F,id {
           Stack.size()-3.code+="push "+id.lexVal();
           Stack.removeElem(2);
           Stack.state=GOTO(Stack.size()-2.state,r4);
         }

F-> id {
         Stack.code="push "+id.lexVal();
         Stack.state=GOTO(Stack.size()-2.state,r5);
       }

In pratica invece di far levare, durante una riduzione gli elementi dallo stack, ho scritto la SDT in modo che si occupi lei dello stack.
Grazie ancora !!

Ultima modifica effettuata da dmr il 26/12/2013 alle 22:06