Compilers and Compilation Study Guide

Overview of Compilers and Compilation

  • Definition of a Compiler: A compiler is a piece of system software that translates high-level programming languages into machine language (10000010010110100100101…10000010010110100100101\dots).

  • Necessity: Computers can only understand machine language; therefore, all high-level language instructions must be translated prior to execution.

  • Compilation Process: This is a process that translates a program from a source language (typically a high-level, problem-oriented language) into an equivalent program in an object or target language (typically a machine-oriented language like machine code or assembly).

  • Abstract to Low-Level: Compilation serves as the vital link between the abstract world of application development and the low-level world of application execution on physical machines.

  • Error Detection: The most important part of compilation is the detection and reporting of errors.

  • Translation Example:

    • Source snippet: while (c !='x') { if (c == 'a' || c == 'e' || c == 'i') printf("Congrats!"); else if (c!='x') printf("Sorry!"); }

    • Result: Machine language bitstream and the executable program prog.

Types of Translators and Relationship with Interpreters

  • Assembler: A type of translator that specifically handles assembly language.

  • Interpreter: Closely related to the compiler but differs in execution.

    • Functionality: It takes both the source program and input data simultaneously.

    • Phase Symmetry: The translation and execution phases of the source program occur at the same time.

    • Advantages: Easier implementation of programs; run-time errors are displayed immediately.

    • Disadvantages: Slower execution compared to compiled code; often requires more memory space.

The Program Compilation Pipeline

  • Step-by-Step Flow:

    1. Skeletal Source Program: The initial code including headers (.c.c source).

    2. Preprocessor (CPP): Produces the Source Program (.i.i source).

    3. Compiler: Translates the source into an Assembly Program (.s.s assembly).

    4. Assembler: Translates assembly into Relocatable Machine Code (.o.o object file).

    5. Linker/Load Editor: Combines object files with external libraries to create Absolute Machine Code (Executable).

  • File Extensions and Tools:

    • helloworld.c→helloworld.c \rightarrow Preprocessor →helloworld.i\rightarrow helloworld.i (Not explicitly named in all slides but common in gcc flow).

    • helloworld.i→helloworld.i \rightarrow Compiler →helloworld.s\rightarrow helloworld.s

    • helloworld.s→helloworld.s \rightarrow Assembler →helloworld.o\rightarrow helloworld.o

    • helloworld.o+Libraries→helloworld.o + \text{Libraries} \rightarrow Linker →a.out\rightarrow a.out (Executable).

The C Preprocessor (CPP)

  • Timing: Preprocessing occurs before a program is compiled.

  • Primary Functions:

    • Inclusion of other files.

    • Definition of symbolic constants and macros.

    • Conditional compilation of program code.

    • Conditional execution of preprocessor directives.

  • Format: All preprocessor directives begin with the # symbol. Only whitespace characters are permitted before a directive on a line.

  • The #include Directive:

    • #include <filename>: Searches the standard library for the file. Used for standard library files.

    • #include "filename": Searches the current directory first, then the standard library. Used for user-defined files.

    • Usage: Necessary for programs with multiple source files or header files containing common declarations (classes, structures, function prototypes).

  • The #define Directive: Symbolic Constants:

    • Format: #define identifier replacement-text.

    • Example: #define PI 3.14159.

    • Note: Everything to the right of the identifier replaces the text. For instance, #define PI = 3.14159 would replace PI with =3.14159= 3.14159.

    • Constants cannot be redefined once created.

  • The #define Directive: Macros:

    • Macros without arguments: Treated like symbolic constants.

    • Macros with arguments: Arguments are substituted into the replacement text during macro expansion.

    • Substitution Mechanics: Performs literal text substitution; no data type checking is performed.

    • Example: #define CIRCLE_AREA(r) (PI * (r) * (r)) used as area = CIRCLE_AREA(4); results in area = (3.14159 * (4) * (4));.

    • Importance of Parentheses: Without parentheses, #define CIRCLE_AREA(x) PI * (x) * (x) applied to CIRCLE_AREA(c + 2) would expand to 3.14159 * c + 2 * c + 2, which is mathematically incorrect due to operator precedence.

    • Multiple Arguments: #define RECTANGLE_AREA(x, y) ((x) * (y)) applied to RECTANGLE_AREA(a + 4, b + 7) expands to ((a + 4) * (b + 7)).

  • The #undef Directive: Used to undefine a symbolic constant or macro, allowing it to be redefined later.

Conditional Compilation

  • Purpose: To control preprocessor directives and the compilation process itself.

  • Constraints: Cast expressions, sizeof, and enumeration constants cannot be evaluated within preprocessor directives.

  • Structure: Similar to if statements in C.

    • #if !defined(NULL)

    • #define NULL 0

    • #endif

    • defined(NULL) evaluates to 11 if defined and 00 otherwise.

  • Shorthand Directives:

    • #ifdef: Short for #if defined(name).

    • #ifndef: Short for #if !defined(name).

  • Other Statements:

    • #elif: Equivalent to "else if".

    • #else: Equivalent to "else".

  • Commenting Out Code: Standard comments (/* ... */) cannot always be nested safely. Use #if 0 to comment out blocks of code. To enable the code again, change the 00 to a 11.

