第95集：语法分析实战（二）—— 变量声明

在编程语言中，变量声明是一种基本的语法结构，用于向编译器介绍新的变量及其类型。本集我们将通过实现变量声明语句的语法分析，学习如何处理更复杂的语法结构，包括类型声明、多个变量声明、初始化表达式等。

一、需求分析

我们需要设计一个能够处理以下变量声明语句的语法分析器：

1. 基本类型：支持 int、float、bool、string 等基本类型
2. 单个变量声明：如 int x;
3. 多个变量声明：如 int x, y, z;
4. 变量初始化：如 int x = 5; 或 int x = 1 + 2;
5. 组合形式：如 int x = 5, y, z = 10;

二、文法设计

1. 扩展词法单元

首先，我们需要扩展之前的词法单元，添加类型关键字和等号：

TOKEN_INT      // int
TOKEN_FLOAT    // float
TOKEN_BOOL     // bool
TOKEN_STRING   // string
TOKEN_ASSIGN   // =
TOKEN_SEMICOLON // ;
TOKEN_COMMA    // ,

2. 文法规则设计

根据需求，我们可以设计如下的文法规则：

declaration → type declarator_list ;
type → int | float | bool | string
declarator_list → declarator ( , declarator )*
declarator → IDENTIFIER ( = expression )?
expression → term ( + term | - term )*
term → factor ( * factor | / factor )*
factor → NUMBER | IDENTIFIER | ( expression )

这个文法规则涵盖了：

• 不同类型的声明
• 单个或多个变量的声明
• 可选的初始化表达式
• 与之前实现的算术表达式的集成

三、词法分析器扩展

我们需要扩展词法分析器，以支持新的词法单元：

// 扩展 Token 类型定义
typedef enum {
    // 之前的 Token 类型...
    TOKEN_INT,      // int
    TOKEN_FLOAT,    // float
    TOKEN_BOOL,     // bool
    TOKEN_STRING,   // string
    TOKEN_ASSIGN,   // =
    TOKEN_SEMICOLON, // ;
    TOKEN_COMMA,    // ,
    TOKEN_IDENTIFIER, // 标识符
    // 其他 Token 类型...
} TokenType;

// 扩展词法分析器
Token lexer_next(Lexer *lexer) {
    // 跳过空白字符
    while (isspace(lexer->input[lexer->pos])) {
        lexer->pos++;
    }
    
    char c = lexer->input[lexer->pos];
    
    // 处理运算符和标点符号
    switch (c) {
        // 之前的处理...
        case '=':
            lexer->pos++;
            return (Token){TOKEN_ASSIGN, 0};
        case ';':
            lexer->pos++;
            return (Token){TOKEN_SEMICOLON, 0};
        case ',':
            lexer->pos++;
            return (Token){TOKEN_COMMA, 0};
        // 其他处理...
    }
    
    // 处理标识符和关键字
    if (isalpha(c) || c == '_') {
        char buffer[100];
        int i = 0;
        while (isalnum(c) || c == '_') {
            buffer[i++] = c;
            c = lexer->input[++lexer->pos];
        }
        buffer[i] = '\0';
        
        // 检查是否为关键字
        if (strcmp(buffer, "int") == 0) {
            return (Token){TOKEN_INT, 0};
        } else if (strcmp(buffer, "float") == 0) {
            return (Token){TOKEN_FLOAT, 0};
        } else if (strcmp(buffer, "bool") == 0) {
            return (Token){TOKEN_BOOL, 0};
        } else if (strcmp(buffer, "string") == 0) {
            return (Token){TOKEN_STRING, 0};
        } else {
            // 是标识符
            Token token;
            token.type = TOKEN_IDENTIFIER;
            // 注意：这里我们需要存储标识符的名称
            // 为了简化，我们可以使用全局变量或修改 Token 结构
            // 这里假设 Token 结构有一个 name 字段
            strcpy(token.name, buffer);
            return token;
        }
    }
    
    // 其他处理...
}

四、抽象语法树（AST）扩展

我们需要扩展 AST 节点类型，以支持变量声明：

// 扩展 AST 节点类型
typedef enum {
    // 之前的节点类型...
    AST_DECLARATION,     // 变量声明
    AST_DECLARATOR_LIST, // 声明符列表
    AST_DECLARATOR,      // 单个声明符
    AST_TYPE,            // 类型
    AST_IDENTIFIER       // 标识符
} ASTNodeType;

