Algoritmi - Implementare una SDT con parser LR(1)

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

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 !

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

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

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.

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

Ok, grazie, provero' così.

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