Languages and Compilation
12 articles · Last updated 2026-01-15
Contents
-
1
Notes
Nondeterministic Finite State Machines NFSM
Nondeterministic finite state machines allow multiple possible next states for an input, including epsilon transitions, but are equivalent to deterministic FSMs via subset construction.
-
2
Notes
Finite State Machine
A finite state machine, defined by states, alphabet, transitions, start and final states, recognizes exactly one regular language.
-
3
Notes
Regular Languages
Regular languages are recognized by finite state machines, described by regular expressions, and generated by regular grammars, with union, concatenation, and Kleene star operations.
-
4
Notes
Context-Free Language
Context-free grammars define context-free languages using production rules and parse trees, with pushdown automata as their recognizing machines, forming a superset of regular languages.
-
5
Notes
Turing Machine
Turing machines extend finite state machines with infinite memory, read-write capability, and bidirectional movement, enabling them to model all computable problems.
-
6
Notes
Lexical Analysis
Lexical analysis converts source code into tokens by removing whitespace and comments, using finite-state machines for efficient recognition and classification.
-
7
Notes
Syntactic Analysis
Syntactic analysis transforms token sequences into parse trees using grammar rules, employing top-down or bottom-up strategies evaluated on power, backtracking, lookahead, efficiency, and size.
-
8
Notes
FIRST & FOLLOW set
FIRST sets identify possible starting terminals of derivations, while FOLLOW sets determine terminals that may appear immediately after a non-terminal in parsing.
-
9
Notes
Bottom-Up Parsing
Bottom-up parsing constructs a syntax tree from input tokens by repeatedly reducing right-hand sides of grammar rules to their left-hand sides using a parse stack.
-
10
Notes
LR(0) Parsing
LR(0) parsing uses a state stack and action/goto tables to shift input symbols or reduce handles, determining whether to accept or report syntax errors.
-
11
Notes
Parsing Table
Explains how to construct LR(0) Action and Goto tables using items, closures, augmented grammar, and state transitions for parsing.
-
12
Notes
Symbol Table
A symbol table stores identifier information in a compiler, supporting declaration tracking, type checking, scope management, and efficient lookup for code generation.