Come creare una tabella di simboli

Question

Abbiamo come compito di creare un compilatore. Abbiamo già effettuato l'analisi lessicale e della sintassi ma siamo bloccati nella generazione di codice intermedio. Ci siamo resi conto che dobbiamo implementare una tabella dei simboli per procedere alla generazione del codice intermedio e non sappiamo come farlo e cosa contiene.

Dato il seguente codice, cosa deve contenere la tabella dei simboli? (Il codice è scritto in un linguaggio educativo che è descritto di seguito)

Inoltre, come possiamo implementare gli ambiti nella nostra tabella dei simboli?

<PROGRAM> ::= PROGRAM ID <BLOCK> ENDPROGRAM 
<BLOCK> ::= {<DECLARATIONS> <SUBPROGRAMS> <SEQUENCE>} 
<DECLARATIONS> ::= ε | DECLARE <VARLIST> ENDDECLARE 
<VARLIST> ::= ε | ID (, ID)* 
<SUBPROGRAMS> ::= (<PROCORFUNC>) * 
<PROCORFUNC> ::= PROCEDURE ID <PROCORFUNCBODY> ENDPROCEDURE | 
FUNCTION ID <PROCORFUNCBODY> ENDFUNCTION 
<PROCORFUNCBODY> ::= <FORMALPARS> <BLOCK> 
<FORMALPARS> ::= ε | (<FORMALPARLIST>) 
<FORMALPARLIST> ::= <FORMALPARITEM> (, <FORMALPARITEM>)* 
<FORMALPARITEM> ::= IN ID | INOUT ID 
<SEQUENCE> ::= <STATEMENT> (; <STATEMENT>)* 
<STATEMENT> ::= ε | <ASSIGNMENT-STAT> | 
<IF-STAT> | 
<WHILE-STAT> | 
<FOR-STAT> | 
<EXIT-STAT> | 
<CALL-STAT> | 
<RETURN-STAT> 
<ASSIGNMENT-STAT> ::= ID := <EXPRESSION> 
<IF-STAT> ::= IF <CONDITION> THEN <SEQUENCE> <ELSEPART> ENDIF 
<ELSEPART> ::= ε | ELSE <SEQUENCE> 
<WHILE-STAT> ::= DO {<SEQUENCE>} WHILE (<CONDITION>) 
<FOR-STAT> ::= (<ASSIGNMENT-STAT>; <CONDITION>;<ASSIGNMENT-STAT>;) 
{<SEQUENCE>} 
<EXIT-STAT> ::= EXIT 
<CALL-STAT> ::= CALL ID <ACTUALPARS> 
<ACTUALPARS> ::= (<ACTUALPARLIST>) | ε 
<ACTUALPARLIST> ::= <ACTUALPARITEM> (, <ACTUALPARITEM>)* 
<ACTUALPARITEM> ::= IN <EXPRESSION> | INOUT ID 
<RETURN-STAT> ::= RETURN <EXPRESSION> 
<CONDITION> ::= <BOOLTERM> (OR <BOOLTERM>)* 
<BOOLTERM> ::= <BOOLFACTOR> (AND <BOOLFACTOR>)* 
<BOOLFACTOR> ::= NOT [<CONDITION>] | [<CONDITION>] | 
<EXPRESSION> <RELATIONAL-OPER> <EXPRESSION> | 
TRUE | FALSE 
<EXPRESSION> ::= <OPTIONAL-SIGN> <TERM> (<ADD-OPER> <TERM>)* 
<TERM> ::= <FACTOR> (<MUL-OPER> <FACTOR>)* 
<FACTOR> ::= CONSTANT | (<EXPRESSION>) | ID <IDTAIL> 
<IDTAIL> ::= ε | <ACTUALPARS> 
<RELATIONAL-OPER> ::= = | < (ε | = | >) | > (ε | =) 
<ADD-OPER> ::= + | - 
<MUL-OPER> ::= * |/
<OPTIONAL-SIGN> ::= ε | <ADD-OPER> 

PROGRAM MULTIPLY 
    { 
    DECLARE 
    A, B, C 
    ENDDECLARE 
    PROCEDURE Aop(INOUT A) 
    { 
     A=A+1; 
    } 
    ENDPROCEDURE 
    FUNCTION Bop(IN B){ 
     IF [NOT[[TRUE AND FALSE]OR[TRUE]]] THEN B := 100/2; 
     ELSE B := 100; 
     ENDIF; 
     RETURN B; 
     } 
    ENDFUNCTION 
    CALL Aop(INOUT A); 
    CALL Bop(IN B); 
    A := 40; 
    C := A * B; 
    } 
ENDPROGRAM 

Answer 1

Una tabella di simboli Mappe identificatori (tipicamente preceduti da un nome di ambito) alle informazioni su tale identificatore, ad esempio il tipo di simbolo (locale/parametro/funzione variabile/classe ecc) , tipo di dati, il suo ordine relativo agli altri identificatori nello stesso ambito, la sua linea di codice sorgente, ecc. La tabella dei simboli può essere generata percorrendo l'albero della sintassi astratta, tenendo sempre traccia di quale ambito ti trovi e aggiungendo informazioni alla tabella dei simboli ogni volta che si preme una dichiarazione di variabile. Nel tuo esempio, una parte della tabella dei simboli potrebbe assomigliare a questo (mappatura per tipo di simbolo, tipo di dati, la posizione, e la linea di codice sorgente):

MULTIPLY.A -> {"LOCAL", "INT", 0, 4} 
MULTIPLY.B -> {"LOCAL", "INT", 1, 4} 
MULTIPLY.C -> {"LOCAL", "INT", 2, 4} 
MULTIPLY.Aop -> {"FUNCTION", "INT", 3, 4} 
MULTIPLY.Aop.A -> {"INOUTPARAM", "INT", 0, 6} 

Ora, è possibile risolvere tutti i riferimenti variabili. Ad esempio, nell'espressione A := A + 1, se si conosce che l'ambito corrente è MULTIPLY.Aop, la tabella di simboli consentirà di scoprire che questo A è un parametro di input/output di tipo INT e che è il primo parametro (questa informazione verrà consente di generare uno spostamento dell'indirizzo di stack in modo da poter caricare/memorizzare la variabile).