System Software (Curriculum)

Introduction Introduction , System software, Utility Software, systems programming. Assembler Introduction, Cross Assembler, Micro Assembler, Meta Assembler, Single pass Assembler, Two Pass Assembler, Design of Operation code table, Symbol table, Literal table. Macro Processor Introduction of Macros, Macro processor design, Forward reference, Backward reference, positional parameters, keyword parameters, conditional assembly, Macro calls within Macros, Implementation of macros within Assembler. Designing Macro name table, Macro Definition table, Kew word parameter table, Actual parameter table, Expansion time variable storage. Compiler Structure Analysis-synthesis model of compilation, various phases of a compiler, tool based approach to compiler construction. Lexical and Syntax analysis Interface with input, parser and symbol table, token, lexeme and patterns, difficulties in lexical analysis, error reporting, and implementation. Regular definition, Transition diagrams . context free grammars, ambiguity, associativity, precedence, top down parsing, recursive descent parsing, transformation on the grammars, predictive parsing, Bottom up parsing, operator precedence parsing, LR parsers.

Symantic Analysis & Intermediate Code generation Syntax Directed Translation,S-attributed definition, L-attributed definition, Type checking, Intermediate representations, Code generation & instruction selection issues, basic blocks & flow graphs, register allocation, optimization of basic blocks, loops, global dataflow analysis. Run Time Environment Absolute loader, Relocation - Relocating loader, Dynamic loader, Bootstrap loader, Linking-loader, Program relocatibility, Design of Absolute Loader, Design of direct-linking editor, other Loader scheme e.g. (Binders, Linking Loaders, Overlays, Dynamic Binders.

BOOKS RECOMMENDED
A.V.Aho, R.Sethi & J D.Ullman, Compilers-Principles, Techniques and Tools. Pearson, 2006 G. Sudha Sadasivam, "Compiler Design", Scitech Publication Dr. O.G.Kakde Compiler Design Chattopadhyay System Software Leland L. Beck , System Software -An Introduction to System Programming, 3/E, Addision Wesley,reprint 2003 6) Louden , Kenneth C : Compiler Construction-Principles and Practice,1/E, Thomson, 1997 7) D. M. Dhamdhere : System Programming and Operating System.,2/E,TMH,1999 8) Houlb : Compiler Design in C, PHI, EEE, 1995 1) 2) 3) 4) 5)

System Software Definition

System software consists of a variety of programs that support the operation of a computer (but exactly what?) developing programs: simplify the programming environment by hiding machine level complexity running programs: enable efficient use of hardware by sharing new definition: provides general programming development in which programmers can create specific applications, and lets the applications efficiently use the system hardware

System Software vs. Application Software

System software
Support the operation and use of the computer itself machine dependency (not all features) compilers, assemblers, linkers, loaders, debuggers, OS Application software designed as a tool to solve a specific problem No direct relation with the hardware Web browser, media players, office tools, image processors, messengers text editor ?

Software Environments
Program development environment compilers, assemblers, linkers, debuggers Integrated developing environment (IDE) IDE examples: Visual C++, J Builder, Visual Basic Program run-time environment operating systems, program loaders, program libraries Java run time environment

System Software: Program Development Environment

Compiler Translates programming language (usually high-level, such as C/C++, Java, Pascal) to object code or machine code Assembler Translates assembly language programs to object programs or machine code Linker Combines and resolves references between object programs Loader Loads an executable program and starts its execution (Low-level) Debugger Used to debug executable programs and their associated object and source programs (trace variables, set breakpoints, etc.)

System Software: Program Run-time Environment

Operating System Abstracts machine-level details (e.g. processes, storage, network, input/output devices, window/display management) Program Loader (as on previous slide) Program Libraries Sets of functions for use by other programs (e.g. math library) Static: is included with calling object program when linking Dynamic or Shared: a separate copy of the library in memory is called by programs at run-time

Other System Software

Window system
Provide virtual terminal to an application program Map virtual terminal operations so that they apply to a specific physical region on a screen

Database management system

Store information on the computers permanent storage devices Provide abstract data types (schema) and creates new applicationspecific software optimized for efficient queries/updates on the data according to the schema definition

Steps in Creating and Running Code

C program Compiler Assembly language program Assembler Object: Machine language module Linker Executable: Machine language program Loader Memory Object: Library routine (machine language)

 Source Program: Human-readable program specification (e.g. C++, Assembly program)Usually created using a text editor (ASCII file) Object Program: Produced from a source program by compiling/assembling to intermediate machine code Intermediate machine code augmented by: - References (possibly undefined) - Additional instructions related to combining the object program with other object programs, and/or executing the object program Executable Program: Instruction sequence that a computer can directly execute (machine code) May be produced directly by a compiler/assembler Often produced by combining object programs

Compilers
What qualities are important in a compiler?
1. Correct code 2. Output runs fast 3. Compiler runs fast 4. Compile time proportional to program size 5. Support for separate compilation 6. Good diagnostics for syntax errors 7. Works well with the debugger 8. Good diagnostics for flow anomalies 9. Cross language calls 10. Consistent, predictable optimization

Complier Design
At the highest level of abstraction, compilers are often partitioned into - a front end that deals only with language-specific issues, and - a back end that deals only with machine-specific issues.

How to translate?
The high level languages and machine languages differ in level of abstraction. At machine level we deal with memory locations, registers whereas these resources are never accessed in high level languages. But the level of abstraction differs from language to language and some languages are farther from machine code than others Goals of translation - Good performance for the generated code - Good compile time performance - Maintainable code - High level of abstraction Correctness is a very important issue.

