Kiến trúc máy tính và hợp ngữ - Chapter 8: Semantic interpretation

Programming Languages2nd editionTucker and NoonanChapter 8Semantic InterpretationTo understand a program you must become both the machine and the program. A. PerlisContents8.1 State Transformations and Partial Functions8.2 Semantics of Clite8.3 Semantics with Dynamic Typing8.4 A Formal Treatment of SemanticsSemantics of a PLDefines the meaning of a programSyntactically validStatic type checking validHistorical ProblemValid program had different meanings on different machinesMore than (e.g.) size of an int or floatProblem was lack of precision in defining meaningMethodsCompiler C on Machine MEx: Fortran on IBM 709/7090Ex: PL/1 (F) on IBM 360 seriesOperational Semantics – Ch. 7Axiomatic Semantics – Ch. 18Denotational Semantics – Ch. 8.4ExampleEnvironmenti, j at memory locations 154, 155{ , }Statei has value 13, j has value -1{ ..., , , ...}Simple StateIgnore environmentSet of identifier – value pairsEx: { , Special value undefined8.1 State TransformationsDefn: The denotational semantics of a language defines the meanings of abstract language elements as a collection of state-transforming functions.Defn: A semantic domain is a set of values whose properties and operations are independently well-understood and upon which the rules that define the semantics of a language can be based.Meaningless Programfor (i = 1; i > -1; i++) i--;// i flips between 0 and 1// why???Meaningless ExpressionAre all expressions meaningful?Give examples8.2 C++Lite SemanticsState – represent the set of all program statesA meaning function M is a mapping:M: Program → StateM: Statement x State → StateM: Expression x State → ValueMeaning Rule 8.1The meaning of a Program is defined to be the meaning of the body when given an initial state consisting of the variables of the decpart initialized to the undef value corresponding to the variable's type. State M (Program p) { // Program = Declarations decpart; Statement body return M(p.body, initialState(p.decpart));}public class State extends HashMap { ... } State initialState (Declarations d) { State state = new State( ); for (Declaration decl : d) state.put(decl.v, Value.mkValue(decl.t)); } return state;}StatementsM: Statement x State → StateAbstract SyntaxStatement = Skip | Block | Assignment | Loop | Conditional State M(Statement s, State state) { if (s instanceof Skip) return M((Skip)s, state); if (s instanceof Assignment) return M((Assignment)s, state); if (s instanceof Block) return M((Block)s, state); if (s instanceof Loop) return M((Loop)s, state); if (s instanceof Conditional) return M((Conditional)s, state); throw new IllegalArgumentException( );}Meaning Rule 8.2The meaning of a Skip is an identity functionon the state; that is, the state is unchanged.??? State M(Skip s, State state) { return state;}Meaning Rule 8.3The output state is computed from the input state by replacing the value of the target variable by the computed value of the source expression.Assignment = Variable target; Expression source State M(Assignment a, State state) { return state.onion(a.target, M(a.source, state));}// ??? onion// ??? M(a.source, state)Meaning Rule 8.4The meaning of a conditional is:If the test is true, the meaning of the thenbranch;Otherwise, the meaning of the elsebranchConditional = Expression test; Statement thenbranch, elsebranch State M(Conditional c, State state) { if (M(c.test, state).boolValue( )) return M(c.thenbranch); else return M(e.elsebranch, state);}Expression SemanticsDefn: A side effect occurs during the evaluation of an expression if, in addition to returning a value, the expression alters the state of the program.Ignore for now.ExpressionsM: Expression x State → ValueExpression = Variable | Value | Binary | UnaryBinary = BinaryOp op; Expression term1, term2Unary = UnaryOp op; Expression termVariable = String idValue = IntValue | BoolValue | CharValue | FloatValueMeaning Rule 8.7The meaning of an expression in a state is a value defined by: If a value, then the value. Ex: 3 If a variable, then the value of the variable in the state. If a Binary: Determine meaning of term1, term2 in the state. Apply the operator according to rule 8.8... Value M(Expression e, State state) { if (e instanceof Value) return (Value)e; if (e instanceof Variable) return (Value)(state.get(e)); if (e instanceof Binary) { Binary b = (Binary)e; return applyBinary(b.op, M(b.term1, state), M(b.term2, state); } ...