Lexical Analysis and Parsing
1. Tokens, Patterns, Lexemes:
o Token: A logical unit, such as keywords, identifiers, operators.
o Pattern: A rule defining tokens, often expressed in regular
expressions.
o Lexeme: Actual text matching a token pattern.
2. Error Recovery in Lexical Analysis:
o Skipping invalid characters, inserting missing characters, and panic
mode recovery.
3. Why Buffering is Used:
o To optimize input operations by reducing the time required for reading
characters.
4. Transition Diagram for Identifier:
o A state diagram where transitions occur on valid identifier characters
(letters, digits after the first letter).
5. Prefix, Suffix, Proper Prefix, Proper Suffix Example:
o String: "abcd"
o Prefix: "ab", Proper Prefix: "abc"
o Suffix: "cd", Proper Suffix: "bcd"
6. Buffer Pair:
o Two buffers are used in lexical analysis for fast reading and sentinel
handling.
7. Interaction Between Lexical Analyzer and Parser:
o Lexical analyzer provides tokens to the parser; the parser requests and
processes tokens.
8. Parse Tree for -(id + id):
9. -
10. /
11. +
12. / \
13. id id
[Link] on Languages:
o Union, Intersection, Concatenation, Kleene Star.
[Link] of a Compiler:
Lexical Analysis, Syntax Analysis, Semantic Analysis, Intermediate Code
Generation, Optimization, Code Generation, Code Optimization.
Parsing Techniques
[Link] in Buffer Pairs:
They reduce the overhead of checking buffer limits.
[Link] Pruning:
A technique in bottom-up parsing for replacing a substring with a non-
terminal.
[Link]:
A component that performs syntax analysis by constructing parse trees.
[Link] Parsing:
Uses a lookahead token for making parsing decisions without backtracking.
[Link]-Down vs. Bottom-Up Parsing:
Top-Down: Constructs parse tree from the root (e.g., LL parsing).
Bottom-Up: Constructs parse tree from leaves (e.g., LR parsing).
[Link] Descent Parsing:
A top-down parsing method using recursive procedures for non-terminals.
[Link] Recovery in Predictive Parsing:
Panic mode, phrase-level recovery, and error productions.
[Link] for FOLLOW:
Initialize FOLLOW(S) for start symbol. Propagate FOLLOW sets iteratively.
[Link] Factoring:
Transforming grammar to remove common prefixes.
Example: A → αβ | αγ → A → αX, X → β | γ
[Link](1) Grammar:
A grammar where parsing decisions depend on a single lookahead symbol.
[Link] vs. Unambiguous Grammar:
Ambiguous: Multiple parse trees (e.g., S → aSb | bSa).
Unambiguous: Unique parse tree.
[Link] Parsing Advantages/Disadvantages:
Advantages: Handles wide classes of grammars.
Disadvantages: Complex tables, hard to implement.
[Link] Grammar:
Extends original grammar with new production rules.
[Link] in Parsing:
Shift-Reduce and Reduce-Reduce conflicts.
[Link]-Reduce Parsing Categories:
Simple LR (SLR), Canonical LR, Lookahead LR (LALR).
[Link]-Output Translator with YACC:
Define grammar rules and translation functions in the YACC file.
[Link] Parsing Actions:
Shift, Reduce, Accept, Error.
Semantic Analysis
[Link] Grammar Example:
Grammar S → aSbS | bSaS | ε is ambiguous.
[Link] Reference:
Occurs when a pointer references memory that has been deallocated.
[Link] of Recursion:
Direct, Indirect, Tail, Non-tail recursion.
[Link] Parsers Comparison:
SLR (simple), LALR (optimized), Canonical LR (complex but powerful).
[Link] of YACC File:
Sections for declarations, rules, and functions.
[Link] vs. YACC:
Lex generates lexical analyzers, YACC generates parsers.
[Link] for Type Checking:
Compatibility and coercion rules.
[Link] vs. Inherited Attributes:
Synthesized: Pass information upwards.
Inherited: Pass information downwards.
[Link] Parse Tree:
Parse tree with attributes for each node.
[Link] Checker:
Ensures type correctness in a program.
[Link] Tree:
:=
/ \
a +
/ \
* *
b -c b -c
[Link] Systems:
Framework defining rules for assigning types.
[Link] Checking Rule for Functions:
Ensure return types and argument types match.
[Link]-Directed Definition:
Associates semantic rules with grammar productions.
[Link] Representations:
Syntax tree, Postfix, Three-address code.
[Link]-Directed Definitions vs. Translation Schemes:
SDD has semantic rules; translation schemes interleave actions.
[Link] Expressions:
Represent types using type constructors.
[Link]-Address Statement Methods:
Quadruples, Triples, Indirect Triples.
46.S-Attribute vs. L-Attribute Definitions:
S-attributed use synthesized attributes; L-attributed use inherited attributes.
[Link] for a + b * c:
abc*+
[Link]-Address Code for Conditional:
if a < b
t1 = 1
else
t1 = 0
49.L-Attribute Rules Example:
Both given rules are L-attributed.
[Link] for Representing Syntax Tree:
Pointer-based, Array-based, String-based.
[Link]-Directed Definition for If-Else:
if_stmt → if expr then stmt else stmt
[Link] of Syntax-Directed Definition:
Attribute evaluation during parsing.
[Link]-Address Code for d=(a-b)+(a-c)+(a-c):
t1 = a - b
t2 = a - c
t3 = t1 + t2
t4 = t3 + t2
d = t4
[Link] Order of SDD:
Depth-first or dependency-based order.
[Link] Scheme:
Combines grammar rules with semantic actions.
[Link] Semantic Rules:
Attribute computation during syntax analysis.