DOC PREVIEW
UT Arlington CSE 3302 - Language implementation

This preview shows page 1-2-15-16-31-32 out of 32 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 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 32 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 32 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 32 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 32 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 32 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSE 3302Lecture 26: Language implementation2 Dec 2010Nate NystromUniversity of Texas at ArlingtonLanguage definition•Syntax defines the structure of a program• set of rules defining which symbols are a legally structured program•Semantics defines the “meaning” of a program• without semantics, programs are just sequences of charactersSyntax•Syntax defined by a context-free grammar• Example:• Exp ::= Exp + Term | Term• Term ::= Term * Factor | Factor• Factor ::= INTEGER• Expressions with + and * operators over integers• * has higher precedence than +• 1+2*3 parses as 1+(2*3) not as (1+2)*3Semantics•Defines the meaning of programs• Often described informally• in a book (e.g., the Java Language Specification)• or, by a reference implementation (e.g., Python)•Better is to describe the semantics formally• Unambiguous• Allows you to check that language is implemented correctly• Can generate some (or all!) of the implementation automatically• Can reason formally about programs•But, this is rareFormal semantics• Several different ways:• operational semantics - rewrite rules• will discuss briefly later in the semester• denotational semantics - program as mathematical formula• requires deep mathematics (domain theory)–not going to discuss• axiomatic semantics - program as logical statements• less useful–not going to discussOperational semantics•Semantics given by a set of syntactic rewrite rules•e.g., if true then s1 else s2 ➝ s1•e.g., if false then s1 else s2 ➝ s2•e.g., if e then s1 else s2 ➝ if e’ then s1 else s2• when e ➝ e’•e.g,. while e do s ➝ if e then { s; while e do s }• Trivial to translate operational semantics into an implementationLanguage implementation◾Compiler• a program that translates an executable program in one language into an executable program in another language• usually higher-level to lower-level• e.g., C to x86, Java to JVM bytecode, C++ to C• “translator” - target code is in a similar language• “decompiler” - target code is in a higher-level language• “assembler” - source is assembly code, target is machine code◾Interpreter• a program that reads an executable program and produces the results of running that programCompilers• recognize legal (and illegal) programs• generate correct code• manage storage of all variables and code• agree on format for target (object, assembly) codecompilersource codetarget codeerrorsInterpreters• recognize legal (and illegal) programs• evaluate programinterpretersource codeoutputerrorsTraditional two-pass compiler• intermediate representation (IR)• front end maps legal code to IR• back end maps IR onto target machine• simplify retargeting• allow multiple front endsfront endsource codetarget codeerrorsback enderrorsIRTraditional interpreter• intermediate representation (IR)• front end maps legal code to IR• evaluator interprets program, producing outputfront endsource codeoutputerrorsevaluatorerrorsIRFront end• Responsibilities:• recognize legal code• report errors• produce IR• preliminary storage map• shape the code for the back end• Much of the front end construction can be automatedscannersource codeerrorsparsererrorstokenssemantic analysiserrorsIR IRScanner•maps characters into tokens• x = x + y• =>• ID(“x”) = ID(“x”) + ID(“y”)• typical tokens: NUMBER, ID, +, -, *, /, if, while• eliminates whitespace and comments• Simplifies the parser• deal with ~100 tokens vs. 65536 characters• smaller state machine• Uses less memory, fasterParser• Turns stream of tokens into an in-memory representation of the program• recognize context-free syntax• construct intermediate representation (IR)• produce meaningful error messages• attempt error recovery to allow compiler to run longer (reporting more errors) before exitingParsing• Many approaches:• parser generators for different classes of grammars• top-down: LL(1), LL(k), LL(*), PEG• bottom-up: LR(1), LALR(1), LR(k), GLR• implement by hand• LL(k) grammars can be implemented easily by a recursive-descent parser• LL(k) and PEG parsers can be implemented using parser combinatorsParser combinators• “combinator” = a function that combines some number of entities into an entity of the same kind• parser combinator = combine small primitive parsers into a parser for a given language• primitive parsers: parse a single character or token• example combinators:• sequencing: x ~ y –– parse with x, then parse with y• alternation: x | y –– parse with x; if it fails, parse with y• x? –– zero or one x• x* –– zero or more x• x+ –– one or more xIntermediate representation• Representation of the program used by the compiler• Parser builds an intermediate representation (IR)• Many different kinds or IR, used by different phases of the compiler• abstract syntax trees• control-flow graphs• three-address code• static single assignment (SSA)• ...Abstract syntax trees• Much more concise than parse tree• Abstract syntax trees (ASTs) are often used as an IR between front end and back endFront endSo, compilers often use an abstract syntax tree<id:x>2><num:<id:>y+-This is much more conciseAbstract syntax trees (ASTs) are often used as an IR between front endand back end20Abstract syntax trees• In OO language, create a class for each node type• class Exp { }• class Add extends Exp { Exp left, right }• class Sub extends Exp { Exp left, right }• class Int extends Exp { int value }• class Ident extends Exp { String name }• In ML, can define a data type (“tagged union”)• type exp = Add of exp * exp | Sub of exp * exp | Int of int | Ident of stringSymbol tables•Symbol table (aka environment or context) maps names to auxiliary information•variables: type, scope, access flags, etc.•classes: superclasses, interfaces, methods, fields, member classes, access flags, etc.•methods: formal parameter types, return type, exceptions thrown, etc.AST traversals• Many compiler passes are traversals of the AST• Type-checking:• at Int node:• set type to integer• at Ident node:• lookup identifier in symbol table to get type• at Add, Sub node:• recurse on children• check if left and right children integers• set type to integerBack end• Responsibilities:• translate IR into target


View Full Document

UT Arlington CSE 3302 - Language implementation

Documents in this Course
Smalltalk

Smalltalk

11 pages

Syntax

Syntax

5 pages

Syntax

Syntax

5 pages

JAVA

JAVA

57 pages

Semantics

Semantics

41 pages

Control

Control

74 pages

Load more
Download Language implementation
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 Language implementation 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 Language implementation 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?