Parsing

Parsing analyzes a string by applying a grammar’s rules to determine its structure. It can produce a tree or another representation of how the string’s parts relate.

Lexical analysis: Lexical analysis groups characters into tokens such as identifiers, numbers, and punctuation. Many parsers receive tokens produced by this preceding stage.
Formal grammar: A system of symbols and rules that specifies which strings belong to a language. Parsing tests strings against the rules that define a formal language.
Compiler: A program that translates source code into another form, often machine code or intermediate code. A compiler parses source syntax before analyzing meaning or generating output.
Semantic analysis: The analysis of whether a syntactically structured program obeys language rules about meaning and use. It follows parsing and checks constraints that grammar alone cannot express.
Context-free grammar: A formal grammar whose production rules replace one nonterminal symbol at a time. Its production rules describe structures that many parsers recognize.
Token: A discrete unit produced by lexical analysis, such as a keyword, identifier, or operator. Token-based parsers operate on these units rather than raw characters.
Parser generator: A tool that constructs a parser from a formal grammar specification. It automates parser implementation from grammar rules.
Interpretation: The execution of a program by directly carrying out its instructions. Parsing identifies program structure; interpretation gives that structure operational effect.
Parse tree: A tree that records how a string is derived from a grammar’s production rules. This is the explicit hierarchical structure a successful parse can produce.
Syntax: The rules governing how symbols combine into well-formed expressions in a language. Parsing determines whether an input conforms to a language’s syntax.

Linked from 12 pages