I. Overview of Symbol Tables and Declaration Checking A. Goals ------------------------------------------ GOALS OF DECLARATION CHECKING Check that: 1. Each declaration has a 2. Each use of an identifier is ------------------------------------------ What should be done if the programming language doesn't have declarations? B. What is a symbol table 1. definition and data structures ------------------------------------------ SYMBOL TABLE def: a *symbol table* is Data Structures: ------------------------------------------ What kind of data structures could be used for a symbol table? Which is easiest to implement? When used to check a program, which is more common: adding/inserting a new mapping (name, attributes) or looking up the attributes of a name? 2. Attributes ------------------------------------------ ATTRIBUTES def: an *attribute* is Examples: ------------------------------------------ a. operations ------------------------------------------ OPERATIONS FOR SYMBOL TABLES int size(); bool full(); bool defined(name); void insert(name, attributes); attributes lookup(name); ------------------------------------------ 3. interaction with scopes a. A program can have multiple scopes ------------------------------------------ SYMBOL TABLES AND SCOPES def: a *scope* is Grammar of a PL/0 program ::= . ::= { } ::= procedure ; ; Example: var x; procedure p; var x; x := 2; procedure q; x := 3; begin x := 1; call q; call p; end. ------------------------------------------ Is a block a scope? What is the final value of the global x in this program? b. strategies for multiple scopes ------------------------------------------ STRATEGIES FOR MULTIPLE SCOPES Needs: Approaches: - [Active Deletion] - [Stack-Based] - [Functional] - [Decorations in AST] ------------------------------------------ II. Declaration Checking A. goals ------------------------------------------ GOALS OF DECLARATION CHECKING Check that: 1. Each declaration has a unique name 2. Each use of an identifier is for a name that has already been declared ------------------------------------------ B. process ------------------------------------------ PROCESS OF DECLARATION CHECKING In each scope: ------------------------------------------ 1. example using the FLOAT language ------------------------------------------ EXAMPLE: FLOAT LANGUAGE See: http://www.cs.ucf.edu/~leavens/COP3402/ example-code/index.html#FloatCalc ------------------------------------------ a. ASTs ------------------------------------------ ASTs for the FLOAT language // file ast.h // types of ASTs (type tags) typedef enum { program_ast, var_decl_ast, assign_ast, begin_ast, if_ast, read_ast, write_ast, /* ignore parse only AST_type */ bin_expr_ast, ident_ast, number_ast, not_expr_ast, } AST_type; // forward declarations typedef struct AST_s AST; typedef AST *AST_list; // ... // P ::= { VD } S typedef struct { AST_list vds; AST *stmt; } program_t; // VD ::= var x typedef struct { var_type vt; const char *name; } var_decl_t; // ... ------------------------------------------ ------------------------------------------ AST STRUCTURE // file ast.h // ... typedef struct AST_s { file_location file_loc; AST_list next; // for lists AST_type type_tag; union AST_u { program_t program; var_decl_t var_decl; assign_t assign_stmt; begin_t begin_stmt; if_t if_stmt; read_t read_stmt; write_t write_stmt; bin_expr_t bin_expr; /* ignore parse-only AST type */ ident_t ident; number_t number; not_expr_t not_expr; } data; } AST; ------------------------------------------ b. symbol table ------------------------------------------ SYMBOL TABLE API // file scope_symtab.h // Maximum number of declarations #define MAX_SCOPE_SIZE 4096 // initialize the symbol table extern void scope_initialize(); // Return the current scope's next offset extern unsigned int scope_size(); // Is the current scope full? extern bool scope_full(); // Is the given name defined? extern bool scope_defined( const char *name); // Requires: !scope_defined(name) // Modify the current scope symbol table // to add a (name |-> attrs) association extern void scope_insert(const char *name, id_attrs *attrs); // Return (a pointer to) the attributes // of the given name // or NULL if it is not declared extern id_attrs *scope_lookup( const char *name); ------------------------------------------ c. Building the symbol table i. programs ------------------------------------------ BUILDING THE SYMBOL TABLE Abstract Syntax of FLOAT: P ::= { VD } S // In file scope_check.c // Build the symbol table for prog // and check for duplicate declarations // or uses of undeclared identifier uses void scope_check_program(AST *prog) { scope_check_varDecls( prog->data.program.vds); scope_check_stmt( prog->data.program.stmt); } ------------------------------------------ ii. variable declarations (1). handling the lists ------------------------------------------ LISTS OF VARIABLE DECLARATIONS // file scope_check.c // build the symbol table and check vds void scope_check_varDecls(AST_list vds) { } ------------------------------------------ (2). handling each variable declaration ------------------------------------------ INDIVIDUAL VARIABLE DECLARATIONS Abstract Syntax of FLOAT: VD ::= float x | bool x // check the var declaration vd // and add it to the symbol table // or produce an error // if the name has already been declared void scope_check_varDecl(AST *vd) { ------------------------------------------ Do we need to accumulate a list of variable declarations? d. checking for undeclared identifier uses What else needs to be done? What if expressions were allowed inside declarations? i. ASTs for statements ------------------------------------------ ASTS FOR STATEMENTS // file ast.h // ... // S ::= assign x E typedef struct { const char *name; AST *exp; } assign_t; // S ::= begin { S } typedef struct { AST_list stmts; } begin_t; // S ::= if E S typedef struct { AST *exp; AST *stmt; } if_t; // ... ------------------------------------------ Can the list in the structure for a begin statement be empty? ii. checking statements What kind of rule is the grammar production for statements? So what does that tell us about how to write the scope_check_stmt function? ------------------------------------------ CHECKING STATEMENTS Abstract syntax of FLOAT: S ::= x = E | begin { S } | if E S | read x | write E // file scope_check.c // check stmt for undeclared id uses void scope_check_stmt(AST *stmt) { ------------------------------------------ ------------------------------------------ CHECKING ASSIGNMENT STATEMENTS // file scope_check.c // S ::= x = E void scope_check_assignStmt(AST *stmt) { ------------------------------------------ What needs to be done? What would the code for scope_check_ifStmt look like? ------------------------------------------ CHECKING BEGIN STATEMENTS // S ::= begin { S } void scope_check_beginStmt(AST *stmt) { ------------------------------------------ What are those curly brackets for? Why isn't the list of statements passed to this function? iii. Expression ASTs ------------------------------------------ ASTS FOR EXPRESSIONS Abstract syntax: E ::= E o E | x | n | ! E o ::= == | != | < | <= | + | - | * | / // file ast.h // ... typedef enum {eqeqop, neqop, ltop, leqop, plusop, minusop, multop, divop } oper; // E ::= E1 o E2 typedef struct { AST *leftexp; oper op; AST *rightexp; } bin_expr_t; // E ::= x typedef struct { const char *name; } ident_t; // E ::= n typedef struct { double value; } number_t; // E ::= !E typedef struct { AST *exp; } not_expr_t; ------------------------------------------ iv. checking expressions What should scope_check_expr do? ------------------------------------------ CHECKING EXPRESSIONS // E ::= E o E | x | n | ! E void scope_check_expr(AST *exp) { switch (exp->type_tag) { case ident_ast: scope_check_ident(exp->file_loc, exp->data.ident.name); break; case bin_expr_ast: scope_check_bin_expr(exp); break; case number_ast: // nothing to do break; case not_expr_ast: scope_check_expr( exp->data.not_expr.exp); break; default: // report error break; } } ------------------------------------------ Why is there nothing to do for number ASTs? ------------------------------------------ CHECKING IDENTIFIERS void scope_check_ident(file_location floc, const char *name) { if (!scope_defined(name)) { general_error(floc, /* ... */, name); } } ------------------------------------------ ------------------------------------------ CHECKING BINARY EXPRESSIONS // E ::= E o E void scope_check_bin_expr(AST *exp) { ------------------------------------------ Does the operator need to be checked? What should the code do?