如何使符号表 [英] How to make a symbol table

问题描述

我们有一个作为编译器的任务。我们已经进行了词法和语法分析，但是我们坚持生成中间代码。我们意识到，我们必须实现一个符号表，以便进行中间代码生成，我们不知道，如何做和它包含什么。

We have as an assignment to make a compiler. We have already made the lexical and syntax analysis but we are stuck at generation of intermediate code. We realized that we have to implement a symbol table in order to proceed to intermediate code generation and we don't know, how to do it and what it contains.

下面的代码，什么应该符号表包含？ （代码是用下面描述的教育语言编写的）

Given the code below, what should the symbol table contain? (The code is written in an educational language which is described below)

同样，我们如何在符号表中实现范围？

Also how can we implement scopes in our symbol table?

<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

推荐答案

A符号表将标识符（通常以范围名称前缀）映射到关于该标识符的信息，例如其符号类型（局部变量/参数/函数/类等），数据类型，其相对于同一范围内其他标识符的顺序，其源代码行等。可以通过遍历抽象语法树来生成符号表，通过始终跟踪您所在的范围，并在每次访问变量声明时向符号表添加信息。在您的示例中，符号表的一部分可能如下所示（映射到符号类型，数据类型，位置和源代码行）：

A symbol table maps identifiers (typically prefixed by a scope name) to information about that identifier, such as its symbol type (local variable / parameter / function / class etc.), data type, its order relative to the other identifiers in the same scope, its source code line, etc. The symbol table can be generated by traversing the abstract syntax tree, by always keeping track of which scope you're in and adding information to the symbol table whenever you hit a variable declaration. In your example, a part of the symbol table might look like this (mapping to symbol type, data type, position, and source code line):

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 的输入/输出参数，它是第一个参数（此信息将让您生成一个堆栈地址偏移，以便您可以加载/存储变量）。

Now, you can resolve all variable references. For instance, in the expression A := A + 1, if you know that your current scope is MULTIPLY.Aop, the symnbol table will let you find out that this A is an input/output parameter of type INT, and that it is the first parameter (this information will let you generate a stack address offset so that you can load/store the variable).

这篇关于如何使符号表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！