Jak zrobić tabelę symboli

Question

Mamy za zadanie wykonać kompilator. Przeprowadziliśmy już analizę leksykalną i składnię, ale utknęliśmy w generowaniu kodu pośredniego. Zdaliśmy sobie sprawę, że musimy zaimplementować tabelę symboli, aby przejść do generowania kodu pośredniego i nie wiemy, jak to zrobić i co zawiera.

Biorąc pod uwagę poniższy kod, co powinna zawierać tablica symboli? (Kod jest napisany w języku edukacyjnym, który jest opisany poniżej)

Również w jaki sposób możemy wdrożyć zakresy w naszej tabeli symboli?

<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

Stół symbol odwzorowuje identyfikatory (zwykle poprzedzony nazwą Zakres) do informacji o tym, takie jak identyfikator tego typu symboli (zmienna lokalna/parametrów/funkcji/klasy itp) , typ danych, jego kolejność w stosunku do innych identyfikatorów w tym samym zakresie, jego kod źródłowy, itp. Tabelę symboli można wygenerować przechodząc przez abstrakcyjne drzewo składniowe, zawsze śledząc, jaki jest zasięg i dodając informacje do tabeli symboli za każdym razem, gdy trafisz w deklarację zmiennej. W przykładzie, część tablicy symboli może wyglądać następująco (odwzorowywania symbolu typu, rodzaju danych, położenia i linii kodu źródłowego):

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} 

Teraz można rozwiązać wszystkie nazwy zmiennych. Na przykład w wyrażeniu A := A + 1, jeśli wiesz, że twój bieżący zakres to MULTIPLY.Aop, tabela symnbol pozwoli ci dowiedzieć się, że ta A jest parametrem wejścia/wyjścia typu INT i że jest to pierwszy parametr (ta informacja będzie pozwala wygenerować przesunięcie adresu stosu, aby można było załadować/zapisać zmienną).