Lexical And Syntax Analysis 2

1. Automated Generation

2. State Transition Diagram

3. Table-Driven Appraoach

Approaches to Building a Lexer

Automated Generation

Use tools like lex to define token patterns.

State Transition Diagram (Manual Coding)

Design a finite automaton that tracks

character transitions.

Table-Driven Approach

Create a lookup table for state transitions.

state diagram

represents a finite automaton used for token recognition.

Character classes

simplify transitions:

Terminal Symbols

These are keywords, operators, or punctuation marks that cannot be broken down further.

Non Terminal Symbols

are like the branches of a tree—abstract structures built by combining terminals or other nonterminals

String of Terminals

is a valid sequence of these basic symbols.

Mixed Strings

combine terminals and nonterminals.

O(n3)

These algorithms operate with ________ time complexity which creates exponentially longer processing times according to the length of the input string.

O(n)

Parsing algorithms running inside modern compilers operate with a time

complexity that matches ____

factor

is the smallest unit of an arithmetic expression.