c - 解析后的符号表总体；编译器构建

Question

创建解析树后，我现在必须填充符号表。

我必须存储诸如

之类的信息

标识符的类型、范围、偏移量等。

现在我如何知道标识符的类型和范围，因为我所知道的只是该特定 ID 的词位值和行号(在词法分析之后)。

我是如何了解整件事的？谢谢。

Answer 1

Now how do i know the type, scope of the identifiers , since all i know is the lexeme value and line number for that particular ID (after lexical analysis).

正如 EJP 提到的，您需要单步执行解析树。您的树应该已创建，以便您可以进行中序遍历，以与计算源代码语句和表达式相同的顺序访问每个节点。您的树节点还应该与特定的语言构造相对应，例如WhileStmtNode、MethodDeclNode 等

假设我正在构建符号表，递归地单步遍历树，并且我刚刚进入了方法体节点。我可能有类似以下内容:

public void doAction(MethodBodyNode methodBody) {
    currScope = 2;
    methodBody.getExpr().applyAction(this);
    currScope = 2;
}

我保留一个全局变量来管理范围。每次我进入范围发生变化的 block 时，我都会增加 currScope。同样，我将维护 currClass 和 currMethod 变量来存储符号名称、类型、偏移量等，以供后续阶段使用。

更新:

Now say, i am traversing the tree, everytime i come across an ID i would have to enter the value to symbol table along with the type, scope and others, say for scope i check if i come across '{' or function name, but how do i know what type of ID is this.

每个树节点应包含整个构造的所有必要信息。如果您使用解析器生成器(例如 CUP 或 Bison)，则可以指定如何在语法操作中构建树。例如

variableDeclaration::= identifier:i identifier:i2 SEMICOLON {: RESULT = new VarDeclNode(i, i2, null); :};
identifier::= ID:i {: RESULT = new IdNode(i.getLineNum(), i.getCharNum(), i.getStringValue()); :};

这些产生式将匹配 Foo f; 并将变量声明节点附加到树中。该节点封装了两个标识符节点，其中包含词位的行号、字符号和字符串值。第一个标识符节点是类型，第二个标识符节点是变量名称。 ID 是词法分析器在匹配标识符时返回的终止符号。我假设您在某种程度上熟悉这一点。

public class VarDeclNode extends StmtNode {

    private IdNode id;
    private IdNode type;
    private ExprNode expr;

    public VarDeclNode(IdNode id, IdNode type, ExprNode expr) {
        super();
        this.id = id;
        this.type = type;
        this.expr = expr;
    }

}

当您拥有包含这样的节点的语法树时，您就获得了所需的所有信息。

第二次更新:

无论您使用的是自定义解析器还是生成的解析器，都有一个不同的点，即在匹配产生式时将节点添加到树中。您使用什么语言并不重要。 C 结构体就可以了。

if it is a non terminal has the info as Nonterminals name, and if it is a terminal i.e. a token, then the info in token i.e. lexeme value, token name and line number are stored

树中必须有专门的节点，例如ClassNode、TypeNode、MethodDeclNode、IfStmtNode、ExprNode。你不能只存储一种类型的节点，然后将非终结符和终结符放入其中。非终结符表示为树节点，除了组成它的部分之外没有其他信息可存储，这些部分通常本身就是非终结符。您不会存储任何 token 信息。只有少数情况下您会实际存储词素的字符串值:用于标识符和字符串/ bool /整数文字。

看看this例子。在第一次归约期间，当 S 归约到 (S + F) 时，您将一个 ParenExprNode 附加到树根。您还可以附加一个 AddExprNode 作为 ParenExprNode 的子节点。当应用语法规则 2 的归约时，必须将该逻辑硬编码到解析器中。

树:

    ExprNode (root)
       |
  ParenExprNode
       |
   AddExprNode
   /         \
ExprNode   ExprNode

代码:

struct ExprNode { void* exprNode; };
struct ParenExprNode { void* exprNode; };
struct AddExprNode { void* op1, * op2; };
struct IdNode { char* val; int line; int charNum; };
struct IntLiteralNode { int val; int line; int charNum; };

void reduce_rule_2(ExprNode* expr) {

    //remove stack symbols

    //create nodes
    struct ParenExprNode* parenExpr = malloc(sizeof(struct ParenExprNode));
    struct AddExprNode* addExpr = malloc(sizeof(struct AddExprNode));
    addExpr->op1 = malloc(sizeof(struct ExprNode));
    addExpr->op2 = malloc(sizeof(struct ExprNode));

    //link them
    parenExpr->exprNode = (void*)addExpr;
    expr->exprNode = (void*)parenExpr;
}

在下一步中，将从输入中删除左括号。之后，S 位于堆栈顶部，并根据规则 1 将其减少为 F。由于 F 是标识符的非终结符，它由 IdNode 表示。

树:

    ExprNode
       |
  ParenExprNode
       |
   AddExprNode
   /         \
ExprNode   ExprNode
   |
 IdNode

代码:

reduce_rule_2(addExpr->op1);

void reduce_rule_1(ExprNode* expr) {
    //reduce stack symbols
    struct IdNode* id = malloc(sizeof(struct IdNode));
    id->val = parser_matched_text();
    id->lineNum = parser_line_num();
    id->charNum = parser_char_num();
    expr->exprNode = (void*)id;
}

等等...