انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

introduction to compiler

·        Compiling and Translators

·        Why Do we need Translators

·        The Structure of a Compiler

2. Lexical Analysis Phase

·        The need to Lexical Analysis.

·        Specification of tokens(String and Languages).

·        A simple Approach to the Design of lexical Analysis

·        Definition of Regular expression

·        Finite Automata

-non Deterministic Automata

- Deterministic Automata

·        How to Build a lexical Analyzer

·        Convert a Grammar into Transition Diagram.

·        Convert Regular Expression into NFA.

·        Convert NFA into DFA.

·        Minimization of a DFA

·        The Language For specifying Lexical Analyzer

·        Implementing the lexical Analyzer

3. Introduction to Symbol table

·        The Concept of a Symbol table

·        Basic Implementation Techniques

1.     Unordered List

2.     Ordered List

3.     Binary Search Tree

4.     Hash Tables

5.     Resolving Collision in Hash Tables

4. Syntax Analysis Phase

·        Context free Grammars (CFG’s).

·        Derivation and parse tree

·        Representation of Parse Tree

·        Ambiguity

5. Basic Parsing Techniques

·        Handle Parsing

·        Shift-Reduce Parser

·        Stack Implementation of Shift Reduce Parser 

·        Constructing Parse Tree from levees to start Symbol

·        Operator Precedence Parser

·        Operator Relations.

1.   Introduction to compiling

1.1  Compilers and translators

Compilers act as translators, transforming human-oriented programming language into computer oriented machine language. To most users , a compiler can therefore be viewed as a “black box” that performs the transformation illustrated in Fig (1).

Fig (1) A user’s view of a Compiler

A compiler allows most (indeed, virtually all) computer users to ignore the machine-dependent details of machine –language, compilers therefore allow programs and programming expertise to be machine-independent.

      The term Compiler was coined in the early 1950’s by “Grace Murray Hopper”. Translation was then viewed as the “Compilation” of a sequence of subprograms selected from a library. Indeed, Compilation (as we now known it) was then called “automatic programming” and there was almost universal skepticism that it would ever be successful.

Today, the automatic translation of programming language is an accomplished fact, but programming translator is still termed Compilers.

      A translator is a program that takes as input a program written in one programming language (the source language )and produce as output a program written in another language (the object or target language). If the source language is high –level language such as Fortran ,PASCAL , … ,  etc , and the object language is a low level language such as assembly language or machine language , then such a translator is called a Compiler.

Executing a program written in high –level programming language is basically a two step process , as illustrated in Fig(2) the source program must first be compiled  ,that is , translated into the object program , then the resulting object program is loaded into memory and executed. 

Fig (2) Compilation and execution

Certain other translators transform a programming language into a simplified language, called intermediate code, which can be directly executed using a program called an interpreter. We may think of the intermediate code as the machine language of an abstract computer designed to execute the source code.

Interpreter are often smaller than compilers and facilitate the implementation of complex programming language constructs .However,  the main disadvantage of interpreters is that the execution time of an interpreted program is usually slower than that of  the corresponding compiled object program .

      There are several others important types of translators, besides compilers.  If the source language is assembly language and the target language is machine language then the translator is called an assembler

      The term preprocessor is sometimes used for translators that take programs in one high-level language into an equivalent programs in another high level language. For example, there are FORTRAN preprocessor that map "structured" version of  FORTRAN into conventional FORTRAN.

·         Why do we need Translators?

      The answer to this question is obvious to anyone who has programmed in machine language. With machine language we must communicate directly with a computer in terms of bits, registers and very primitive machine operations.

Since a machine language program is nothing more than a sequence of 0 s and 1 s, programming complex algorithm in such a language is terribly tedious and fraught with opportunities for mistakes.

      Perhaps the most serious disadvantage of machine language, coding is that all operation and operands must be specified in a numeric code.

      Because of the difficulties with machine-languages, programming a host of  "higher – level" language have been invented to enable  the programmer to code in away that resembles his own thought processes rather than the elementary steps of the computer. The most immediate step away from machine languages is symbolic assembly language. In this language, a programmer uses numeric names for both operation codes and data addresses .Thus a programmer could write ADD X,Y in assembly languages instead of something like 0110 001110 011011 in machine language( where 0110 is hypothetical  machine operation code for "ADD" and 001110 and 011011 are the address of  X and Y).

A computer, however, cannot execute a program written in assembly languages. That program has to be first translated to machine language, which the computer can understand. The program that performs this translation is the assembler.