// 扩展 AST 节点结构
typedef struct ASTNode {
    ASTNodeType type;
    union {
        int int_value;         // 数字值
        float float_value;     // 浮点数值
        char *string_value;    // 字符串值
        char *identifier_name; // 标识符名称
        int type_kind;         // 类型种类
    } value;
    struct ASTNode *left;
    struct ASTNode *right;
    struct ASTNode *next; // 用于链表结构，如声明符列表
}

// 类型种类定义
typedef enum {
    TYPE_INT,
    TYPE_FLOAT,
    TYPE_BOOL,
    TYPE_STRING
} TypeKind;

五、递归下降分析器实现

1. 类型解析

// 解析类型
ASTNode* parser_parse_type(Parser *parser) {
    Token token = parser->current_token;
    ASTNode *node = malloc(sizeof(ASTNode));
    node->type = AST_TYPE;
    node->left = NULL;
    node->right = NULL;
    node->next = NULL;
    
    switch (token.type) {
        case TOKEN_INT:
            node->value.type_kind = TYPE_INT;
            parser_match(parser, TOKEN_INT);
            break;
        case TOKEN_FLOAT:
            node->value.type_kind = TYPE_FLOAT;
            parser_match(parser, TOKEN_FLOAT);
            break;
        case TOKEN_BOOL:
            node->value.type_kind = TYPE_BOOL;
            parser_match(parser, TOKEN_BOOL);
            break;
        case TOKEN_STRING:
            node->value.type_kind = TYPE_STRING;
            parser_match(parser, TOKEN_STRING);
            break;
        default:
            fprintf(stderr, "Syntax error: expected type, got %d\n", token.type);
            exit(1);
    }
    
    return node;
}

2. 声明符解析

// 解析单个声明符
ASTNode* parser_parse_declarator(Parser *parser) {
    // 匹配标识符
    Token token = parser->current_token;
    if (token.type != TOKEN_IDENTIFIER) {
        fprintf(stderr, "Syntax error: expected identifier, got %d\n", token.type);
        exit(1);
    }
    
    ASTNode *declarator_node = malloc(sizeof(ASTNode));
    declarator_node->type = AST_DECLARATOR;
    declarator_node->left = NULL;
    declarator_node->right = NULL;
    declarator_node->next = NULL;
    
    // 创建标识符节点
    ASTNode *identifier_node = malloc(sizeof(ASTNode));
    identifier_node->type = AST_IDENTIFIER;
    identifier_node->value.identifier_name = strdup(token.name);
    identifier_node->left = NULL;
    identifier_node->right = NULL;
    identifier_node->next = NULL;
    
    declarator_node->left = identifier_node;
    parser_match(parser, TOKEN_IDENTIFIER);
    
    // 检查是否有初始化表达式
    if (parser->current_token.type == TOKEN_ASSIGN) {
        parser_match(parser, TOKEN_ASSIGN);
        ASTNode *expr_node = parser_parse_expr(parser);
        declarator_node->right = expr_node;
    }
    
    return declarator_node;
}

3. 声明符列表解析

// 解析声明符列表
ASTNode* parser_parse_declarator_list(Parser *parser) {
    ASTNode *list_node = malloc(sizeof(ASTNode));
    list_node->type = AST_DECLARATOR_LIST;
    list_node->left = NULL;
    list_node->right = NULL;
    list_node->next = NULL;
    
    // 解析第一个声明符
    ASTNode *current_declarator = parser_parse_declarator(parser);
    list_node->left = current_declarator;
    
    // 解析后续的声明符
    while (parser->current_token.type == TOKEN_COMMA) {
        parser_match(parser, TOKEN_COMMA);
        ASTNode *next_declarator = parser_parse_declarator(parser);
        current_declarator->next = next_declarator;
        current_declarator = next_declarator;
    }
    
    return list_node;
}

4. 声明解析

// 解析变量声明
ASTNode* parser_parse_declaration(Parser *parser) {
    ASTNode *declaration_node = malloc(sizeof(ASTNode));
    declaration_node->type = AST_DECLARATION;
    declaration_node->left = NULL;
    declaration_node->right = NULL;
    declaration_node->next = NULL;
    
    // 解析类型
    ASTNode *type_node = parser_parse_type(parser);
    declaration_node->left = type_node;
    
    // 解析声明符列表
    ASTNode *declarator_list_node = parser_parse_declarator_list(parser);
    declaration_node->right = declarator_list_node;
    
    // 匹配分号
    parser_match(parser, TOKEN_SEMICOLON);
    
    return declaration_node;
}

