Turing Machines and Compiler Design Fundamentals

Introduction to Turing Machines (TM)

• Definition: A Turing Machine is an abstract machine that accepts languages generated by Type 0 grammars, also known as Unrestricted Grammars (UG).
• History: The concept was orignally invented in 1936 by Alan Turing.
• Language Hierarchy:
  • Unrestricted Grammar (UG): Generates Recursively Enumerable Languages (REL).
  • Recursively Enumerable Language (REL): A language that is accepted/recognized by a Turing Machine.
  • Context-Sensitive Grammar (CSG): Generates Context-Sensitive Languages (CSL).
  • Context-Free Grammar (CFG): Generates Context-Free Languages (CFL) accepted by Pushdown Automata (PDA).
  • Regular Grammar (RG): Generates Regular Languages (RL) accepted by Finite Automata (FA).

Model of a Turing Machine

• Components: The Turing Machine model consists of three primary components:
  1. Infinite Input Tape:
     • The tape is divided into a series of cells.
     • Each cell can hold exactly one symbol.
     • The symbols that make up the input string are initially placed on the tape; all other remaining cells hold the Blank symbol ($B$).
     • The tape is two-way, meaning it is infinite in both directions (or conceptually extending indefinitely from the input).
  2. Read/Write Head:
     • This component is capable of reading symbols from the input tape and writing symbols back to the tape.
     • It can move one cell at a time to the Left ($L$) or to the Right ($R$).
  3. Finite Control (FC):
     • The FC manages the actions performed by the machine.
     • It tracks the current state of the TM.
     • It makes decisions on where to move ($L$ or $R$) and what to write based on the current state and the symbol being read.

Formal Mathematical Definition

• 7-tuple System: A TM is formally defined as $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$.
  • $Q$: A finite set of states.
  • $\Sigma$: The input alphabet (the set of symbols allowed in the input string).
  • $\Gamma$: The set of symbols that can appear on the input tape ($\Sigma \subset \Gamma$).
  • $q_0$: The initial state ($q_0 \in Q$).
  • $B$: The Blank symbol ($B \in \Gamma$, but $B \notin \Sigma$).
  • $F$: The set of final or accepting states ($F \subseteq Q$).
  • $\delta$: The transition function.
• Transition Functions:
  • Deterministic TM (DTM): $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$.
  • Non-Deterministic TM (NTM): $\delta: Q \times \Gamma \rightarrow 2^{Q \times \Gamma \times \{L, R\}}$.
• Halting Conditions:
  • If a string $w \in L$, the machine halts in a final state.
  • If a string $w \notin L$, the machine either halts in a non-final state or loops infinitely (fails to halt).

Representations of Turing Machines

• Transition Table:
  • A tabular representation of the transition function $\delta$.
  • Columns: Represent the symbols on the input tape ($\Gamma$).
  • Rows: Represent the various states ($Q$).
  • Entries: Contain the next state, the symbol to be written, and the direction of movement.
  • Symbols: The start state is marked with an arrow ($\rightarrow$), and the accept/final state is marked with a star ($*$).
  • Undefined Entries: Specify that there is no transition defined; if the machine reaches an undefined entry (a "dead state"), it halts and rejects the input.
• Transition Diagram:
  • Consists of a set of nodes/circles representing states ($Q$).
  • Directed edges (arrows) represent transitions from one state to another.
  • The start state is indicated by an incoming arrow.
  • Final states are represented by double circles.
  • Edge Labels: Transitions are formatted as $(X, Y, D)$ where:
    • $X$ = Old tape symbol (the symbol being read).
    • $Y$ = New tape symbol (the symbol to be written).
    • $D$ = Direction of movement ($L$ or $R$).
• Instantaneous Description (ID):
  • A string used to represent the current configuration of the TM.
  • Format: $\alpha q \beta$, where $q$ is the current state and $\alpha\beta$ is the current content of the tape.
  • The Read/Write head is assumed to be pointing at the first symbol of the substring $\beta$.
  • An ID captures:
    1. Content of all cells from the leftmost non-blank symbol to the rightmost non-blank symbol.
    2. The cell currently being scanned.
    3. The current state of the machine.

Case Study: Construction for $L = \{a^n b^n \mid n \geq 1\}$

• Logic: The goal is to match an equal number of $a$'s and $b$'s.
  1. Read the leftmost $a$, change it to $X$, and move right looking for the leftmost $b$.
  2. Once a $b$ is found, change it to $Y$ and move left looking for the rightmost $X$.
  3. Move one cell to the right of $X$ to find the next $a$ and repeat the cycle.
  4. If for every $a$ there is a corresponding $b$, the machine will eventually see only $Y$'s and $B$'s (blanks).
  5. Reach the final state if symbols match perfectly.
