Language Processing g4i69

OS – System Software

Defn System Software: (Source : Wiki)

System software is computer software designed to operate and control the computer hardware and to provide a platform for running application software.[

Components Of System Software 1. Hardware – provides basic computing resources (U, memory, I/O devices). 2. Operating system – controls and coordinates the use of the hardware among the various application programs for the various s. 3. Applications programs – define the ways in which the system resources are used to solve the computing problems of the s (compilers, database systems, video games, business programs). 4. s (people, machines, other computers).

Abstract View of System Components

Operating System Concepts

Language Processor Basics Why Language Processing? -Language Processing activities arise due to the diff between the manner in which a software designer describes the ideas and the manner in which ideas are implemented in a computer system. - Application Domain : The designer expresses the ideas in related to the application domain. - Execution Domain : To implement these ideas, their description has to be interpreted in related to the execution domain. - Semantic : We use the term semantics to represent the rules of meaning of a domain. - Semantic Gap : To represent the difference between the semantics of two domains. Semantic Gap

Application Domain

Execution Domain

• Consequences of semantic gap – large development times, large development efforts, poor quality of s/w • Can be tackled by Programming Languages (PLs). • Software engineering steps aimed at the use of a PL can be grouped into 1. Specification, design and coding steps. 2. PL implementation steps.

Bridged by designer of programming lang processor

Bridged by s/w devnt team

Application Domain

Specification Gap PL Domain

Shorter Gap

Execution Gap Execution Domain

Definition – Language Processor : A language processor is a software which bridges a specification or execution gap. Language Processing is the activity performed by a language processor. Source program: Input to language processor. Target program : Output of language processor. The language are respectively called source language and target language.

Spectrum of language processors: 1. Language translator : Bridges an execution gap to the machine language. (e.g. .Net CLR, Delphi) 2. Assembler : Language translator whose source language is assembly language. 3. Compiler : Language translator which is not an assembler. 4. Detranslator : Translator working in either direction. 5. Preprocessor : Is a language processor which bridges execution gap but is not a language translator. 6. Language migrator : bridges the specification gap between two PLs. 7. Interpreter : Is a language processor which bridges an execution gap without generating a machine language program. Example: C++ Program converted to C Program by C++ Preprocessor C++ Program converted to machine language by C++ translator.

Problem oriented and procedural oriented languages Classical solution to bridge specification gap is to build a PL such that the PL domain is very close to the application domain, which leads to small specification gap. Such PLs can only be used for specific applications, hence they are called problem oriented language. They however have large execution gap. e.g. COBOL is made for business purpose A procedural language provides general purpose facilities required in most app domains. e.g. C, Java, C# etc.

Language Processing Activities Fundamental language processing activities can be divided into those that bridges the specification gap and those that bridges the execution gap. i.e. 1. Program generation activities 2. Program execution activities Should be error free and perfect

Program Generation Program generation activities -It aims at automatic generation of a program.

Errors

Program Specification

Program Generator

Program in target PL

Contd.. Program generator Specification gap

Application Domain

Program generator Domain

Target PL Domain

Execution Domain

Program Execution Two popular models are 1. Translation 2. Interpretation Program Translation It bridges the execution gap by translating a program written in a PL, called source Program (SP), into an equivalent program in the machine or assembly language, called target program. Characteristics of the program translation model: A program must be translated before it can be executed. The translated program may be saved in a file. The saved program may be executed repeatedly. A program must be retranslated following modifications.

Program execution contd.. Program Interpretation -Interpreter reads the source program and stores in a memory. - During interpretation, it takes a source statement, determines its meaning and performs actions which implement it. - This includes computational and input-output actions. - Program interpretation can be compared to execution of Machine level program by U. - U uses Program Counter (PC) to note the address of next intstruction to be executed. -Instruction execution cycle -1. Fetch the instruction -2. Decode the instruction -3. Execute the instruction - 4. Change PC and repeat the cycle

Program execution contd.. Program Interpretation contd.. -Interpretation cycle -1. Fetch the statement. -2. Analyze the statement and determine its meaning -3. Execute the meaning of statement - 4. Change PC and repeat the cycle

-i.e. After interpretation, source program is retained in the source form itself, means, no target program form exists.

Fundamentals of Language Processing Language Processing = Analysis of SP + Synthesis of TP

Analysis Phase Input of SP Analysis phase -> Specification of the source language Specification consists of 3 components: 1. Lexical rules 2. Syntax rules 3. Semantic rules Lexical Rules : governs the formation of valid lexical units in the SL Syntax Rules : governs the formation of valid statements in the SL Semantic Rules : associate meaning with valid statements

Example : Analysis Phase Consider the statement : Percent_profit := (profit * 100) / cost_price; Lexical analysis identifies : :=, *, / as operators 100 as constant Others as identifiers Syntax analysis identifies: Statement as an assignment statement with percent_profit on LHS and (profit * 100) / cost_price; on RHS. Semantic analysis identifies: Meaning of the statement is profit * 100/cost_price and assign it to percent_profit

Synthesis Phase The phase is concerned with the construction of target language statement, which have the same meaning as a source statement.

Consist of 2 activities: -Creation of data structures in the target program = memory allocation -Generation of target code = code generation

Phases and es of language processor Language Processor

Analysis Phase

Synthesis Phase

Source Program

Target Program

Errors

Errors

-It is not feasible to analyse a source statement immediately followed by synthesis of eqnt target statements. -Because : - Forward Reference (Definition ): A forward reference of a program entity is a reference to the entity which precedes its definition in the program. - Example: Defn of variable is given before declaration of variable. - Issues concerning memory reqnt & organization of a language processor. Language Processor (Definition): A language Processor is the processing of every statement in a SP, or its equivalent representation, to perform a language processing function.

Intermediate representation of program Intermediate Representation (IR) Definition: An IR is a representation of a sp which reflects the effect of some, but not all, analysis and synthesis tasks performed during language processing. Diff betn target program & IR

Front End and Back End in IR: First performs analysis of SP and reflects its results in the IR. Called Front End Second reads and analyses the IR, instead of the SP, to perform synthesis of TP. Called Back End.

Source Program

Front End

Back End IR

Its useful because it doesn’t need to analyse sp multiple times

Target Program

Intermediate representation of program contd.. E.g. Front end of a Toy compiler performs 1. Lexical analysis 2. Syntax analysis 3. Semantic analysis O/P of front end is IR IR consist of 1. Table of Information - Table contains info obtained during different analyses of SP. - Most Imp table is Symbol table, which contains info of all identifiers. 2. Intermediate Code (IC) which is description of SP. - The IC is a sequence of IC units, each IC unit representing the meaning of one action in SP.

Example of IR: i : integer; a, b : real; a := b+i;

Symbol table : Id

Symbol

Type

1

i

int

2

a

Real

3

b

Real

4

i*

Real

5

temp

real

Length

address

Intermediate Code 1. Convert (Id, #1) to real, giving (Id, #4) 2. Add (Id, #4) to (Id, #3), giving (Id, #5) 3. Store (Id, #5) in (Id, #2)

Lexical Analysis (Scanning) -Lexical analysis identifies the lexical units in a source statement. - Then classifies the units into different lexical classes. E.g. id’s, constants, reserved id’s etc. and enters them into different tables. - Lexical analysis builds a descriptor, called a token, for each lexical unit. - A token contains two fields – class code, number in class. -E.g. Statement a := b + I; is represented as the strings of token id #2

Op #5

Id #3

Op #3

Id #1

Op #10

Syntax analysis (Parsing) Syntax analysis processes the string of tokens built by lexical analysis to determine the statement class . Eg. Assignment statement, if statement etc. -Then builds IC to represent the structure of the statements. - IC is ed to semantic analysis to determine the meaning of statement. -Example -IC for the statement a,b : real; a := b+i; IC in the form of Abstract Syntax Tree Example:

Semantic Analysis -IC from Syntax analysis is ed to Semantic analysis to determine the meaning of the statement. -Example:

Back End -Back end performs memory allocation and code generation.

-Memory allocation -Memory allocation is a simple task given the presence of the symbol table. - Memory reqnt of an identifier is computed from its type, length and dimensionality, and memory is allocated to it. - Address of memory is entered into symbol table. Symbol

Type

Length

address

1

i

Int

2000

2

a

Real

2001

3

b

Real

2002

Back end continue… Code generation Important issues in code generation: 1. 2. 3.

Place where the intermediate results should be kept i.e. in memory or in Which instruction should be used to conversion operations. Which addressing modes should be used for accessing variables.

Language Processor Development Tools (LPDT) -LPDT focus on generation of the analysis phase of the language processors. - The LPDT requires the following 2 inputs: 1. Specification of a grammar of language L 2. Specification of semantic actions to be performed in the analysis phase. LPDTs widely used in practice 1. LEX – lexical analyzer 2. YACC – parser generator Input to LPDT -Specification of the lexical and syntactic constructs of L - Semantic actions to be performed on recognizing the constructs - The specification consists of a set of translation rules of the form C code <string specification> (<semantic actions>) -LEX and YACC Generates C programs which contain the code for scanning and parsing respectively. - A YACC generated parser can use LEX generated scanner as a routine if the scanner and parser use same conventions concerning the representation of tokens.

Source program in L

Lexical specification LEX Scanner

Syntax specification

IR1 YACC Parser

Specification of L

IR / Target Code Using LEX and YACC