GCC (GNU Compiler Collection)

  • Standard: GCC is the standard Linux C compiler.

  • Stages and Flags:

    • gcc -E helloworld.c: Stop after preprocessing; send output to stdout.

    • gcc -S helloworld.c: Stop after the compilation stage (proper); output assembler code to helloworld.s.

    • gcc -c helloworld.c: Assemble source code but do not link; generates relocatable object file helloworld.o.

    • gcc helloworld.o: Build the default executable a.out.

    • gcc -o prog helloworld.c: Compile and link, naming the executable prog.

    • gcc -lm helloworld.o: Connect/link the math library.

    • gcc -g: Include debugging information for use with debuggers.

    • gcc -l<library_name>: Link with a specified external library.

  • Running the Program: Use ./hello to execute a compiled file named hello.

Compiler Components, Assembler, Linker, and Loader

  • Compiler Internal Parts:

    • Parser

    • Analyzer

    • Code Optimizer

    • Code Generation

  • Assembler Details:

    • Generates relocatable object code.

    • Contains metadata (label definitions referring to locations).

    • Includes "holes" (relocation entries) to be filled later with values of labels defined elsewhere.

    • Tools for inspecting object files: nm (e.g., nm example.o) and objdump (e.g., objdump -t example.o).

  • Linker Details:

    • Combines compiled and assembled object code with standard library functions.

    • Resolves references in object files to external variables and procedures in other files.

  • Loader Details:

    • Compilers/Linkers produce relocatable machine code (memory references relative to an undetermined starting location).

    • The loader calculates absolute addresses for these locations.

    • It amends the code to use these addresses, gets the starting address from the OS, and places the code into memory to execute.

Properties and Goals of a Compiler

  • Performance and Quality:

    • Correctness: The compiler must preserve the meaning of the input program; source and output must be equivalent.

    • Efficiency: Output programs should run fast. Optimizing compilers should produce code more efficient than the input.

    • Compiler Speed: The compiler itself should be fast; compile time should be proportional to code size.

  • Diagnostics: Should provide high-quality error messages for programming mistakes.

  • Interoperability: Must support separate compilation and work well with debuggers.

  • Correctness Example (Logic Avoidance):

    • Target: A=(B+C)−(D+E)A = (B + C) - (D + E).

    • Invalid Translation: LOAD B; ADD C; STORE B; LOAD D; ADD E; STORE D; LOAD B; SUBTRACT D; STORE A;.

    • This is incorrect because STORE B and STORE D modify variables that the high-level language did not intend to change.

  • Efficiency Example (Optimization):

    • Calculating Sum: sum = 0.0; for (i = 0; i < 50000; i++) sum = sum + (2.0 * x[i]);.

    • Optimized version: sum = 0.0; for (i = 0; i < 50000; i++) sum = sum + x[i]; sum = sum * 2.0;.

    • This produces 49,99949,999 fewer multiplication instructions.

Why Study Compilers?

  • Theoretical Foundations: Compilers embody Deterministic Finite Automata (DFAs), Deterministic Pushdown Automata (DPDAs), formal languages/grammars, and lattice theory.

  • Skill Development: Teaches advanced programming and software engineering skills.

  • Versatility: Techniques are useful in many applications (embedded languages, command-line interfaces, macros).

  • Modern Challenges: It is not a "solved problem." New programming languages and multicore architectures present constant new challenges.

  • Interface Gap: Compilers bridge the gap between high-level language (productivity, portability) and low-level machine details (instruction selection, addressing modes, pipelines, registers, and cache).

Syntax and Semantics of Language

  • Syntax: Refers to the structure of the language.

    • Usually defined via Context-Free Syntax using Context-Free Grammars (CFGs).

    • A CFG is a set of recursive rewriting rules used to generate patterns of strings.

    • Example: a = b + c is syntactically legal, while b + c = a is illegal.

  • Semantics: Refers to the meaning of the language.

    • Static Semantics: Rules checked at compile time (e.g., number and types of arguments in a function).

    • Runtime Semantics: Rules that can only be checked during program execution.

Practice Tasks and Solutions

  • Task I: Macro Expansion:

    • Given: #define SQUARE(x) x * x.

    • Question: What will SQUARE(3 + 1) expand to?

    • Answer: 3 + 1 * 3 + 1. This evaluates to 77 (due to operator precedence) instead of the intended 1616.

    • Fix: Use parentheses: #define SQUARE(x) ((x) * (x)).

  • Task II: Debug Code:

    • Question: How to compile debug code only if DEBUG_MODE is defined?

    • Answer: #ifdef DEBUG_MODE // Debug code here #endif.

  • Task III: Comparison Logic:

    • Question: How to check if symbolic constant MAX_SIZE is defined to 100100?

    • Answer: #if !defined(MAX_SIZE) #define MAX_SIZE 100 #endif.