六、符号表实现

为了跟踪变量的类型和作用域，我们需要实现一个简单的符号表：

// 符号表条目
typedef struct Symbol {
    char *name;
    TypeKind type;
    struct Symbol *next;
} Symbol;

// 符号表
typedef struct SymbolTable {
    Symbol *symbols;
    struct SymbolTable *parent;
} SymbolTable;

// 创建符号表
SymbolTable* create_symbol_table(SymbolTable *parent) {
    SymbolTable *table = malloc(sizeof(SymbolTable));
    table->symbols = NULL;
    table->parent = parent;
    return table;
}

// 添加符号
void add_symbol(SymbolTable *table, const char *name, TypeKind type) {
    // 检查符号是否已存在
    Symbol *existing = find_symbol(table, name);
    if (existing) {
        fprintf(stderr, "Error: variable '%s' already declared\n", name);
        return;
    }
    
    // 创建新符号
    Symbol *symbol = malloc(sizeof(Symbol));
    symbol->name = strdup(name);
    symbol->type = type;
    symbol->next = table->symbols;
    table->symbols = symbol;
}

// 查找符号
Symbol* find_symbol(SymbolTable *table, const char *name) {
    // 在当前表中查找
    for (Symbol *sym = table->symbols; sym; sym = sym->next) {
        if (strcmp(sym->name, name) == 0) {
            return sym;
        }
    }
    
    // 在父表中查找
    if (table->parent) {
        return find_symbol(table->parent, name);
    }
    
    return NULL;
}

七、语义分析与符号表填充

在解析变量声明后，我们需要进行语义分析，将变量信息填充到符号表中：

// 处理变量声明
void process_declaration(ASTNode *declaration_node, SymbolTable *symbol_table) {
    if (declaration_node->type != AST_DECLARATION) {
        return;
    }
    
    // 获取类型
    ASTNode *type_node = declaration_node->left;
    TypeKind type = type_node->value.type_kind;
    
    // 处理声明符列表
    ASTNode *declarator_list_node = declaration_node->right;
    ASTNode *current_declarator = declarator_list_node->left;
    
    while (current_declarator) {
        // 获取标识符名称
        ASTNode *identifier_node = current_declarator->left;
        const char *name = identifier_node->value.identifier_name;
        
        // 添加到符号表
        add_symbol(symbol_table, name, type);
        
        // 处理初始化表达式（如果有）
        if (current_declarator->right) {
            // 这里可以添加初始化表达式的类型检查
            // 例如，确保初始化表达式的类型与变量类型匹配
        }
        
        current_declarator = current_declarator->next;
    }
}

八、完整示例

现在，我们将上述组件整合起来，创建一个完整的变量声明分析器示例：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

// 类型定义部分（省略，见上文）

// 函数声明部分（省略，见上文）

int main() {
    // 测试变量声明语句
    const char *declarations[] = {
        "int x;",
        "int x = 5;",
        "int x, y, z;",
        "int x = 1 + 2, y, z = 10;",
        "float a = 3.14, b;",
        NULL
    };
    
    // 创建全局符号表
    SymbolTable *global_symtable = create_symbol_table(NULL);
    
    // 测试每个声明语句
    for (int i = 0; declarations[i] != NULL; i++) {
        const char *decl = declarations[i];
        printf("\nTesting declaration: %s\n", decl);
        
        // 初始化词法分析器
        Lexer lexer;
        lexer_init(&lexer, decl);
        
        // 初始化语法分析器
        Parser parser;
        parser_init(&parser, &lexer);
        
        // 解析声明
        ASTNode *ast = parser_parse_declaration(&parser);
        
        // 验证是否到达输入结束
        if (parser.current_token.type != TOKEN_EOF) {
            fprintf(stderr, "Syntax error: unexpected tokens after declaration\n");
            free_ast(ast);
            continue;
        }
        
        // 处理声明，填充符号表
        process_declaration(ast, global_symtable);
        
        // 打印符号表内容
        printf("Symbol table after processing:\n");
        print_symbol_table(global_symtable);
        
        // 释放内存
        free_ast(ast);
    }
    
    // 释放符号表
    free_symbol_table(global_symtable);
    
    return 0;
}

九、测试与验证

1. 测试用例设计

我们设计了以下测试用例，覆盖不同的变量声明形式：

2. 编译与运行

