Compiler Design Chapter 4

Lexical Analysis and Syntax Analysis

• Lexical analysis is separated from syntax analysis due to portability, simplicity, and efficiency considerations.

Top-Down Parsers

• Top-down parsers build a parse tree in a preorder fashion, visiting each node before its branches.
• They utilize leftmost derivation to construct the branches of the tree.

LL Algorithm

• The first 'L' stands for a left-to-right scan of the input.
• The second 'L' refers to generating a leftmost derivation.

Bottom-Up Parsers

• Bottom-up parsers construct a parse tree from the leaves upward to the root.
• This process involves reversing the right derivation to establish the tree structure.

Time Complexity

• Ambiguous grammars have a time complexity of O(n^3), indicating higher computational demand.
• Syntax analyzers and commercial compilers typically operate with a time complexity of O(n), ensuring efficiency.

Purpose of Top-Down Parser

• Top-down parsers focus on determining the correct A rule to formulate the next sentential form during leftmost derivation.

Left Derivation with Right Recursion

• It is false to assert that left derivation with right recursion is desirable; in practice, this approach is avoided.

Advantages of LR Parsers

• LR parsers can be constructed for all programming languages, offering versatility.
• They detect syntax errors earlier in a left-to-right scan.
• The LR grammar class is a proper superset of LL grammars, capable of handling left recursive grammars excluded from LL.

Direct Left Recursion Removal (Example: A → Aa | Abc | bc | d)

• Removed direct left recursion by introducing a secondary nonterminal A':
  • A → bcA' | dA'
  • A' → aA' | bcA' | ε

Direct Left Recursion Removal (Example: X → Xyy | Xz | Yx | w)

• Removed direct left recursion using new nonterminals X' and Y':
  • X → YxX' | wX'
  • X' → zX' | yyX' | ε
  • Y → zyY' | xY'
  • Y' → yY' | wY' | ε

Pairwise Disjointness Test

• For each grammar rule, the FIRST() function is calculated to determine if the left-hand side rule passes or fails pairwise disjointness:
  • a. S → aSb | bAA
    • Passes: FIRST(aSb) = {a}, FIRST(bAA) = {b}
  • b. A → b{aB} | a
    • Passes: FIRST(b{aB}) = {b}, FIRST(a) = {a}
  • c. B → aB | a
    • Fails: FIRST(aB) = {a}, FIRST(a) = {a}