Formal Grammar

Definitions

1. Formal Grammar is a set of production rules that precisely defines the syntax of a language by specifying how strings of symbols can be generated from a start symbol. In computer science, formal grammars are essential for defining programming language syntax and building parsers. The Chomsky hierarchy classifies grammars into four types with increasing generative power: Type 3 (regular grammars, recognized by finite automata), Type 2 (context-free grammars, recognized by pushdown automata), Type 1 (context-sensitive grammars), and Type 0 (unrestricted grammars, recognized by Turing machines). Context-free grammars (CFGs) are the most practically important, as they define the syntax of most programming languages. A CFG consists of terminal symbols (actual characters/tokens), non-terminal symbols (abstract categories), production rules, and a start symbol. Backus-Naur Form (BNF) and Extended BNF are standard notations for writing context-free grammars. Parser generators like Yacc, Bison, and ANTLR automatically create parsers from grammar specifications, making formal grammars an indispensable tool in language design and compiler construction.

   In plain English: The official rulebook for a language that says exactly which strings of symbols are valid. Programming language syntax is defined this way.

   Example: "We wrote a context-free grammar for the config DSL and generated the parser with ANTLR."

Related Terms

• Automata
• Type Theory
• Computability
• Decidability
• Haskell
• Lisp
• Prolog
• OCaml
• JIT Compiler
• Lookahead
• Object File
• Parse Tree
• Parser Combinator
• Parser Generator
• Regex Engine
• Scope Resolution