Semantic Analysis Rules for Phase 3

Comments

Semantic actions should be executed in a separate pass, after the abstract syntax tree has been built. We will be using a symbol table to keep track of declared symbols and help typechecking. As scopes get nested, we have to use a stack of scopes, and use static scoping rules to access non-local variables. You may choose to implement this as a stack of symbol tables.

Recursive procedures are allowed. To facilitate this, all function, procedure, and variable declarations should be processed within the scope before the function/procedure bodies are processed. Function parameters should be considered as belonging to the same scope as the function body.

Data structures:

A stack used to record information about the scopes: pointer to start of symbol table entries for the scope and possibly other information.

Used to record names and attributes of all symbols declared in the program. Organized as a list and accessed by scope. It should be possible to add, remove, and lookup entries in this table.

Might be needed.

Types:

Variables can be of two basic types in our programming language: integer and boolean. As well, we have text strings, which can be considered as a type (STRING) which cannot be manipulated in any way, stored, or returned. For convenience we can assume that all constructs in the language which are not expressions or text strings are of type VOID. No type-casting is allowed in our language
(i.e., 1 & true is illegal). Note that comparison operators have boolean type.

Symbols:

Duplicate symbols in the same scope are illegal, as well as use of an identifier which has not been declared in the current or any previous scope. Checks as well should be made that no attempt is made to assign to a constant, scalar parameter, array name, function, or procedure (this includes the 'get' statement as well).

Semantic Analysis Operators

In what follows, we will give some semantic rules to the language constructs. Your job is to extend them to all constructs and implement them.

program : scope

scope: BEGIN declarations statements END
            /* First start a new scope for declarations and statements.
               Upon exit, remove current scope off the stack */

declaration:    
        type : identifier = expression ,
        CONST type : identifier = expression ,
        type : identifier [ expression ] ,
             /* If identifier is not already declared in current scope,
                insert variable/constant/array into table. In first two
                rules a check should be made that expression, if
                present, agrees with type. For array bounds expression
                should always be of type integer. */

        type  FUNCTION identifier ( parameters ) scope ,
             /* make new entry in symbol table for function.
                Start new scope with parameter list once declarations
                for the current scope level have been processed */

        PROCEDURE  identifier ( parameters ) scope ,
             /* same as function declaratiion, but type is VOID */

/* make sure that type of all statements is VOID */

statement:      
        variable = expression ,
             /* check that var is an lvalue and type(var) = type(exp) */

        IF expression THEN statements
             ELSEIF expression THEN statements ...
             ELSE statements
             END
        WHILE expression DO statement END ,
             /* check type(exp) is boolean */

        BREAK ,
             /* Check that the exit statement is contained within a
                loop construct within the current function scope */

        RETURN ( expression ) ,
             /* make sure that type(exp) = type(return(current scope))
                (= VOID if current scope is procedure) */
        PUT output ,
             /* make sure that all expressions are evaluable types
                i.e. no procedure calls, array names, etc. */

        GET input ,
             /* check that all inputs are lvalues */

        procedurename ( arguments ) ,
             /* make sure procedurename is declared as procedure, and
                that args match in number and type */

expression:     
        - expression ,
        expression + expression ,
        expression - expression ,
        expression * expression ,
        expression / expression ,
        expression ^ expression ,
             /* all sub exp's involved must be of type integer, exp's
                return type is integer */

        ! expression ,
        expression & expression ,
        expression | expression ,
             /* all sub exp's involved must be of type boolean, exp's
                return type is boolean */

        expression < expression ,
        expression <= expression ,
        expression > expression ,
        expression >=  expression ,
             /* all sub exp's involved must be of type integer, exp's
                return type is boolean */

        expression =  expression ,
        expression != expression ,
             /* both sub exp's involved must be of same type (either
                boolean or integer), exp's return type is boolean */

        id             
             /* Check if id present and valid rvalue (e.g. not an array
                or procedure name; return type of id. */

        id [ expression ]
             /* Check if id present and an array. Check if type of exp
                is integer. */

        id ( args )  
             /* Check if id present and a function. Check if type and
                number of args match declaration. */