Other Applications
In addition to the development of a compiler, the techniques used in compiler design can be applicable to many problems in computer science.
Techniques used in a lexical analyzer can be used in text editors, information retrieval system, and pattern recognition programs. Techniques used in a parser can be used in a query processing system such as SQL. Many software having a complex front-end may need techniques used in compiler design.
A symbolic equation solver which takes an equation as input. That program should parse the given input equation.

Most of the techniques used in compiler design can be used in Natural Language Processing (NLP) systems.

The Many Phases of a Compiler

Source Program

- The typical compiler consists of several phases each of which passes its output to the next phase. It uses Analysis-Synthesis Model :
- Analysis: convert source code into discrete, manageable chunks. Strings tokens - trees
Symbol-table Manager

Lexical Analyzer

Syntax Analyzer

Semantic Analyzer Error Handler

Intermediate Code Generator

- Synthesis: Convert each chunk into a piece of target code. Trees- Intermediate code target code. Phase 1, 2, 3 : Analysis Phase 4, 5, 6 : Synthesis

Code Optimizer

Code Generator

Target Program

Lexical Analyzer (Scanner)

The lexical phase (scanner) groups characters into lexical units or tokens (Keyword, identifier, number,..etc.)
The input to the lexical phase is a character stream. The output is a stream of tokens. Regular expressions are used to define the tokens recognized by a scanner (e.g. digit -> 0|1|..|9 and letter -> [A..Za-z], and identifier -> letter (letter|digit)*. The scanner can be implemented as a finite state machine. Example: Position := initial + rate * 60 ;
_______ __ _____ _ ___ _ __ _

All are tokens

Lexeme: Position
Tokens: ID

:=

initial
ID

+
PLUS

rate
ID

60

ASSIGN

MULT INT SEMI

Blanks, Line breaks, etc. are scanned out

Syntax Analyzer (Parser)

The parser recognizing whether a program (or sentence) is grammatically well formed. It groups tokens into syntactical units.
The output of the parser is a parse tree representation of the program. Context-free grammars are used to define the program structure recognized by a parser. assignment statement := identifier expression + position expression expression * identifier expression expression initial identifier number
Nodes of tree are constructed using a grammar for the language

rate

60

What is a Grammar?
Grammar is a Set of Rules Which Govern the Interdependencies & Structure Among the Tokens
statement is an assignment statement, or while statement, or if statement, or ... identifier := expression ; (expression), or expression + expression, or expression * expression, or number, or identifier, or ...

assignment statement expression

is an is an

Semantic Analyzer (Semantic)

The semantic analysis phase analyzes the parse tree for context-sensitive information often called the static semantics.
Type Checking - Legality of Operands Real := int + char ; A[int] := A[real] + int ; while char <> int do The output of the semantic analysis phase is an annotated parse tree (augmented with semantic actions).
:= position initial rate + * 60 position initial := + * rate inttoreal 60 Compressed Tree Conversion Action

Symbol Table/Error Handling

Symbol Table Creation / Maintenance
Contains Info on Each Meaningful Token, Typically Identifiers Data Structure Created / Initialized During Lexical Analysis Utilized / Updated During Later Analysis & Synthesis

Error Handling
Detection of Different Errors Which Correspond to All Phases What Kinds of Errors Are Found During the Analysis Phase or Synthesis Phase? What Happens When an Error Is Found?

Intermediate Code Generation

It uses Abstract Machine Version of Code - Independent of Architecture Easy to Produce and Do Final, Machine Dependent Code Generation Three-Address Code: Portable assembly-like language Every memory location can act like a register At most three operands per instruction

temp1 := inttoreal(60) temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3

Code Optimization & Code Generator

Optimizer: Find More Efficient Ways to Execute Code Replace Code With More Optimal Statements Code Generator: Find More Efficient Ways to Execute Code Replace Code With More Optimal Statements
code optimizer temp1 := id3 * 60.0 id1 := id2 + temp1 final code generator movf id3, r2 mulf #60.0, r2 movf id2, r1 addf r2, r2 movf r1, id1

Example
Phase Programmer (source code producer) Scanner (performs lexical analysis) Parser (performs syntax analysis based on the grammar of the programming language) Token string Parse tree or abstract syntax tree Output Source string A=B+C; A, =, B, +, C, ; And symbol table with names
; | = / \ A B + / \ C

Sample

Semantic analyzer (type checking, etc) Intermediate code generator

Annotated parse tree or abstract syntax tree Three-address code, quads, or RTL Three-address code, quads, or RTL Assembly code int2fp B + t1 := t2 int2fp B + t1 C t1 t2 A t1 A

Optimizer Code generator

#2.3

MOVF #2.3,r1 ADDF2 r1,r2 MOVF r2,A ADDF2 #2.3,r2 MOVF r2,A

Peephole optimizer

Assembly code

Compiler Passes
number of Passes
Single - read input file, write output file. It is Preferred Multiple - Each pass may consist of several phases. It is Easier than single, but less efficient because it needs more memory

Compiler / Translator Design Decisions

Choose a source language Large enough to have many interesting language features Small enough to implement in a reasonable amount of time Examples for us: MicroJava, Decaf, MiniJava Choose a target language Either a real assembly language for a machine with an assembler Or a virtual machine language with an interpreter Examples for us: MicroJava VM ( JVM), MIPS (a popular RISC architecture, for which there is a SPIM simulator) Choose an approach for implementation: Either use an existing scanner and parser / compiler generator lex/flex, yacc/bison/byacc, Antlr/JavaCC/SableCC/byaccj/Coco/R. Or implement these yourself (limits the languag26e somewhat)