Compilateurs et Interpréteurs

Compilation - Théorie des Langages

• This document is a compilation of study notes on compilation theory, for a second-year IUP (Licence Professionnelle) Information Engineering class at the University of Western Brittany.
• The document covers the theory and practical aspects of compilers, including their structure and various phases.
• The last revision date is January 29, 2003.

Table of Contents

• The document provides a detailed table of contents outlining the key topics covered, allowing for easy navigation and focused study.
• Specific subtopics include Introduction (compiler purpose, reasons for the course, and literature review), Compiler Structure (lexical, syntax, semantic analysis, code generation, and optimization phases), and specific tools like (f)lex and yacc/bison.
• Further subsections are detailed within each major topic, providing a well-structured overview.

Chapter 1: Introduction

• What is compilation? A compiler is a software tool translating high-level code into executable instructions.
• Why this course? Compilation is crucial in many software scenarios, going beyond simply translating high-level language to machine code. -It includes translation between high-level programming languages (Pascal to C, Java to C++).
• It also includes translation from low-level languages to high-level languages (recovering source code from compiled binaries).
• It spans the translation of programs written in any language to another.
• The general principles are applicable to data processing, search engines, text-processing tools like sed or awk, etc.
• Key takeaway Compilers and interpreters are different. Compilers generate a separate executable file, while interpreters execute instructions directly.

Chapter 2: Compiler Structure

• Analysis phase: Identifies variables, instructions, operators, and establishes the program's structure with semantic properties.
• Synthesis/Production phase: Creates the target code.
• Analysis phases: -Lexical analysis (scanning): groups characters into tokens (e.g., identifiers, keywords, operators) -Syntax analysis (parsing): checks if tokens are in the correct order and are structured according to the language rules -Semantic analysis: ensures that tokens form valid and meaningful constructs according to the language's semantics -Symbol table management: stores information about variables, types, and scopes.
• Production phases: -Code generation: translates the structured information into target machine instructions. -Code optimizations: improves the generated code for faster execution (e.g., eliminating redundant calculations).
• Parallel phases: -Simultaneous phases like table handling and error correction -Error handling: detects issues (syntax, semantic, or system) and informs the user.

Chapter 3: Lexical Analysis

• Lexical units/tokens: Groups of characters having a collective meaning (e.g., +, <, identifiers, keywords).
• Lexemes: Specific character sequences in the source code matching the pattern for a particular lexical unit. Example: identifiers or numbers.
• Regular expressions: Formal description technique for recognizing sequences within a given set of characters. This is used to specify patterns for lexical units.
• Lexical analysis implementation/lexical analysis tool: Techniques and tools to define and implement lexical analyzers (e.g., using (f)lex for practical implementation).

Chapter 4: Lexical Analysis Tool

• (f)lex: A tool generating lexical analyzers from regular expressions.
• Specifications (f)lex file contains regular expressions and corresponding actions.
• Variables and functions (e.g. yytext, yyleng, yylex, yywrap) are part of the (f)lex specification and tool.

Chapter 5: Syntax Analysis

• Grammatical structure: Languages have rules dictating how their structures should be formed.
• Grammer: Set of production rules specifying how symbols can be rearranged to form larger structures.
• Derivation trees: Abstract syntax trees representing the sequence of derivation steps from the starting symbol to the source code.
• Parsing methods: Two common methods for constructing derivation trees: -Top-down parsing (e.g., LL(1)): Starts with the starting symbol and applies rules downward. -Bottom-up parsing (e.g., LALR): Starts with the terminal tokens and works upward to the starting symbol.
• Tool yacc/bison A tool for generating syntax analyzers (parsers) from a grammar specification.

Chapter 6: Syntax Analysis Tool

• yacc/bison A tool generating syntax analyzers (parsers).
• Input Grammar specifications.
• Output A parser.
• Error handling, resolving conflicts (shift-reduce, reduce-reduce).
• Attribute values: Attaching values (integers, strings) to symbols.
• Communication with lexical analyzer: How the parser retrieves tokens through the yylval variable managed within the lexical analyzer that communicates to the parser.

Chapter 7: Language Theory - Automata

• Language Types: Classification of languages based on grammar types, with regular and context-free being a key subset.
• Automata: Formal models (e.g., finite automata with states and transitions) to describe how recognition of various tokens is made.
• Deterministic vs. non-deterministic automata: Different models of automata, with deterministic ones being more computationally efficient.
• Minimization and Construction of automata: techniques and algorithms to minimize the size of automata for efficiency.

Chapter 8: Semantic Analysis

• Semantic properties: Information a compiler needs to analyze beyond structure, concerning code meaning. -Meaningful code relies on proper variable scope definitions.
• Definition-directed parsing: Rules that allow connecting actions in productions to the grammar's construction. This enables calculating attribute values within each production.
• Different attribute kinds, such as:
• synthesized attributes: calculated "downward" or "bottom up" from the leaves to the root.
• inherited attributes: calculated "upward" or "top down" from the root toward the leaves.
• Scope of identifiers: The determination of a variable's valid region in the program.
• Type checking: Ensuring variables are used correctly (int variables used in functions expecting floats etc).

Chapter 9: Code Generation

• Execution environment: The way memory spaces are organized to properly store data (global data, locals, function calls etc).
• Code generation technique: Creating target machine instructions from the intermediate representation.
• Intermediate representation: A form of representation of the code (e.g., 3-address code) that's close to machine code but independent.
• Code optimization: Techniques to make the generated code faster without changing the output, by looking for ways to remove redundant or unnecessary operations.