Introduction to compilers and lexical analysis notes — Unit 1

A compiler is a specialized software program that translates a program written in a high-level language (Source Language) into an equivalent program in a low-level language (Target Language), such as machine code or assembly.

⇒1.1 Key Responsibilities

• Translation: Converting source code to object code.
• Error Reporting: Detecting and reporting syntax and semantic errors to the user.
• Optimization: Making the target program run faster and consume less memory.

The translation process must be absolutely correct; a compiler must never change the meaning (semantics) of the original program.

Both translate high-level languages, but their approach is fundamentally different.

A compiler operates in phases. Each phase transforms the source program from one representation to another.

⇒3.1 The Front-End (Analysis Phase)

Depends only on the Source Language. It breaks up the source program into constituent pieces and creates an intermediate representation.

• 1. Lexical Analysis (Scanner)
• 2. Syntax Analysis (Parser)
• 3. Semantic Analysis
• 4. Intermediate Code Generation

⇒3.2 The Back-End (Synthesis Phase)

Depends on the Target Machine. It constructs the desired target program from the intermediate representation.

• 5. Code Optimization
• 6. Target Code Generation

These two components span across all phases of the compiler.

⇒4.1 The Symbol Table

A data structure containing a record for each identifier (variable name, function name) with fields for the attributes of the identifier (type, scope, memory location). Every phase interacts with the symbol table to insert or retrieve data.

⇒4.2 The Error Handler

Each phase can encounter errors. The error handler manages reporting these errors clearly and recovering from them (if possible) so the compiler can continue parsing the rest of the file to find further errors.

Lexical Analysis is the first phase of a compiler. Its main task is to read the input characters and produce as output a sequence of tokens that the parser uses for syntax analysis.

⇒5.1 Key Tasks

• Tokenization: Grouping characters into meaningful sequences called lexemes, and producing tokens.
• Stripping Whitespace: Removing blanks, tabs, and newline characters.
• Removing Comments: Stripping out comments (`//` or `/ ... /`) as they have no semantic meaning.
• Line Numbers: Tracking line numbers for error messages.

It is crucial to understand the difference between these three terms.

• Token: An abstract symbol representing a category (e.g., `IDENTIFIER`, `KEYWORD`, `OPERATOR`, `NUMBER`).
• Lexeme: The actual sequence of characters in the source code that matches the pattern for a token (e.g., `count`, `while`, `+`, `3.14`).
• Pattern: The rule describing the set of lexemes that can represent a particular token (usually defined using Regular Expressions).

Example: In the code `count = 10;`, the lexeme `count` maps to the token `<IDENTIFIER, pointer_to_symbol_table>`.

Regular expressions are used to define the Patterns for tokens. They are an exact algebraic notation for describing sets of strings.

⇒7.1 Basic Operations

• Union (`|`): `a | b` means 'a' or 'b'.
• Concatenation (`ab`): 'a' followed by 'b'.
• Kleene Closure (`*`): Zero or more occurrences. (e.g., `a*` matches empty string, 'a', 'aa', 'aaa').
• Positive Closure (`+`): One or more occurrences. (e.g., `a+` matches 'a', 'aa', but not the empty string).

Example (Identifier): `letter (letter | digit)*`

A Regular Expression describes a pattern mathematically, but to actually write code that recognizes it, we convert the RE into a Finite Automaton (a state machine).

⇒8.1 Types of FA

• NFA (Nondeterministic Finite Automaton): Can have multiple transitions for the same symbol from a state, and can have epsilon (`ε`) transitions (moving states without reading input). Easier to generate from an RE.
• DFA (Deterministic Finite Automaton): Exactly one transition for every symbol from every state. No epsilon transitions. Much faster to execute in code.

The standard pipeline is: RE -> NFA -> DFA -> Lexer Code.

Writing a lexer by hand using massive `switch` statements is tedious. Tools like Lex (or Flex) automate this process.

⇒9.1 How Lex Works

You provide a `.l` file containing Regular Expressions and corresponding C actions. Lex reads this file and automatically generates a C program (`lex.yy.c`) which contains a giant DFA implementation that returns tokens.

%%
"if"       { return IF; }
[a-z]+   { yylval = strdup(yytext); return IDENTIFIER; }
[0-9]+   { yylval = atoi(yytext); return NUMBER; }
[ \t\n]   { /* ignore whitespace */ }
%%

Reading characters one-by-one directly from the hard drive is incredibly slow. Lexical analyzers use input buffering techniques to speed this up.

⇒10.1 Two-Buffer Scheme

Two large memory buffers (e.g., 4KB each) are used. The lexer maintains two pointers: `lexemeBegin` and `forward`.

• The `forward` pointer scans ahead to find the end of the token.
• When the `forward` pointer hits the end of the first buffer, the OS asynchronously loads the next chunk of the file into the second buffer.
• Once a token is identified, a substring from `lexemeBegin` to `forward` is extracted, and `lexemeBegin` is moved forward.

Lexical errors are relatively rare because the Lexer just matches characters. It doesn't know about grammar.

⇒11.1 What causes a lexical error?

When the characters remaining in the input do not match any pattern defined for any token. For example, typing an illegal character like `@` in C code.

⇒11.2 Panic Mode Recovery

The simplest recovery strategy. The lexer deletes successive characters from the remaining input until it finds a well-formed token, prints an error message for the deleted characters, and continues.