如何製作符號表

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類型的輸入/輸出參數，它是第一個參數（該信息會讓你產生一個堆棧地址偏移量，以便你可以加載/存儲變量）。