UNIT 4: Compiler Design & Data Mining

I. COMPILER DESIGN (Primary Focus)

A. Compiler Fundamentals & Phases

A compiler translates source code to target machine code through a sequence of phases, each with a specific role. Separation of concerns (e.g., lexical vs. syntax analysis) simplifies design, improves modularity, and allows use of specialized tools.

Phases of a Compiler:

1. Lexical Analysis (Scanner): Reads input stream, groups characters into tokens (e.g., identifiers, keywords, operators), removes whitespace/comments. Output: stream of tokens.

2. Syntax Analysis (Parser): Organizes tokens into a hierarchical parse tree according to grammar rules. Checks syntactic correctness.

3. Semantic Analysis: Checks for semantic consistency (e.g., type checking, type coercion). Uses symbol table for type information.

4. Intermediate Code Generation (ICG): Produces a machine-independent intermediate representation (e.g., quadruples, triples).

5. Optimization: Improves intermediate code for efficiency (speed, size) without changing meaning. Can be local (basic block) or global.

6. Code Generation: Maps intermediate code to target machine code. Involves register allocation, instruction selection.

7. Symbol Table Management: Centralized database storing information about identifiers (name, type, scope, address).

8. Error Handling: Detects and reports errors (lexical, syntactic, semantic) with accurate location and description.

[!TIP] Exam Focus: Be prepared to list all 6-8 core phases and explain 2-3 in detail. The separation of lexical and syntax analysis is a frequent 7-mark question.

B. Lexical Analysis

Finite Automata (FA) are abstract machines used to recognize tokens. A Deterministic Finite Automaton (DFA) is constructed from regular expressions (token patterns). The DFA processes the input character-by-character, transitioning between states until it reaches an accepting state, signaling a token is found.

Example: For identifier regex [a-zA-Z][a-zA-Z0-9]*, a DFA starts in a start state, moves to a state on a letter, then loops on alphanumeric characters until a non-alphanumeric triggers token return.

LEX Tool: A lexer generator. User writes rules with regex patterns and associated C code actions. lex generates a lex.yy.c file containing a yylex() function that uses a DFA (from the regexes) to tokenize input.

Lex Program Example (Identifiers & Operators):

%{
#include "y.tab.h" /* Token definitions from parser */

%}

%%

"+"     { return PLUS; }

"-"     { return MINUS; }

"*"     { return MUL; }

"/"     { return DIV; }

"="     { return EQUAL; }

[a-zA-Z][a-zA-Z0-9]* { yylval = atoi(yytext); return ID; }

[ \t\n] ; /* Skip whitespace */

%%

The DFA built from these rules matches the longest possible regex. On a+b, it returns ID (for a), then PLUS, then ID (for b).

[!TIP] Common Pitfall: LEX uses maximal munch (longest match). If == and = are both rules, == must appear before = to be recognized correctly.

C. Syntax Analysis (Parsing)

Parsing Techniques Overview:

Operator Precedence Parsing: A simple bottom-up method for a subset of grammars (operator grammars). It uses precedence relations (<·, =·, ·>) between terminals to guide shifts and reduces. No need for a full parser stack; only operator stack. Example grammar: E → E+E | E*E | (E) | id. Relations: id <· +, + ·> id, + <· *, * ·> +, etc.

Bottom-Up Parsing (LR Family): All use a stack of grammar symbols and a parsing table with ACTION (shift/reduce/accept/error) and GOTO (state transition) entries.

1. SLR(1) Parsing:

   • Construct canonical collection of LR(0) items.

   • ACTION table: On (state_i, a), if item [A → α·aβ] exists → shift state_j. If item [A → α·] exists → reduce A→α for all a in FOLLOW(A).

   • SLR(1) Correctness Check: For any reduce entry [A→α·] in state i, FOLLOW(A) must not contain any terminal a that also causes a shift in that state. If conflict → not SLR(1).

2. LALR Parsing:

   • Constructs states by merging LR(1) items with same core (production and dot position) but different lookahead.

   • More powerful than SLR (resolves some conflicts) but less than full LR(1).

   • Comparison SLR vs LALR:

     • SLR: Uses FOLLOW set for reduce actions. May have spurious conflicts.

     • LALR: Uses precise lookaheads from merged LR(1) states. More accurate, fewer conflicts. Parser table size similar to SLR.

