Parsing

15 Nov 2017

Context-free Grammar

Word categories

• noun
• pronoun
• verb
• adjective
• adverb
• conjunction
• preposition
• interjection *

##

• word
• consituent phrases

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.