• States Summary:
  • $q_0$: Look for an $a$ to replace with $X$.
  • $q_1$: Skip over $a$'s and $Y$'s moving right to find a $b$.
  • $q_2$: Skip over $a$'s and $Y$'s moving left to find an $X$.
  • $q_3$: Completion check (no move $a$'s left, looking for blanks).
  • $q_4$: Final State.
• Transition Function Example: $\delta(q_0, a) = (q_1, X, R)$.

Case Study: Construction for $L = \{a^n b^n c^n \mid n \geq 1\}$

• Logic Extension:
  1. Read $a$, write $X$, move right to find the first $b$.
  2. Read $b$, write $Y$, move right to find the first $c$.
  3. Read $c$, write $Z$, move left until the first $X$ is reached.
  4. Move right to find the next $a$ and repeat.
  5. If all characters are successfully replaced by $X, Y, Z$, the machine reaches an accepting state ($q_6$).
• Symbols: $\Gamma = \{a, b, c, X, Y, Z, B\}$.

Case Study: Palindrome Recognition

• Even Palindrome: $L = \{ww^R \mid w \in (a, b)^+\}$ (e.g., $abba$, $baab$).
  1. Read the leftmost symbol ($a$ or $b$) and replace it with a Blank ($B$).
  2. Move right to the end of the string (before the Blank).
  3. Check if the rightmost symbol matches the one replaced on the left.
  4. If they match, replace the rightmost character with $B$ and move left to repeat the process on the remaining string.
  5. If the tape becomes entirely blank, the string is accepted.
• Odd Palindrome: $L = \{wcw^R \mid w \in (a, b)^*\}$ (e.g., $abcba$).
  • The logic is similar, but the machine accounts for a middle pivot character ($c$).

Language Processing Systems

• Compiler Definition: A compiler is a language translator or program that translates a source language (typically high-level like C, Java, Fortran) into an equivalent target language (typically low-level machine code or assembly).
• Goals of Translation:
  1. Correctness: All valid programs must compile correctly.
  2. Performance: Minimizing the size of machine code and maximizing execution speed.
  3. Compile-Time Efficiency: How fast the compiler itself runs.
• Environment Components: Programs are often developed using a suite of tools:
  • Preprocessor: Produces input for the compiler. Functions include Macro processing (e.g., #define PI 3.14), File inclusion (#include <stdio.h>), Rational preprocessors, and Language extensions.
  • Assembler: Translates assembly language (mnemonics) into machine code (object program).
  • Linker: Combines several object files into a single program and resolves external references.
  • Loader: Reads relocatable machine code, alters addresses to fit current memory, and loads it into memory for execution.

Phases of a Compiler

The compilation process is divided into two main parts: Analysis (Front End) and Synthesis (Back End).

1. Lexical Analyzer (Scanner):
   • Reads the source program character by character.
   • Groups characters into meaningful sequences called Lexemes.
   • Outputs a stream of Tokens in the format <Token name, Attribute value>.
   • Removes comments and whitespace.
2. Syntax Analyzer (Parser):
   • Takes tokens as input.
   • Uses production rules (grammar) to create a tree-like representation called a Parse Tree or Abstract Syntax Tree.
   • Checks for grammatical errors.
3. Semantic Analyzer:
   • Checks the syntax tree for semantic correctness (meaning).
   • Performs Type Checking: Identifies type mismatches and handles conversions (e.g., inttoreal).
   • Ensures variables are declared before use and functions have proper arguments.
4. Intermediate Code Generator (ICG):
   • Produces a low-level or machine-independent representation of the source program.
   • Common forms: Three-address code (e.g., $t_1 = id_3 \times 60.0$).
5. Code Optimizer (CO):
   • Optional but highly beneficial phase.
   • Improves the code to run faster or use less power/space.
   • Technique examples: Loop optimization, removal of redundant computations, strength reduction.
6. Code Generator (CG):
   • The final phase that produces the target machine code (relocatable machine code or assembly).
   • Manages memory allocation and register assignments.

Lexical Analysis and Symbol Table

• Tokens vs. Lexemes:
  • Token: A syntactic category (e.g., Identifier, Constant, Keyword, Operator).
  • Lexeme: The actual sequence of characters (e.g., 100.01, counter).
• Symbol Table:
  • The primary data structure of the compiler.
  • Stores identifiers, their types, scopes, and memory addresses.
  • Interacts with all phases to facilitate searching and fetching.

Input Buffering

• Rationale: Reading from a hard disk character by character is time-consuming and expensive. Buffering stores a block of characters in memory to be scanned efficiently.
• Pointers:
  • Begin Pointer (bp): Points to the start of the current lexeme.
  • Forward Pointer (fp): Moves ahead to find the end of the lexeme.
• One Buffer Scheme:
  • Uses a single buffer to store input.
  • Problem: If a lexeme is longer than the buffer, the first part may be overwritten when the buffer is refilled.
• Two Buffer Scheme:
  • Uses two buffers scanned alternately.
  • When the fp reaches the end of the first buffer, the second is filled and scanned.
  • Sentinels: A special Character (eof) is placed at the end of each buffer to signal the boundary. This prevents the machine from checking the end of the buffer at every single character increment, improving speed.
• Pseudo-code for Buffer Navigation:
  • if forward at end of first half then reload second half; forward := forward + 1
  • else if forward at end of second half then reload first half; move forward to beginning of first half
  • else forward := forward + 1