Parser

A parser analyzes a sequence of tokens according to a grammar, determining its structure and often building a structured representation.

Context-free grammar: A formal grammar whose production rules replace a single nonterminal with a sequence of symbols. Its production rules specify which token sequences the parser accepts.
Lexical analysis: The process of converting a character sequence into tokens such as identifiers, operators, and keywords. It commonly supplies the token sequence that parsing analyzes.
Compiler: A program that translates source code into another representation or executable form. A compiler typically parses source code before analyzing or translating it.
Finite-state machine: A computational model with finitely many states and transitions determined by input symbols. Finite-state machines handle regular patterns, while parsers capture nested grammatical structure.
Abstract syntax tree: A tree representation of a program that records its syntactic structure while omitting many surface details. Many parsers turn recognized input into this structural representation.
Token: A categorized unit of input, such as an identifier, number, or punctuation mark. Tokens are the parser's immediate input symbols.
Interpreter: A program that executes instructions or source code, often without first producing a standalone executable. An interpreter commonly parses input before evaluating its structure.
Regular expression: A notation for describing patterns in strings, usually corresponding to regular languages. Regular expressions suit token patterns but generally cannot express recursively nested syntax.
Recursive descent parser: A top-down parser implemented as mutually recursive procedures, usually one for each grammar rule. It translates grammar rules directly into parsing procedures.
Grammar: A formal system of rules that defines valid sequences in a language. A parser uses grammar rules to decide how tokens may be grouped.

Linked from 6 pages