A program is a block that consists of possibly empty sequences of declarations and statements.
Program[1]==A declaration defines one or more variables of type int. Each declaration is terminated by a ';'. The symbol VarDecl distinguishes this defining occurrence of Ident from other occurrences. Several identifiers are separated by ','.This macro is invoked in definition 12.Prog ::= Block . Block ::= '{' Decl* Stmt* '}' .
Declarations[2]==There are several forms of statements: assignments, conditionals, switch statements, break statements, for loops, blocks, and expression statements. Statements, except blocks and switch statements are terminated by ';'.This macro is invoked in definition 12.Decl ::= 'int' VarDecls ';' . VarDecls::= VarDecl // ',' . VarDecl ::= Ident .
Statements[3]==An assignment has the usual notation. The Assign symbol is introduced, because for loops contain assignments without terminating ';'. The symbol VarSet distinguishes the variable on the left-hand side from variable occurrences where their value is accessed rather than set.This macro is invoked in definition 12.Stmt ::= Block . Stmt ::= Expr ';' . Stmt ::= 'break' ';' .
Assignments[4]==For statements consist of the initial assignment, the iteration condition, the assignment executed after each iteration, and the iterated statement.This macro is invoked in definition 12.Stmt ::= Assign ';' . Assign ::= VarSet '=' Expr . VarSet ::= Ident .
For loop[5]==The else branch of an if statement is optional. The dangling else ambiguity is resolved such that an else branch is bound to the innermost if statement. The $'else' modification instructs the parser generator not to reduce that production if an 'else' token follows.This macro is invoked in definition 12.Stmt ::= ForStmt . ForStmt ::= 'for' '(' ForCtrl ';' Expr ';' Assign ')' Stmt . ForCtrl ::= Assign .
If statement[6]==Switch statements have the same structure as in C.This macro is invoked in definition 12.Stmt ::= 'if' '(' Expr ')' Stmt $'else' . Stmt ::= 'if' '(' Expr ')' Stmt 'else' Stmt .
Switch statement[7]==The following expression syntax specifies precedence and associativity of operators: MulOpr have highest precedence, CmpOpr have lowest precedence. AddOpr and MulOpr are left-associative, and CmpOpr are not associative.This macro is invoked in definition 12.Stmt ::= SwStmt . SwStmt ::= 'switch' '(' Expr ')' '{' Case* '}' . Case ::= CaseLab Stmt* . CaseLab ::= 'case' CaseLit ':' . CaseLab ::= 'default' ':' . CaseLit ::= Number .
Expressions[8]==The precedence and associativity rules are only relevant for the construction of the tree. The then constructed tree need not distinguish between Expr, Sum, Fact, and Operand. They are all represented by an Expr node. Similarly all operators are represented by an Opr node in the tree:This macro is invoked in definition 12.Expr ::= Sum CmpOpr Sum / Sum . Sum ::= Sum AddOpr Fact / Fact . Fact ::= Fact MulOpr Operand / Operand . CmpOpr ::= '<' / '>' / '==' / '!=' / '<=' / '>=' . AddOpr ::= '+' / '-' . MulOpr ::= '*' / '/' . Operand ::= '(' Expr ')' .
Expressions in abstract tree[9]==Operands are integral numbers, identifiers that denote access of a variable value, or calls of predefined functions. The latter may have an arbitrary number of arguments.This macro is invoked in definition 13.Expr ::= Sum Fact Operand . Opr ::= CmpOpr AddOpr MulOpr .
Operands[10]==The notation for numbers, identifiers, and comments are specified as in C using canned token specifications.This macro is invoked in definition 12.Operand ::= Number . Operand ::= VarUse . VarUse ::= Ident . Operand ::= Ident '(' Params ')' . Params ::= . Params ::= Expr // ',' .
Tokens[11]==This macro is invoked in definition 14.Number: C_INTEGER Ident: C_IDENTIFIER C_COMMENT
tree.con[12]==This macro is attached to an output file.Program[1] Declarations[2] Statements[3] Assignments[4] For loop[5] If statement[6] Switch statement[7] Expressions[8] Operands[10]
tree.sym[13]==This macro is attached to an output file.Expressions in abstract tree[9]
tree.gla[14]==This macro is attached to an output file.Tokens[11]
Using a SYMBOL computation for Stmt INH.WarnSingleIf = 0; avoids to take care of any other Stmt context. It is overridden by the RULE computation in the one-sided if context.
dangling else[15]==This macro is invoked in definition 16.ATTR WarnSingleIf: int; SYMBOL Stmt COMPUTE INH.WarnSingleIf = 0; END; RULE: Stmt ::= 'if' '(' Expr ')' Stmt COMPUTE Stmt[2].WarnSingleIf = 1; END; RULE: Stmt ::= 'if' '(' Expr ')' Stmt 'else' Stmt COMPUTE IF (Stmt[1].WarnSingleIf, message (WARNING, "beware of dangling else!", 0, COORDREF)); END;
dangling.lido[16]==This macro is attached to an output file.dangling else[15]
The functions f2, f1, f0 are chosen such that f1 yields the appropriate value of a single item, and for any x the equation f2 (x, f0 ()) = x holds.
The first CONSTITUENTS doesn't use the values of CaseLit.Sym at all for counting, since ARGTOONE is a constant (unary!) function, that yields 1 for any argument. f_INT_MAX and f_INT_MIN are constant function that yield the largest repectively the smallest int value.
In case of nested switch statements the CONSTITUENTS do not access CaseLit occurrences of inner switch statements. This fact could be made explicit by using CONSTITUENTS CaseLit.Sym SHIELD (SwStmt) WITH ...
The SYMBOL computation for CaseLit acesses the value of the terminal Number.
Compute Switch Case Lables[17]==ADD, ZERO, ARGTOONE, and IDENTICAL are predefined macros in LIDO. The other functions are supplied by the following cpp macros:This macro is invoked in definition 19.ATTR Sym: int; SYMBOL SwStmt COMPUTE printf ("switch in line %d has %d case labels in the range %d to %d\n", LINE, CONSTITUENTS CaseLit.Sym WITH (int, ADD, ARGTOONE, ZERO), CONSTITUENTS CaseLit.Sym WITH (int, MIN, IDENTICAL, f_INT_MAX), CONSTITUENTS CaseLit.Sym WITH (int, MAX, IDENTICAL, f_INT_MIN)); END; SYMBOL CaseLit COMPUTE SYNT.Sym = TERM; END;
Define Constituents Procedure Macros[18]==This macro is invoked in definition 20.#include <limits.h> #define MIN(x,y) ((x)<=(y) ? (x) : (y)) #define MAX(x,y) ((x)>=(y) ? (x) : (y)) #define f_INT_MIN() INT_MIN #define f_INT_MAX() INT_MAX
switch.lido[19]==This macro is attached to an output file.Compute Switch Case Lables[17]
switch.head[20]==This macro is attached to an output file.Define Constituents Procedure Macros[18]
We specify C-like scope rules by using the library module CScope:
Instanciating CScope Module[21]==This module provides computational roles for a root symbol RootScope that contains all scopes, for a symbol RangeScope that forms a possibly nested scope, and for defining and applied identifier occurrences, IdDefScope, IdUseEnv.This macro is invoked in definition 34.$/Name/CScope.gnrc:inst
These roles are associated to our grammar symbols.
Inheritance of scope ranges to grammar symbols[22]==Additionally we have to make the value of the terminal Ident available one level up at the VarDecl, VarUse, and VarSet nodes. That is achieved by the computation associated to the abstract symbol IdOcc:This macro is invoked in definition 35.SYMBOL Prog INHERITS RootScope END; SYMBOL Block INHERITS RangeScope, RangeUnique END; SYMBOL VarDecl INHERITS IdDefScope END; SYMBOL VarUse INHERITS IdUseEnv END; SYMBOL VarSet INHERITS IdUseEnv END;
Making Available Identifier Code[23]==Our scope rules can be violated in any of two cases: A variable is used but not defined, or a variable is defined more than once in a range. In each case we want to produce an error message.This macro is invoked in definition 35.SYMBOL IdOcc COMPUTE THIS.Sym = TERM; END; SYMBOL VarDecl INHERITS IdOcc END; SYMBOL VarUse INHERITS IdOcc END; SYMBOL VarSet INHERITS IdOcc END;
The first case is checked by inspecting the Key attribute of an applied identifier occurrence:
Check if variables are defined[24]==The check for multiply defined variables is obtained from the library:This macro is invoked in definition 35.SYMBOL IsDefined COMPUTE IF (EQ (THIS.Key, NoKey), message (ERROR, "variable not defined", 0, COORDREF)); END; SYMBOL VarUse INHERITS IsDefined END; SYMBOL VarSet INHERITS IsDefined END;
Instanciate Module to check for multiple definitions[25]==The computational role Unique provides a compuation for a boolean attribute that indicates uniqueness. The RangeUnique role is associated to the root of the grammar.This macro is invoked in definition 34.$/Prop/Unique.gnrc:inst
Check for multiple definitions of variables[26]==We now get to the analysis of variable usage. We split the task into two subtasks. First it is checked whether a variable is set (used) somewhere in the program. A message is issued at the variable declaration if it is never set (used).This macro is invoked in definition 35.SYMBOL Prog INHERITS RangeUnique END; SYMBOL VarDecl INHERITS Unique COMPUTE IF (NOT (THIS.Unique), message (ERROR, "variable is multiply defined", 0, COORDREF)); END;
For that purpose we associate properties IsSet and IsUsed to variables:
Set and Used Properties of Variables[27]==The attribute Prog.GotUseSet represents the computational state when the IsSet and IsUsed properties are set at all variable occurrences. It is a precondition for the check in the declaration context.This macro is invoked in definition 36.IsSet: int; IsUsed: int;
Propagate Definitions and Uses of Variables[28]==For the second analysis we associate the property LastAccess to variables representing the current state of a variable.This macro is invoked in definition 35.SYMBOL Prog COMPUTE THIS.GotUseSet = CONSTITUENTS (VarSet.GotUseSet, VarUse.GotUseSet); END; SYMBOL VarSet COMPUTE THIS.GotUseSet = ResetIsSet (THIS.Key, 1); END; SYMBOL VarUse COMPUTE THIS.GotUseSet = ResetIsUsed (THIS.Key, 1); END; SYMBOL VarDecl COMPUTE IF (NOT (GetIsSet (THIS.Key, 0)), message (WARNING, "variable is never set", 0, COORDREF)) <- INCLUDING Prog.GotUseSet; IF (NOT (GetIsUsed (THIS.Key, 0)), message (WARNING, "variable is never used", 0, COORDREF)) <- INCLUDING Prog.GotUseSet; END;
LastAccess property[29]==It may assume one of the valuesThis macro is invoked in definition 36.LastAccess: int;
Possible Values of LastAccess property[30]==We simulate assignments and accesses of variables along a left-to-right CHAIN through the program. (This simulation is of course not accurate in the presence of loops or if statements. Hence not all situation where a variable may be used before it is set will be flagged with a warning.)This macro is invoked in definition 37.#define unused 0 #define set 1 #define used 2
That CHAIN is started in the Prog context. It does not carry a value.
The computations that set LastAccess are allocated on the UseSetChain CHAIN by each having UseSetChain as both pre- and postcondition.
LastAccess starts with the value unused at the variable declaration and may then alternate between set and used along the CHAIN.
Define SetUsed Chain[31]==The CHAIN computation for VarUse comprises two actions which have to be executed in that order: first check the LastAccess state, then modify it to "used". The ORDER constructs combines these actions.This macro is invoked in definition 35.CHAIN UseSetChain: VOID; SYMBOL Prog COMPUTE CHAINSTART HEAD.UseSetChain = "yes"; END; SYMBOL VarDecl COMPUTE THIS.UseSetChain = ResetLastAccess (THIS.Key, unused) <- THIS.UseSetChain; END;
Mark Variable Use in SetUsed Chain[32]==The LastAccess property for an assignment has to occur after the the expression is examined by the CHAIN computations. Hence it is allocated with suitable pre- and postconditions in the RULE context for assignments. (If it were specified as a CHAIN computation in the SYMBOL VarSet context, it would occur BEFORE the CHAIN computations of the righthand side expression.)This macro is invoked in definition 35.SYMBOL VarUse COMPUTE THIS.UseSetChain = ORDER ( IF (EQ (GetLastAccess (THIS.Key, unused), unused), message (WARNING, "variable is used before set", 0, COORDREF)), ResetLastAccess (THIS.Key, used)) <- THIS.UseSetChain; END;
Mark Varialbe Definition in SetUsed Chain[33]==This macro is invoked in definition 35.RULE: Assign ::= VarSet '=' Expr COMPUTE Assign.UseSetChain = ResetLastAccess (VarSet.Key, set) <- Expr.UseSetChain; END;
vars.specs[34]==This macro is attached to an output file.Instanciating CScope Module[21] Instanciate Module to check for multiple definitions[25]
vars.lido[35]==This macro is attached to an output file.Inheritance of scope ranges to grammar symbols[22] Making Available Identifier Code[23] Check if variables are defined[24] Check for multiple definitions of variables[26] Propagate Definitions and Uses of Variables[28] Define SetUsed Chain[31] Mark Variable Use in SetUsed Chain[32] Mark Varialbe Definition in SetUsed Chain[33]
vars.pdl[36]==This macro is attached to an output file.Set and Used Properties of Variables[27] LastAccess property[29]
vars.head[37]==This macro is attached to an output file.Possible Values of LastAccess property[30]
for control property[38]==It can have one of three values:This macro is invoked in definition 44.IsForCtrl: int;
possible values of for control property[39]==For variables derived from ForCtrl that property is set to ForCtrl if it is not yet set, or to MultForCtrl if it is already set elsewhere.This macro is invoked in definition 45.#define NoForCtrl 0 #define ForCtrl 1 #define MultForCtrl 2
A warning is issued if the ForCtrl variable is set to MultForCtrl. The dependency on INCLUDING Prog.GotForCtrl ensures that ALL offending ForCtrl occurrences are indicated (rather than only the last one).
for control used in other statement warning[40]==The task to check for control variables used outside for statement can be expressed as onother instance of a name analysis task: A for control variable is defined by a ForCtrl with the ForStmt being its range. Usage of a for control variable outside its range is considered to be an undefined occurrence, indicated by a warning.This macro is invoked in definition 46.SYMBOL Prog COMPUTE SYNT.GotForCtrl = CONSTITUENTS ForCtrl.GotForCtrl; END; SYMBOL ForCtrl: Key: DefTableKey; SYMBOL ForCtrl COMPUTE SYNT.Key = CONSTITUENT VarSet.Key; SYNT.GotForCtrl = SetIsForCtrl (THIS.Key, ForCtrl, MultForCtrl); IF (EQ (MultForCtrl, GetIsForCtrl (THIS.Key, ForCtrl)), message (WARNING, "ctrl variable used in other for statement", 0, COORDREF)) DEPENDS_ON INCLUDING Prog.GotForCtrl; END;
Hence we use another instance of the CScope module:
CScope instanciation used to check for control variables[41]==The parameter +instance=For modifies the identifiers used in the module to ForKey, ForRootScope, ForRangeScope, ForIdDef, ForIdUse, and such avoids name clashes with identifers of the modules used before. The parameter +referto=For causes the module to use key attributes named ForKey instead of Key. Hence, at a ForCtrl we can have both a Key attribute representing the variable according to the original scope rules and a ForKey attribute representing the object according to our For rules.This macro is invoked in definition 47.$/Name/CScope.gnrc+instance=For +referto=For:inst
The condition for the warning then checks whether the variable is a for control variable (property IsForCtrl) and it is undefined with respect to uses in our "for ranges" (THIS.ForKey is NoKey). The warning has to depend on a computational state where th property IsForCtrl is set for all variables (INCLUDING Prog.GotForCtrl).
for control used outside of scope warning[42]==Finally we check for control variables being assigned outside the for control part. We associate an attribute InForCtrl to Assign. It indicates whether the Assign occurs in a for control part. (We use the same technique of SYMBOL computation and overriding as in the dangling else task.) Then the warning condition is similar to that of the above warning.This macro is invoked in definition 47.SYMBOL Prog INHERITS ForRootScope END; SYMBOL ForStmt INHERITS ForRangeScope END; SYMBOL ForCtrl INHERITS ForIdDefScope COMPUTE THIS.Sym = CONSTITUENT VarSet.Sym; END; SYMBOL VarSet INHERITS ForIdUseEnv, OutsideFor END; SYMBOL VarUse INHERITS ForIdUseEnv, OutsideFor END; SYMBOL OutsideFor COMPUTE IF (AND (NE (NoForCtrl, GetIsForCtrl (THIS.Key, NoForCtrl)), EQ (THIS.ForKey, NoKey)), message (WARNING, "for ctrl variable used outside for scope", 0, COORDREF)) DEPENDS_ON INCLUDING Prog.GotForCtrl; END;
assignment to for control variable warning[43]==This macro is invoked in definition 47.ATTR InForCtrl: int; SYMBOL Assign COMPUTE THIS.InForCtrl = 0; END; RULE: ForStmt ::= 'for' '(' ForCtrl ';' Expr ';' Assign ')' Stmt COMPUTE Assign.InForCtrl = 1; END; RULE: ForCtrl ::= Assign COMPUTE Assign.InForCtrl = 1; END; RULE: Assign ::= VarSet '=' Expr COMPUTE IF (AND (NE (NoForCtrl, GetIsForCtrl (VarSet.Key, NoForCtrl)), NOT (Assign.InForCtrl)), message (WARNING, "assignment to for control variable", 0, COORDREF)) DEPENDS_ON INCLUDING Prog.GotForCtrl; END;
loop.pdl[44]==This macro is attached to an output file.for control property[38]
loop.head[45]==This macro is attached to an output file.possible values of for control property[39]
loop.lido[46]==This macro is attached to an output file.for control used in other statement warning[40]
loop.specs[47]==This macro is attached to an output file.CScope instanciation used to check for control variables[41] for control used outside of scope warning[42] assignment to for control variable warning[43]