A context-free grammar G is described by four
parameters: N, Σ, R, S .


N a set of non-terminal symbols (or variables)

Σ a set of terminal symbols (disjoint from N)

R a set of rules or productions, each of the form A → β ,
   where A is a non-terminal,

β is a string of symbols from the infinite set of strings (Σ∪N)

S a designated start symbol and a member of N

San Jose State University

A context-free grammar consists of a set of rules or productions and a lexicon of words and symbols.  Each of those rules expresses the ways that symbols of the language can be grouped and ordered together.
For example, one rule for noun phrase, like "the flight", is that a noun phrase can be composed of a determiner and a nominal.
$$ NP --> Det \quad Nominal$$



Context-Free Grammars


An on-going but a helpful book resource about NLP
https://web.stanford.edu/~jurafsky/slp3/

Speech and Language Processing (3rd ed. draft) 

The terminal symbols is one of  the two symbol classes in the CFG, it corresponds to words in the language, like “the” and “flight”


Terminal Symbols


The non-terminal symbols are the symbols that express abstractions over the terminsals. For example, $$NP$$, $$Det$$, and $$Nominal$$ are non-terminal symbols.


Non-terminal Symbols


Some Grammar Rules

Sentences and their annotated parse trees in a treebank can form grammars representations. Hence, context-free grammar rules can be extracted, such as expanding VPs (4500 differenct rules for the Penn Treebank project) or NPs.

 CFG rules extractions in Treebanks

Formal Description of Context-Free Grammar

Standard lexicalized grammar is a type of grammar rule where each non-terminal node in a  lexicalized parse tree is associated with a lexical head (the headword) and a head tag, and the head tag is the part-of-speech tag of grammar. Below is an example of a parse tree for the sentence "Workers dumped sacks into a bin.".

Learn Before

Related