Translation Schemes In a syntax-directed definition,we do not say anything about the evaluation times of the semantic rules (when the semantic rules associated with a production should be evaluated?). .A translation scheme is a context-free grammar in which: -attributes are associated with the grammar symbols and semantic actions enclosed between braces are inserted within the right sides of productions. ·Ex: A→{}X{…}Y{…} Semantic Actions CS308 Compiler Theory 6
Translation Schemes • In a syntax-directed definition, we do not say anything about the eval i i fh i l ( h h i l luat ion t imes o f t he semant ic ru les ( w hen t he semant ic ru les associated with a production should be evaluated?). • A translation scheme is a context-free grammar in which: – att ib t i t d ith th b l d tt rib u tes are assoc i a t e d with the grammar sym b o ls an d – semantic actions enclosed between braces {} are inserted within the right sides of productions the right sides of productions. • Ex: A → { }X{ }Y{ } ... } X { ... } Y { ... } S ti A ti CS308 Compiler Theory 6 Semantic A ctions
A Translation Scheme Example A simple translation scheme that converts infix expressions to the corresponding postfix expressions. E→TR R→+T{print((+")}R1 R→E T-id print(id.name)} a+b+c>ab+c+ infix expression postfix expression CS308 Compiler Theory 7
A Translation Scheme Example • A simple translation scheme that converts infix expressions to the correspondi fi i ding postfix express ions. E → T R R → + T { print(“+”) } R1 R → ε T → id { print(id.name) } a+b+c Î ab+c+ infix expression postfix expression CS308 Compiler Theory 7
Type Checking A compiler has to do semantic checks in addition to syntactic checks ● Semantic Checks Static-done during compilation -Dynamic-done during run-time Type checking is one of these static checking operations we may not do all type checking at compile-time -Some systems also use dynamic type checking too. A type system is a collection of rules for assigning type expressions to the parts of a program. A type checker implements a type system. A sound type system eliminates run-time type checking for type errors. A programming language is strongly-typed,if every program its compiler accepts will execute without type errors. In practice,some of type checking operations are done at run-time(so,most of the programming languages are not strongly-typed). Ex:int x[100];...x[i]>most of the compilers cannot guarantee that i will be between 0 and 99 CS308 Compiler Theory 8
Type Checking • A compiler has to do semantic checks in addition to syntactic checks. • Semantic Checks Semantic Checks – Static – done during compilation – Dynamic – done during run-time • T h ki ype checking is one of these static checking operations is one of these static checking operations. – we may not do all type checking at compile-time. – Some systems also use dynamic type checking too. • A t t ype system i ll ti f l f i i t i t th t f is a collection of rules for assigning type expressions to the parts of a program. • A type checker implements a type system. • A sound type system eliminates run-time type checking for type errors. • A programming language is strongly-typed, if every program its compiler accepts will execute without type errors. – In practice, some of type checking operations are done at run-time (so, most of the programming languages are not strongly-typed). – Ex: int x[100]; … x[i] Î most of the compilers cannot guarantee that i will be between 0 and 99 CS308 Compiler Theory 8
Intermediate Code Generation Intermediate codes are machine independent codes,but they are close to machine instructions. ● The given program in a source language is converted to an equivalent program in an intermediate language by the intermediate code generator. Intermediate language can be many different languages,and the designer of the compiler decides this intermediate language. syntax trees can be used as an intermediate language 一 postfix notation can be used as an intermediate language. three-address code (Quadraples)can be used as an intermediate language we will use quadraples to discuss intermediate code generation quadraples are close to machine instructions,but they are not actual machine instructions. some programming languages have well defined intermediate languages java-java virtual machine prolog-warren abstract machine In fact,there are byte-code emulators to execute instructions in these intermediate languages CS308 Compiler Theory
Intermediate Code Generation • Intermediate codes are machine independent codes, but they are close to machine instr ctions to machine instructions. • The given program in a source language is converted to an equivalent program in an intermediate language by the intermediate equivalent program in an intermediate language by the intermediate code generator. • Intermediate language can be many different languages, and the designer of the compiler decides this intermediate language. – syntax trees can be used as an intermediate language. – p gg ostfix notation can be used as an intermediate lan gua ge. – three-address code (Quadraples) can be used as an intermediate language • we will use quadraples to discuss intermediate code generation • qp , y uadra ples are close to machine instructions, but the y are not actual machine instructions. – some programming languages have well defined intermediate languages. • java – java virtual machine • prolog – warren abstract machine CS308 Compiler Theory 9 • In fact, there are byte-code emulators to execute instructions in these intermediate languages
Three-Address Code (Quadraples) 。A quadraple is: x :y op z where x,y and z are names,constants or compiler-generated temporaries;op is any operator. But we may also the following notation for quadraples(much better notation because it looks like a machine code instruction) op yizIx apply operator op to y and z,and store the result in x. ·We use the term“three-address code”because each statement usually contains three addresses(two for operands,one for the result). CS308 Compiler Theory 10
Three-Address Code (Quadraples) • A quadraple is: x := y op z where x, y and z are names, constants or compiler-generated temporaries; op is any operator. • But we may also the following notation for quadraples (much better notation because it looks like a machine code instruction) op y,z,x apply operator op to y and z, and store the result in x. • We use the term “three-address code” because each statement usually t i th dd (t f d f th lt) CS308 Compiler Theory 10 con t a ins three addresses (two for operan ds, one for the result)