Formal Languages and Compiler Design by Simona Motogna - Overview

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.

• Formal Languages
• Compiler Design
• Simona Motogna
• Course Overview
• Programming Languages

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.

Presentation Transcript

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

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

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

4. 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

5. References See fi a disciplinei S. Motogna - LFTC

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

7. 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

8. 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

9. 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

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

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

12. 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

13. 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

14. 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

15. 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

16. 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

17. 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

18. Visibility domain (scope) Each scope separate ST Structure -> inclusion tree S. Motogna - LFTC