3. CLR(1) / LR(1) Parsing:

   • Uses full LR(1) items: [A → α·β, a] where a is lookahead.

   • Constructs canonical collection of LR(1) items (no merging).

   • Most powerful, but tables can be large.

   • Example Grammar 1: S → L = R | R, R → L, L → *R | id.

   • Example Grammar 2: E → E+T | T, T → T*F | F, F → (E) | id.

   • Construction Steps: (1) Augment grammar (S' → S). (2) Compute closure and goto for LR(1) items. (3) Build parsing table from final item sets.

Parse Trees & Ambiguity: Ambiguous grammar (e.g., E → E+E | E*E | E | a | b | c) allows multiple parse trees for a+b*c. To eliminate ambiguity, enforce precedence (* > +) and associativity (left). Create unambiguous grammar:

E → E + T | T

T → T * F | F

F → (E) | a | b | c

Now a+b*c has one parse tree: E(E(a) + T(T(b) * F(c))).

[!TIP] Exam Focus: Constructing CLR(1) tables for the two given grammars is a 14-mark question. Practice thoroughly. Know how to check SLR(1) correctness. Be able to disambiguate a grammar.

D. Syntax-Directed Translation (SDT)

Attribute Grammars: Augment grammar with attributes (values associated with grammar symbols) and semantic rules (computations on attributes).

• Synthesized Attributes: Values computed from children to parent (bottom-up).

• Inherited Attributes: Values computed from parent/siblings (top-down or left-to-right).

S-Attributed Definitions: All attributes are synthesized. Evaluated in a bottom-up manner during parsing. Example: Computing expression value.

E → E1 + T   { E.val = E1.val + T.val; }

E → T        { E.val = T.val; }

T → int      { T.val = int.lexval; }

L-Attributed Definitions: Attributes are either synthesized or inherited, but inherited attributes on the left side of a production can only depend on:

1. Parent's inherited attributes.

2. Sibling symbols to the left.

3. Own synthesized attributes.

Allows evaluation in a single left-to-right pass during bottom-up parsing (using a stack). Example: Type checking in a declaration list.

D → D1 ; L   { L.in = D1.out; }  // Inherited

D → int id   { D.out = id.type = int; } // Synthesized

Translation Schemes: SDT with embedded semantic actions placed within productions. For L-attributed grammars, actions can be placed to ensure left-to-right evaluation order (e.g., at right end of RHS for inherited attributes).

Case Statement Translation Scheme:

case E of

  c1: S1; ... cn: Sn;

esac

Scheme:

E → c1 : S1 { gen('if E.val == c1.val goto S1.next'); } 

   | E c2 : S2 { gen('else if E.val == c2.val goto S2.next'); }

   | ... 

   | else S { gen('else goto S.next'); }

[!TIP] Key Difference: S-attributed = only synthesized, bottom-up. L-attributed = synthesized + inherited (left-only), can be evaluated bottom-up with careful action placement.

E. Intermediate Code Generation (ICG)

Intermediate Forms:

1. Quadruples: 4-tuple (op, arg1, arg2, result). Easy to generate, but temporary names need symbol table.

   
   d = a-b + a-c + a-c
   
   ( -, a, b, t1 )
   
   ( -, a, c, t2 )
   
   ( +, t1, t2, t3 )
   
   ( -, a, c, t4 )
   
   ( +, t3, t4, d )
   
   

2. Triples: 3-tuple (op, arg1, arg2). No temporary names; refer to triples by number. Can have structural sharing issues.

   
   ( -, a, b )
   
   ( -, a, c )
   
   ( +, (1), (2) )
   
   ( -, a, c ) // Re-computed! Not same as (2)
   
   ( +, (3), (4) )
   
   d = (5)
   
   

3. Indirect Triples: A separate list of triples and a pointer list pointing to them. Allows easy reordering/optimization without changing references.

   
   Triple List:
   
   1: ( -, a, b )
   
   2: ( -, a, c )
   
   3: ( +, 1, 2 )
   
   4: ( -, a, c )
   
   5: ( +, 3, 4 )
   
   Pointer List for d: -> 5
   
   

Example: a + a*(b-c) + (b-c)*d

Quadruples:

t1 = b - c

t2 = a * t1

t3 = b - c   // Common subexp, not yet optimized

t4 = t3 * d

t5 = a + t2

d = t5 + t4

Dependency Graphs: Directed graph showing dependencies between statements (for optimization). Nodes = statements/expressions; edge i → j if j uses result of i. Used for:

• Common subexpression elimination: Find nodes computing same value.

• Dead code elimination: Nodes with no path to output.

• Ordering: Topological sort for evaluation order.

Backpatching: Technique for translating boolean expressions and control flow (if/while) where target addresses of jumps are unknown until later.

• Maintain lists of unresolved jump addresses (in quadruples).

• When target address becomes known, backpatch the list to that address.

• Example: if a < b then S1 else S2. Generate (j<, a, b, ?) and (j, _, _, ?). After parsing S1, backpatch first list to S1.code_start. After S2, backpatch second list to S2.code_start.

[!TIP] Exam Focus: Generating quadruples/triples for given expressions (like d = (a-b)+(a-c)+(a-c)) is a 7-mark question. Understand the difference between triples and indirect triples. Know backpatching for boolean expressions.

F. Symbol Table Management

Purpose: Store information about identifiers (name, type, scope, dimension, address, line number) for use by all compiler phases.

Data Structures:

[!TIP] Practical Choice: Hash tables are most common for speed. For scoped languages, a hash table per scope or BST with scope chains is used.

G. Runtime Storage Organization

Activation Record (AR) / Frame: Data structure for a single procedure/function call. Components (typical order, may vary):

1. Actual Parameters (passed by caller)

2. Return Address (where to continue after return)

3. Control Link (pointer to caller's AR)

4. Access Link (pointer to non-local data's AR, for nested scopes)

5. Saved Machine Status (registers)

6. Local Data (local variables, temporaries)

7. Returned Value (space for function result)

Storage Allocation Strategies:

[!TIP] Key Point: Stack for activation records (control flow), heap for dynamic objects (data with arbitrary lifetime).

H. Code Optimization

Basic Blocks & Flow Graphs:

• Basic Block: Sequence of statements with single entry (first statement) and single exit (last statement). No jumps inside except at end.

• Construction Algorithm:

  1. Identify leaders: first statement, any target of jump, any statement following a jump.

  2. Each leader starts a new block; block extends to next leader-1.

• Flow Graph: Nodes = basic blocks. Edge B1 → B2 if B1 ends with jump to B2's leader or B2 immediately follows B1 (fall-through).

Reducible vs. Non-Reducible Flow Graphs:

• Reducible: Can be reduced to a single node by repeatedly removing self-loops and edges to ancestors in the depth-first spanning tree. All structured programs (loops with single entry) are reducible. LR parsers require reducible graphs.

• Non-Reducible: Contains jumps into loops from outside (e.g., goto into middle of loop). Harder to analyze; may require iterative algorithms.

Optimization Techniques (with Example Context: for(i=0; i<N; i++) A[i] = B[i] * C + D;):

[!TIP] Loop Optimization Hierarchy: First do code motion (invariant code), then induction variable elimination, then strength reduction on remaining ops.

I. Specialized Topics & Miscellaneous

Bootstrapping: Process of using a simple compiler (written in machine code or another language) to compile a more advanced version of itself. Steps:

1. Write compiler C1 for language L in language L0 (simple).

2. Compile C1 with compiler C0 (for L0) → get executable C1.exe.

3. Rewrite compiler as C2 in L (more features).

4. Compile C2 using C1.exe → get C2.exe (self-hosting compiler).

Capabilities of Context-Free Grammars (CFG):

• Can Express: Nested structures (matching parentheses), recursion, most programming language constructs (if, while, expressions).

• Cannot Express: Context-sensitive features (e.g., variable must be declared before use, type consistency across distant statements). These require semantic analysis or more powerful grammars (indexed, attribute). Also cannot enforce "exactly one declaration" or "no duplicate parameters" purely with CFG.

FIRST and FOLLOW Sets:

• FIRST(α): Set of terminals that can begin any string derived from α. If α ⇒* ε, include ε.

• FOLLOW(A): Set of terminals that can appear immediately to the right of A in some sentential form. Include $ (end-of-input) if A can be at end.

• Computation Steps:

  1. Initialize: FIRST of terminals = themselves. FIRST of non-terminals empty. FOLLOW of start symbol = {$}.

  2. For each production A → α:

     • Add FIRST(α) \ {ε} to FIRST(A).

     • If ε ∈ FIRST(α), add FOLLOW(A) to FIRST(α).

     • For each symbol B in α until one without ε in its FIRST, add FIRST(next symbol) \ {ε} to FOLLOW(B). If all have ε, add FOLLOW(A) to FOLLOW(last B).

  3. Repeat until no changes.

II. DATA MINING (Secondary Focus)

A. Knowledge Discovery Process & Data Warehousing

KDD Process Steps:

1. Selection: Retrieve relevant data from database/data warehouse.

2. Preprocessing: Clean noise, handle missing values, resolve inconsistencies.

3. Transformation: Normalize, aggregate, construct attributes, reduce dimensionality.

4. Data Mining: Apply core algorithms (classification, clustering, association, etc.).

5. Interpretation/Evaluation: Interpret patterns/models, assess interestingness, visualize results.

OLAP (Online Analytical Processing):

• Purpose: Multidimensional analysis of summarized data (data warehouse).

• Types:

  | Type | Storage | Query Speed | Scalability | Example | | :--- | :--- | :--- | :--- | :--- | | MOLAP | Proprietary multidimensional array (cube). | Very fast. | Poor for high dimensions. | Microsoft Analysis Services. | | ROLAP | Relational tables (star/snowflake schema). | Slower (SQL joins). | Good for large data. | Oracle, SQL Server. | | HOLAP | Hybrid: aggregates in cube, detailed data in RDBMS. | Balanced. | Balanced. | SAP BW. |

• OLAP Operations:

  • Roll-up (Drill-up): Summarize data (e.g., city → country).

  • Drill-down: Go to finer detail (e.g., year → quarter → month).

  • Slice-and-dice: Select subset (e.g., fix time=2024, project product, sales).

  • Pivot (Rotate): Reorient cube (swap rows/columns).

Data Warehouse Schemas:

• Star Schema: Central fact table (foreign keys to dimensions, measures) surrounded by denormalized dimension tables.

• Snowflake Schema: Normalized dimensions (sub-dimensions). Reduces redundancy but increases join complexity.

• University Snowflake Example:

  
  Fact_Table (Student_Key, Course_Key, Semester_Key, Instructor_Key, count, avg_grade)
  
  ↓ FK ↓ FK ↓ FK ↓ FK
  
  Dim_Student (Student_Key, name, dept, ...)
  
  Dim_Course (Course_Key, title, credits, Dept_Key)
  
      ↓ FK
  
      Dim_Department (Dept_Key, dept_name, ...)
  
  Dim_Semester (Semester_Key, year, season, ...)
  
  Dim_Instructor (Instructor_Key, name, rank, ...)
  
  

  Measures: count (number of enrollments), avg_grade (stored at lowest level as actual grade; aggregated as average at higher levels).

B. Data Preprocessing

Data Transformation Strategies:

• Smoothing: Remove noise (binning, regression, clustering).

• Attribute Construction: Create new attributes from existing (e.g., area = length * width).

• Aggregation: Summarize data (e.g., daily sales → monthly sales).

• Normalization: Scale to small range (e.g., min-max to [0,1], z-score).

• Discretization: Convert continuous to categorical (e.g., age → youth/adult/senior).

• Concept Hierarchy Generation: Replace low-level values with higher-level concepts (e.g., city → state → country).

Handling Missing Values:

1. Ignore Tuple: Discard if many attributes missing. Not good if large % missing.

2. Fill with Global Constant: e.g., Unknown, 0. May distort statistics.

3. Fill with Mean/Median: For numerical; mode for categorical. Simple but reduces variance.

4. Regression/Prediction: Use other attributes to predict missing value (e.g., linear regression).

5. Imputation: Use most probable value from similar tuples (k-NN, hot-deck).

6. Treat as Special Value: Some algorithms can handle ? as separate category.

C. Association Rule Mining

Apriori Algorithm: Uses Apriori property: All non-empty subsets of a frequent itemset must also be frequent.

• Proof: Contrapositive. If some subset S of itemset I is not frequent (support(S) < min_sup), then any superset J ⊇ I cannot be frequent because support(J) ≤ support(S) < min_sup. Hence, I cannot be frequent.

• Algorithm Steps:

  1. C1 = all 1-itemsets. Scan DB, count support → L1 (frequent 1-itemsets).

  2. For k=2 while L_{k-1} ≠ ∅:

     • Ck = candidates from L_{k-1} (join step).

     • Prune Ck: remove any candidate with a (k-1)-subset not in L_{k-1}.

     • Scan DB, count support of Ck → Lk (frequent k-itemsets).

  3. Result = ∪ Lk.

  4. Generate rules from frequent itemsets: for each l ∈ Lk, for each non-empty subset s ⊂ l, rule s → (l-s) if confidence(s→l-s) ≥ min_conf.

Strong Association Rules with Negative Correlation:

• Support (P(A∩B)) and Confidence (P(B|A)) measure co-occurrence, not correlation.

• Example: A = {buy diapers}, B = {buy beer}.

  • Support(A→B) might be high (many buy both).

  • But P(B|not A) could be higher than P(B|A). Actually, P(A∩B) < P(A)*P(B) → negative correlation.

  • Why strong rule? Because P(B|A) is still high (many diaper buyers also buy beer), even if beer buyers are more likely to not buy diapers. Rule is useful for targeting diaper buyers with beer promotions.

D. Classification

Decision Tree Induction:

• Tree Pruning: Remove branches that fit noise (overfitting).

  • Pre-pruning: Stop early (e.g., max depth, min samples per leaf).

  • Post-pruning: Build full tree, then remove/replace subtrees (e.g., error-based pruning using validation set).

• Drawback of Separate Validation Set: Reduces training data size → may underfit. If dataset small, validation set may not be representative → pruning decisions biased.

E. Clustering & Outlier Detection

K-Means Clustering:

• Algorithm:

  1. Choose k initial centroids (randomly).

  2. Repeat until convergence:

     • Assign each point to nearest centroid.

     • Recompute centroids as mean of assigned points.

• Limitation (Global Optimum): Sensitive to initial centroids. May converge to local optimum.

  • Example: Two clusters, one large dense, one small sparse. Random init may place both centroids in dense cluster → small cluster never found. Objective function (within-cluster sum of squares) not minimized globally.

Clustering-Based Outlier Detection:

• Method: Cluster data at multiple granularities (e.g., using DBSCAN with different eps, or hierarchical clustering).

• Outliers are points that:

  • Belong to very small clusters.

  • Are far from any cluster centroid.

  • Are noise points in density-based clustering (DBSCAN).

• Finds outliers at different levels: point outlier (noise), cluster outlier (small cluster).

Semi-Supervised Outlier Detection:

• Advantage: Uses abundant unlabeled data to learn the "normal" behavior/model, while using limited labeled outliers to adjust decision boundary. More robust than purely supervised (which needs many labeled outliers) or unsupervised (which may miss subtle outliers).

F. Advanced Data Mining Topics

Web Mining: Application of data mining to web data.

• Web Content Mining: Mining text, images, audio on web pages (e.g., topic extraction).

• Web Structure Mining: Mining link structure (e.g., PageRank, hub/authority).

• Web Usage Mining: Mining user access logs (e.g., clickstream analysis, personalization).

Security Issues in Data Mining:

• Privacy: Mining personal data (medical, financial) without consent.

• Data Misuse: Using mined patterns for discrimination (e.g., insurance, hiring).

• Adversarial Attacks: Manipulating training data to poison model (data poisoning), or evading detection (evasion attacks).

• Regulatory Compliance: GDPR, HIPAA restrictions on data use.

Spatial and Temporal Mining:

• Spatial Mining: Patterns in geographic data.

  • Example: Finding hotspots of crime, predicting disease spread based on location.

• Temporal Mining: Patterns over time.

  • Example: Stock trend analysis, sales forecasting, detecting sequential patterns in user behavior (e.g., buy phone → buy case within 1 week).

[!TIP] Exam Focus: Data Mining questions are often definitional or example-based. Be ready to draw the snowflake schema for the university example. Know the Apriori proof and negative correlation example. For clustering, know the k-means limitation example and clustering-based outlier detection method.