将完整代码保存为 decl_parser.c，然后编译并运行：

gcc decl_parser.c -o decl_parser
./decl_parser

3. 预期输出

Testing declaration: int x;
Symbol table after processing:
x: int

Testing declaration: int x = 5;
Error: variable 'x' already declared
Symbol table after processing:
x: int

Testing declaration: int x, y, z;
Error: variable 'x' already declared
Symbol table after processing:
x: int
y: int
z: int

Testing declaration: int x = 1 + 2, y, z = 10;
Error: variable 'x' already declared
Error: variable 'y' already declared
Error: variable 'z' already declared
Symbol table after processing:
x: int
y: int
z: int

Testing declaration: float a = 3.14, b;
Symbol table after processing:
x: int
y: int
z: int
a: float
b: float

十、错误处理改进

1. 类型错误处理

我们可以添加类型检查，确保初始化表达式的类型与变量类型匹配：

// 检查初始化表达式类型
TypeKind get_expression_type(ASTNode *expr_node) {
    // 简单的类型推断实现
    // 实际应用中可能需要更复杂的类型系统
    switch (expr_node->type) {
        case AST_NUMBER:
            return TYPE_INT;
        case AST_ADD:
        case AST_SUBTRACT:
        case AST_MULTIPLY:
        case AST_DIVIDE:
            // 假设算术表达式结果为 int 类型
            return TYPE_INT;
        case AST_IDENTIFIER:
            // 从符号表中查找标识符类型
            // 这里简化处理
            return TYPE_INT;
        default:
            return TYPE_INT;
    }
}

// 改进的初始化处理
void process_initializer(ASTNode *declarator_node, TypeKind variable_type, SymbolTable *symbol_table) {
    if (!declarator_node->right) {
        return; // 没有初始化表达式
    }
    
    ASTNode *expr_node = declarator_node->right;
    TypeKind expr_type = get_expression_type(expr_node);
    
    // 检查类型匹配
    if (expr_type != variable_type) {
        ASTNode *identifier_node = declarator_node->left;
        fprintf(stderr, "Type error: cannot initialize %s with expression of type %d\n", 
                identifier_node->value.identifier_name, expr_type);
    }
}

2. 作用域处理

我们可以扩展符号表实现，支持嵌套作用域：

// 进入新作用域
SymbolTable* enter_scope(SymbolTable *current_table) {
    return create_symbol_table(current_table);
}

// 退出作用域
SymbolTable* exit_scope(SymbolTable *current_table) {
    if (current_table->parent) {
        SymbolTable *parent = current_table->parent;
        free_symbol_table(current_table);
        return parent;
    }
    return current_table; // 不能退出全局作用域
}

十一、扩展与优化

1. 支持更多类型

可以扩展类型系统，支持：

• 复合类型：数组、结构体、联合体
• 指针类型
• 自定义类型：typedef

2. 支持更复杂的初始化

可以扩展初始化表达式，支持：

• 字符串字面量：string s = "hello";
• 布尔值：bool flag = true;
• 数组初始化：int arr[] = {1, 2, 3};
• 结构体初始化：struct Point p = {1, 2};

3. 性能优化

对于大型程序，可以考虑以下优化：

• 符号表优化：使用哈希表存储符号，提高查找速度
• 内存管理：使用内存池管理 AST 节点，减少内存分配开销
• 语法分析优化：对于简单的声明语句，可以使用更高效的解析策略

十二、总结

通过本集的实战练习，我们成功实现了一个变量声明语句的语法分析器，涵盖了：

1. 文法设计：设计了支持类型声明、多个变量和初始化表达式的文法规则
2. 词法分析器扩展：添加了类型关键字、等号、分号等新的词法单元
3. 语法分析器实现：实现了递归下降分析器，处理变量声明的各种形式
4. 抽象语法树扩展：扩展了 AST 节点类型，支持变量声明相关的结构
5. 符号表实现：实现了简单的符号表，用于跟踪变量的类型信息
6. 语义分析：添加了基本的语义检查，如变量重复声明检测
7. 错误处理：实现了基本的错误检测和报告机制

这个变量声明分析器展示了如何处理更复杂的语法结构，是构建完整编程语言编译器的重要一步。通过理解和扩展这个示例，你可以掌握处理更复杂语法结构的技术，为实现完整的编程语言编译器打下坚实的基础。

在后续的实战章节中，我们将继续扩展语法分析器的能力，处理控制流语句、函数定义等更复杂的语法结构。