シンボルテーブルの作成方法

Question

私たちはコンパイラを作成することができます。私たちはすでに字句解析を行っていますが、私たちは中間コードの生成に固執しています。私たちは、中間コード生成に進むためにシンボルテーブルを実装しなければならないことを認識しました。私たちはそれをどのように行うのか、どのように含んでいるのか分かりません。

以下のコードでは、シンボルテーブルには何が含まれていますか？ （コードは下記の教育言語で書かれています）

また、シンボルテーブルにスコープを実装するにはどうすればよいですか？

<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

シンボルテーブルは、（等のローカル変数/パラメータ/機能/クラス）は、そのシンボルタイプとして識別子（典型的には、スコープ名を前置）その識別子に関する情報には、マップ、データ型、同じスコープ内の他の識別子に関連するその順序、ソースコード行などが含まれます。シンボルテーブルは、抽象構文木をトラバースし、常にどのスコープを追跡して情報を追加することによって生成できます変数宣言を打つたびにシンボルテーブルに移動します。あなたの例では、シンボルテーブルの一部は、この（シンボルタイプ、データタイプ、位置、およびソースコード行へのマッピング）のようになります。

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} 

さて、あなたはすべての変数の参照を解決することができます。たとえば、式A := A + 1の場合、現在の有効範囲がMULTIPLY.Aopであることがわかっている場合、symnbolテーブルではAがタイプINTの入出力パラメータであり、これが最初のパラメータであることがわかります変数をロード/ストアできるようにスタックアドレスオフセットを生成させます）。