DOC PREVIEW
U of I CS 421 - Programming Languages and Compilers

This preview shows page 1-2-16-17-18-34-35 out of 35 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Programming Languages andCompilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/fa06/cs421/Based in part on slides by Mattox Beckman, as updatedby Vikram Adve and Gul AghaElsa L. GunterSemantics• Expresses the meaning of syntax• Static semantics– Meaning based only on the form ofthe expression without executing it– Usually restricted to type checking /type inferenceElsa L. GunterDynamic semantics• Method of describing meaning ofexecuting a program• Several different types:–Operational Semantics–Axiomatic Semantics–Denotational SemanticsElsa L. GunterDynamic Semantics• Different languages bettersuited to different types ofsemantics• Different types of semanticsserve different purposesElsa L. GunterOperational Semantics• Start with a simple notion of machine• Describe how to execute (implement)programs of language on virtualmachine, by describing how to executeeach program statement (ie, followingthe structure of the program)• Meaning of program is how itsexecution changes the state of themachine• Useful as basis for implementationsElsa L. GunterAxiomatic Semantics• Also called Floyd-Hoare Logic• Based on formal logic (first orderpredicate calculus)• Axiomatic Semantics is a logicalsystem built from axioms andinference rules• Mainly suited to simple imperativeprogramming languagesElsa L. GunterAxiomatic Semantics• Used to formally prove a property(post-condition) of the state (the valuesof the program variables) after theexecution of program, assuminganother property (pre-condition) of thestate before execution• Written :{Precondition} Program {Postcondition}• Source of idea of loop invarientElsa L. GunterDenotational Semantics• Construct a function M assigning amathematical meaning to each programconstruct• Meaning function is compositional:meaning of construct built from meaningof parts• Useful for proving properties of programsElsa L. GunterTransition Semantics• Form of operational semantics• Describes how each program construct transformsmachine state by transitions• Rules look like(C, m) --> (C’, m’)• C, C’ is code remaining to be executed• m, m’ represent the state/store/memory/environment– Partial mapping from identifiers to values– Sometimes m (or C) not needed• Indicates exactly one step of computationElsa L. GunterExpressions and Values• Special class of expressions designatedas values– Eg 2, 3 are values, but 2+3 is only anexpression• Memory only holds values• Transitions stop when C is a value• Value is the final meaning of originalexpression (in the given state)• C, C’ used for commands; E, E’ forexpressions; U,V for valuesElsa L. GunterSimple ImperativeProgramming Language• I ∈ Identifiers• N ∈ Numerals• B ::= true | false | B & B | B or B | not B| E < E | E = E• E::= N | I | E + E | E * E | E - E | -E• C::= skip | C;C | I ::= E| if B then C else C fi | while B do C odElsa L. GunterTransitions for Expressions• Identifiers: (I,m) --> m(I)• Numerals are values: (N,m) --> N• Notation - Function update:• m[I<--V] = λ y. if y = I then V else m(y)Elsa L. GunterBooleans:• Values = {true, false}• Operators: (short-circuit)(false & B, m) --> false (B, m) --> (B’’, m)(true & B, m) --> B (B & B’, m) --> (B’’ & B, m)(true or B, m) --> true (B, m) --> (B’’, m)(false or B, m) --> B (B or B’, m) --> (B’’ or B, m)(not true, m) --> false (B, m) --> (B’, m)(not false, m) --> true (not B, m) --> (not B’, m)Elsa L. GunterRelations(E, m) --> (E’’,m)(E ~ E’, m) --> (E’’~E’,m)(E, m) --> (E’,m) (V ~ E, m) --> (V~E’,m)(U ~ V, m) --> true or false, depending onwhether U ~ V holds or notElsa L. GunterArithmetic Expressions(E, m) --> (E’’,m)(E op E’, m) --> (E’’ op E’,m)(E, m) --> (E’,m) (V op E, m) --> (V op E’,m)(U op V, m) -->N where N is thespecified value for U op VElsa L. GunterCommands - in English• skip is done evaluating• When evaluating an assignment, evaluate theexpression first• If the expression being assigned is already avalue, update the memory with the new value forthe identifier• When evaluating a sequence, work on the firstcommand in the sequence first• If the first command evaluates to a new memory(ie completes), evaluate remainder with newmemoryElsa L. GunterCommands(skip, m) --> m(E,m) --> (E’,m)(I::=E,m) --> (I::=E’,m)(I::=V,m) --> m[I <-- V ](C,m) --> (C’’,m’) (C,m) --> m’(C;C’, m) --> (C’’;C’, m’) (C;C’, m) --> (C’, m’)Elsa L. GunterIf Then Else Command - inEnglish• If the boolean guard in and if_then_elseis true, then evaluate the first branch• If it is false, evaluate the second branch• If the boolean guard is not a value, thenstart by evaluating it first.Elsa L. GunterIf Then Else Command(if true then C else C’ fi, m) --> (C, m)(if false then C else C’ fi, m) --> (C’, m)(B,m) --> (B’,m)(if B then C else C’ fi, m)--> (if B’ then C else C’ fi, m)Elsa L. GunterWhile Command(while B do C od, m)--> (if B then C;while B do C od else skip fi, m)In English: Expand a While into a test of the booleanguard, with the true case being to do the body andthe try the while loop again, and the false casebeing to stop.Elsa L. GunterExample Evaluation• First step:(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi, {x -> 7})--> ?Elsa L. GunterExample Evaluation• First step:(x > 5, {x -> 7}) --> ?(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi, {x -> 7})--> ?Elsa L. GunterExample Evaluation• First step:(x,{x -> 7}) --> 7(x > 5, {x -> 7}) --> ?(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi, {x -> 7})--> ?Elsa L. GunterExample Evaluation• First step:(x,{x -> 7}) --> 7(x > 5, {x -> 7}) --> (7 > 5, {x -> 7})(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi, {x -> 7})--> ?Elsa L. GunterExample Evaluation• First step:(x,{x -> 7}) --> 7(x > 5, {x -> 7}) --> (7 > 5, {x -> 7})(if x > 5 then y:= 2 + 3 else y:=3 + 4 fi, {x -> 7})--> (if 7 > 5 then y:=2 + 3 else y:=3 + 4 fi,{x -> 7})Elsa L. GunterExample Evaluation• Second Step:(7 > 5, {x -> 7}) --> true(if 7 > 5 then y:=2 + 3 else y:=3 + 4 fi,{x -> 7})--> (if true then y:=2 + 3 else y:=3 + 4 fi, {x -> 7})• Third Step:(if true then y:=2 + 3 else y:=3 + 4 fi, {x -> 7}) -->(y:=2+3, {x->7})Elsa L. GunterExample Evaluation• Fourth Step: (2+3, {x-> 7}) --> 5(y:=2+3, {x->7}) --> (y:=5, {x->7})• Fifth Step:(y:=5, {x->7}) --> {y -> 5, x -> 7}Elsa L. GunterExample


View Full Document

U of I CS 421 - Programming Languages and Compilers

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

Midterm

Midterm

13 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

Load more
Download Programming Languages and Compilers
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Programming Languages and Compilers and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Programming Languages and Compilers 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?