CFG

CFG is an acronym that can denote more than one concept in computing. The two most common interpretations are context-free grammar, a formalism used to define programming languages and other formal languages, and a control flow graph, a representation of possible execution paths in a program. Both concepts are central to language design and program analysis, but they address different aspects of computation.

In context-free grammar (CFG), a grammar consists of a set of nonterminal symbols, a set of terminal symbols, a set of production rules, and a designated start symbol. Production rules have the form A -> α, where A is a nonterminal and α is a string of terminals and nonterminals. The grammar defines a context-free language as the set of strings that can be derived from the start symbol by repeatedly applying productions. CFGs underpin syntax definitions for many programming languages and natural languages, and they are categorized in the Chomsky hierarchy as Type-2 grammars. Parsers use CFGs to perform syntax analysis; common parsing techniques include top-down parsers (LL) and bottom-up parsers (LR, LALR). Grammars can be transformed into normal forms, such as Chomsky normal form, to facilitate parsing. A simple example is an expression grammar with rules for sums and products. Context-free grammars are not powerful enough to capture all languages; for example, {a^n b^n c^n | n ≥ 1} is not context-free.

In contrast, a control flow graph (CFG) represents the flow of control within a procedure or program. Its nodes (basic blocks) contain sequences of instructions with a single entry and exit point, and its directed edges indicate possible transfers of control between blocks (for example, following a conditional branch or a loop back to a top block). CFGs are used in compiler optimizations and static analysis to model how data and control propagate through a program. Common tasks include dead code elimination, data-flow analysis, loop optimization, and register allocation. CFGs are typically constructed on a per-procedure basis and can be extended to interprocedural graphs that span multiple functions.

In practice, the intended meaning of CFG is usually inferred from context. Context-free grammars are foundational for language specification and parsing, while control flow graphs are fundamental to program analysis and optimization.