Exhaustive Study Notes on Compilers and Compilation pt2

Overview of the Compilation Process

• Definition of Compilation: Compilation is the process of translating a source program into a target program, such as machine code or assembly.

• Phases of Compilation:

  • Lexical Analysis (Tokenization): Converts the sequence of characters in the source program into logically cohesive lexical units.

  • Syntax Analysis (Parsing): Transforms these lexical units into hierarchical parse trees that represent the syntactic structure of the program.

  • Semantic Analysis: Analyzes the meaning of the program and generates intermediate code.

  • Code Generation: Produces the final machine code.

• Detailed Stages of a Compiler:

  • Lexical Analysis (Scanner): First stage of scanning.

  • Syntax Analysis (Parser): Structural verification.

  • Semantic Analysis: Meaning verification.

  • Intermediate Code Generation: Creating a machine-independent version of the logic.

  • Machine-Independent Code Improvement (Optional): Optimization before hardware considerations.

  • Target Code Generation: Assembly or machine code production.

  • Machine-Specific Code Improvement (Optional): Hardware-specific optimization.

Lexical Analysis (The Scanner)

• Primary Function: To recognize the "tokens" of a program by scanning source code from left-to-right, character-by-character. It groups these characters into lexemes (sequences matching a pattern).

• Tokens: The smallest meaningful units in a programming language, treated as single, indivisible entities for translation.

