Compiler: Difference between revisions

From 太極
Jump to navigation Jump to search
Line 71: Line 71:


= Semantic Analysis =
= Semantic Analysis =
* Last "front end" phase
* Last "front end" phase (together with lexical analysis & parsing) to enforce language
* Catches all remaining errors
* Catches all remaining errors



Revision as of 18:13, 26 November 2014

Lexical Analysis

  if (i == j)
    z = 0;
  else
    z = 1;

is indeed below in computers

\tif (i == j)\n\t\tz = 0;\n\telse\n\t\tz = 1;

An implementation must do

  1. Recognize substrings corresponding to tokens
  2. Identify the token class of each lexeme

Token Class

Identifier, keywords, '(', ')', Numbers, ...

  • Token classes correspond to sets of strings.
  • Identifier: A1, Foo, B17
  • Integer: 0, 99
  • Keyword: 'else' or 'if' or 'begin' or ...
  • Whitespace: if___else

For the last code example, the tokens are: if, whitespace, (, i, == , j, \t, \n, else, z, =, 1, ;

                                 Token    
   string ---> Lexical Analysis -------> Parser

Regular Languages

Regular expressions specify regular languages.

Five constructs

  • Two base cases - empty and 1-character strings
  • Three compound expressions - union, concatenation, iteration.

Finite Automata

  • Regular expressions = specification
  • Finite automata = implementation

A finite automaton consists of

  • input alphabet
  • set of states
  • start state
  • set of accepting states
  • set of transitions

Parsing

Input Ouput
Lexer Strings of characters Strings of tokens
Parser String of tokens Parse tree

Context-Free Grammars (CFG)

Parser must distinguish between valid and invalid strings of tokens.

Programming languages have recursive structure.

Semantic Analysis

  • Last "front end" phase (together with lexical analysis & parsing) to enforce language
  • Catches all remaining errors

Coolc checks

  1. all identifiers are declared
  2. types
  3. inheritance relationships
  4. classes defined only once
  5. methods in a class defined only once
  6. reserved identifiers are not misused
  7. ...

Scope

  • Static scope: scope depends only on the program text, not on run-time behavior
  • Dynamically scope: scope depends on execution of the program

Type

  • It doesn't make sense to add a function pointer and an integer in C.
  • It does make sense to add two integers
  • But both have the same assembly language implementation!

A language's type system specifies which operations are valid for which types.

Three kinds of languages:

  • Statistically typed: All or almost all check of types is done as part of compilation (C, Java, Cool)
  • Dynamically typed: Almost all checking of types is done as part of program execution (Scheme, Python, Perl)
  • Untyped: No type checking (machine code)

Optimization

Code Generation

Resource