Formal Languages and Compiler Design by Simona Motogna - Overview

Slide Note

This content provides an in-depth look into the course "Formal Languages and Compiler Design" by Simona Motogna. Covering topics such as compiler design, organization issues, history of programming languages, structure of a compiler, scanning techniques, and more. It also delves into the components of a compiler, including lexical analysis, parsing, semantic analysis, syntax trees, code generation, and optimization. The course structure, including seminars and laboratory requirements, along with the grading system, is highlighted. Simona Motogna's insights and the importance of understanding compilers in the field of computer science are emphasized.

vanvliet_h Follow

Uploaded on Sep 28, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Formal languages and Compiler Design Simona Motogna S. Motogna - LFTC

Why Why? ? Compiler Design Formal Languages FLCD S. Motogna - LFTC

Organization Issues Course 2 h/ week Seminar 1h/week Laboratory - 1h/week 5 presences seminar 6 presences - lab PRESENCE IS MANDATORY S. Motogna - LFTC

Organization Issues Final grade = 70% written exam + 20% lab + 10% seminar Lab: Seminar: - all laboratory assignments are mandatory - delays NO more than 2 weeks - solved problems, answers (blackboard), homeworks S. Motogna - LFTC

References See fi a disciplinei S. Motogna - LFTC

What is a compiler? Interpreter? Object code / program Source code / program Compiler Assembler? S. Motogna - LFTC

A little bit of history Java 1995 C 1969 - 1973 J. Gosling Pascal 1968 - 1970 D. Ritchie Lisp 1962 N. Wirth McCarthy Fortran 1954-1957 Backus S. Motogna - LFTC

Structure of a compiler analysis Error handling Source code/ program Scanning (lexical analysis) Parsing (syntactical analysis) tokens Semantic analysis Syntax tree Intermediary code generation synthesis Adnotated syntax tree Intermediary code optimization Symbol Table management Intermediary code Object code / program Object code generation Optimized intermediary code S. Motogna - LFTC

Chapter 1. Scanning Definition = treats the source program as a sequence of characters, detect lexical tokens, classify and codify them INPUT: source program OUTPUT: PIF + ST Algorithm Scanning v1 While (not(eof)) do detect(token); classify(token); codify(token); End_while S. Motogna - LFTC

Detect I am a student. - Separators => Remark 1) + 2) if (x==y) {x=y+2} - Look-ahead => Remark 3) S. Motogna - LFTC

Classify Classes of tokens: Identifiers Constants Reserved words (keywords) Separators Operators If a token can NOT be classified => LEXICAL ERROR S. Motogna - LFTC

Codify Codification table Identifier, constant => Symbol Table (ST) PIF = Program Internal Form = array of pairs Token replaced by pair (code, position in ST) identifier, constant S. Motogna - LFTC

Algorithm Scanning v2 While (not(eof)) do detect(token); iftoken is reserved word OR operator OR separator then genFIP(code, 0) else if token is identifier OR constant then index = pos(token, ST); genFIP(code, index) elsemessage Lexical error endif endif endwhile S. Motogna - LFTC

Remarks: genFIP = adds a pair (code, position) to PIF Pos(token,ST) searches token in symbol table ST; if found then return position; if not found insert in SR and return position Order of classification (reserved word, then identifier) If-then-else imbricate => detect error if a token cannot be classified S. Motogna - LFTC

Symbol Table Definition = contains all information collected during compiling regarding the symbolic names from the source program identifiers, constants, etc. Variants: table) - Unique symbol table contains all symbolic names - distinct symbol tables: IT (identifiers table) + CT (constants S. Motogna - LFTC

ST organization Remark: search and insert 1. Unsorted table in order of detection in source code 2. Sorted table: alphabetic (numeric) 3. Binary search tree (balanced) 4. Hash table O(n) O(lg n) O(lg n) O(1) S. Motogna - LFTC

Hash table K = set of keys (symbolic names) A = set of positions (|A| = m; m prime number) h: K A h(k) = (val(k) mod m) + 1 Conflicts: k1 k2 , h(k1) = h(k2) S. Motogna - LFTC