• Categories of Tokens:

  • Keywords: if, while, return.

  • Operators: +, *, <=, ||.

  • Identifiers: Names of variables, arrays, procedures, classes (e.g., i, count, sum).

  • Numbers: 12, 3.14, $7.2 \times 10^{-2}$.

  • Separators: }, (, ;.

  • Literals: true, $6.02 \times 10^{23}$, "music".

  • Comments: /* ... */, // ....

• Example Analysis: The expression x = a + b * 2; yields:

  • [(identifier, x), (operator, =), (identifier, a), (operator, +), (identifier, b), (operator, *), (literal, 2), (separator, ;)].

• Core Tasks:

  • Identify lexical units in a source statement.

  • Classify units into lexical classes and enter them into symbol tables.

  • Build a descriptor (token) for each unit.

  • Ignore whitespace and comments.

  • Detect tokens that are invalid according to language rules.

• The Digital Perspective: How the computer sees a line like sum = sum + a[i];:

  • tab, s, u, m, blank, =, blank, s, u, m, blank, +, blank, a, [, i, ], ;.

• Lexical Analysis Process:

  1. Discard blanks and tabs to find the start of a token.

  2. Group characters together.

  3. Continue until the end of the token.

  4. Classify and save the token.

  5. Repeat until the end of the statement/source code.

Formal Language Definitions

• Alphabet (\Sigma): A finite, non-empty set of symbols.

• String/Word: A finite concatenation of symbols from $\Sigma$.

• Length of a string ($|w|$): The number of characters in string $w$.

• Empty String ($\epsilon$): A string with length $|\epsilon| = 0$.

• Concatenation ($x^n$): A symbol or word $x$ concatenated with itself $n$ times; $x^0$ denotes $\epsilon$.

• Language ($L$): A set such that $L \subseteq \Sigma^*$, where $\Sigma^*$ is the set of all possible strings over $\Sigma$.

• Equality: Two languages are equal if they are equal as sets.

Regular Expressions (RegEx)

• Purpose: RegExes specify patterns to identify valid tokens in a language. The grammar defined by RegExes is called Regular Grammar, and the language defined is Regular Language.

• Operations on Languages:

  • Union: $L \cup M = \{s \mid s \text{ is in } L \text{ or } s \text{ is in } M\}$. Notation: (r)|(s).

  • Concatenation: $LM = \{st \mid s \text{ is in } L \text{ and } t \text{ is in } M\}$. Notation: (r)(s).

  • Kleene Closure: $L^*$ indicates zero or more occurrences of $L$. Notation: (r)*.

• Precedence and Associativity:

  • Operations are left-associative.

  • 1st Precedence: * (highest).

  • 2nd Precedence: Concatenation (.).

  • 3rd Precedence: Pipe sign | (lowest).

• RegEx Symbols:

  • x*: Zero or more occurrences: $\epsilon, x, xx, xxx, ...$

  • x+: One or more occurrences ($x . x^*$).

  • x?: At most one occurrence ($x \text{ or } \epsilon$).

  • [a-z]: Lower-case alphabets.

  • [A-Z]: Upper-case alphabets.

  • [0-9]: Natural digits.

• Common Token Regex Representations:

  • letter = [a-z] | [A-Z]

  • digit = [0-9]

  • sign = [+ | -]

  • Decimal = (sign)?(digit)+

  • Identifier = (letter)(letter | digit)*

Advanced RegEx Extensions (Lex Syntax)

• [abc]: Matches a, b, or c.

• [^abc]: Negation; matches any character except a, b, or c.

• . (Dot): Matches any character except the newline ([\text{^}\backslash n]).

• "[: Using double quotes makes metacharacters plain characters.

• \[: Using a backslash makes a metacharacter plain.

• Regular Definitions (Macros): Defining symbols to be used in other RegExes (e.g., {Letter}({Letter}|{Digit})*). Recursion is not permitted in regular definitions.

Finite Automata (FA)

• Definition: The simplest abstract machine used for pattern recognition, consisting of states and transitions based on input symbols. It consists of five tuples: Input, Output, States, State relation, and Output relation.

• Deterministic Finite Automata (DFA):

  • For any input character from a given state, there is exactly one transition to a single state.

  • No null ($\epsilon$ ) moves are allowed.

  • Components: A set of states $S$, an alphabet $\Sigma$, a transition function $\delta : S \times \Sigma \rightarrow S$, a start state $s_0$, and a set of final states $F$.

• DFA Simulation Algorithm: state = s0; char = get_next_char(); while (char != EOF) { state = delta(state, char); char = get_next_char(); } if (state in Final) report acceptance; else report failure;     

• Longest Accepted Prefix: A variation of the algorithm where the simulator records the last state that was in the "Final" set to return the longest valid token (e.g., if input is R17R, it returns R17 if R17 was the longest accepted string).

Syntax Analysis (The Parser)

• Goal: To group token sequences into phrases based on the rules of the source language.

• Operations:

  • Obtain tokens from the Lexical Analyzer.

  • Check for syntactic correctness.

  • Report syntax errors.

  • Determine statement class (e.g., assignment, condition).

  • Construct parse trees.

• Grammars:

  • Ambiguity: A grammar is ambiguous if it can generate more than one parse tree for the same string (e.g., abab in simple grammars). Programming languages should be unambiguous.

  • Terminals: The actual tokens of the language.

  • Non-Terminals: Intermediate grammatical categories (e.g., <while statement>, <block>).

• Examples:

  • The statement b = a + 7 results in a tree where = is the root, b is the left child, and an expression a + 7 is the right child.

  • Expression Evaluation for ((7+3)*(5-2)): Includes specific rules involving descending to children on ( and returning to parents on ).

Recursive Descent Parsing

• Mechanism: A top-down parser built from context-free grammar where each non-terminal is implemented as a function. It uses "Match" for terminals and "Call" for non-terminals.

• Advantages: Exceptionally simple; easy to construct from recognizers; builds parse trees logic directly into the program.

• Disadvantages: Slower than other methods; difficult to provide high-quality error messages; cannot handle grammars requiring arbitrarily long look-aheads.

• Stack Implementation: Methods take tokens, build a tree, and push the tree onto a global stack last in first out (LIFO). Successful methods leave exactly one result on the stack.

• While Statement Example:

  1. Tokenizer returns while token.

  2. while becomes a tree node on the stack.

  3. Condition parser adds <condition> to the stack.

  4. Block parser adds <block> to stack.

  5. makeTree(3, 2, 1) pops the top three items and assembles them into a subtree with while as the root.

Compiler Component Generators

• flex (Fast Lexical Analyzer Generator):

  • Generates scanners based on pairs of Regular Expressions and C code.

  • Output: lex.yy.c which defines yylex().

  • Requires compilation and linking with the -lfl library.

• yacc (Yet Another Compiler-Compiler):

  • A tool for describing the input structure (grammar) of a program.

  • Turns a specification into a subroutine that handles the input process.

  • Output: y.tab.c.

• Example: Desk Calculator: To create a calculator:

  1. Create desk.l (flex) and desk.y (yacc).

  2. Run flex desk.l and yacc desk.y.

  3. Add function prototypes int yylex(void); and void yyerror(const char *); to y.tab.c.

  4. Compile: gcc y.tab.c -ly -lfl.

  5. Executes mathematical operations like 1.2*(3.4+5.6) to return results (e.g., 10.8).