Lexical and Syntax Analysis Notes

Lexical and Syntax Analysis

Lexical Analysis

  • Definition:

    • Lexical analysis reads the source code from left to right, organizing characters into tokens.
    • The goal is to break down input code into meaningful elements (tokens) for easier computer understanding.
    • Eliminates comments and whitespace.

  • Process:

    • Input Preprocessing: Cleans the input text by removing comments, whitespaces, and unnecessary characters.
    • Tokenization: Breaks the input text into tokens by matching characters against definitions in regular expressions.
    • Token Classification: Identifies different types of tokens such as keywords, identifiers, operators, and punctuation.
    • Token Validation: Checks the validity of tokens according to programming language rules (e.g., valid identifier names).
    • Output Generation: Produces a token stream as the output for the next stage of compilation.

  • Tokens: Defined as individual words or symbols. Examples:

    • Alphabets: Hexadecimal characters.
    • Strings: Continuous sequences of characters (e.g., 'STIisthebest' has 12 characters).
    • Symbols: Special characters used in high-level programming languages (e.g., +, -, *, =, ==).
    • Non-tokens: Include comments and blank spaces.

  • Lexemes: The character sequences classified as tokens, which are recognized through patterns.

  • Example:

    • For the assignment statement: result = oldsum - value / 50;
    • Tokens and Lexemes:
    • IDENT: result
    • ASSIGN_OP: =
    • IDENT: oldsum
    • SUB_OP: -
    • IDENT: value
    • DIV_OP: /
    • INT_LIT: 50
    • SEMICOLON: ;

Interaction with Syntax Analysis

  • Parsing/Syntax Analysis:

    • Analyzes tokens to ensure they follow the grammar of the programming language.
    • Identifies syntax errors in code, requiring correction before compilation.
    • Outputs a parse tree or Abstract Syntax Tree (AST) representing program structure.

  • Important Concepts:

    • Context-Free Grammar (CFG): Used to define syntax rules to validate token streams during syntax analysis.
    • Error Handling: Syntax analyzers flag syntax errors and provide location feedback.
    • Symbol Table Creation: Stores information about the identifiers used in the program, such as type and scope.

Derivation Process

  • Derivation: The application of CFG rules to generate valid structures.

    • Decisions include selecting non-terminals and corresponding production rules.
    • Two methods: Left-most and Right-most derivation.

  • Parse Tree:

    • A graphical representation showing how strings are derived using grammatical rules.
    • Leaf nodes represent terminals; interior nodes represent non-terminals. The tree structure reflects operator precedence and associativity.

Ambiguity and Associativity

  • Ambiguity: Occurs when a grammar produces multiple parse trees for a single string. Firms need methods to remove or manage ambiguity.

    • Solutions: Rewrite grammar or establish operator precedence and associativity.

  • Associativity: Determines the order of operations between operators.

    • Left-Associative Operations: Evaluated from left to right (e.g., addition, multiplication).
    • Right-Associative Operations: Evaluated from right to left (e.g., exponentiation).

Precedence of Operators

  • Operator Precedence: Dictates which operator takes effect first when two operators share a common operand.

    • Example: In the expression 2 + 3 * 4, multiplication takes precedence over addition, leading to the interpretation: 2 + (3 * 4).

  • Priority Table of Operators in Python:

    1. ** (Exponentiation)
    2. Unary +, -
    3. *, /, //, %
    4. +, -

References

  • Geeks for Geeks. (2024). Introduction to syntax analysis in compiler design.
  • Sebesta, R. (2019). Concepts of programming languages.
  • TutorialsPoint. (2024). Compiler design – Syntax analysis.