Context-free Grammar

Word categories


CFG = Context-Free Grammar = Phrase Structure Grammar = BNF = Backus-Naur Form

Context-free grammar

G = <T,N, S,R> • T is set of terminals (lexicon) • N is set of non-terminals For NLP, we usually distinguish out a set P  N of preterminals which always rewrite as terminals. • S is start symbol (one of the nonterminals) • R is rules/productions of the form X ! , where X is a nonterminal and is a sequence of terminals and nonterminals (may be empty). • A grammar G generates a language L.