Grammars

Grammars describe languages. Natural languages, such as English, are often described by a grammar which groups words into syntactic categories such as subjects, predicates, prepositional phrases etc., and then into subcategories such as nouns, verbs, and prepositions, etc.

Stated more mathematically, a grammar is a formal device for specifying a potentially infinite language in a finite way, since it is impossible to list all the possible strings in a language whether it is English or C. At the same time, a grammar imposes a structure on the sentences in the language. That is, a grammar, G, defines a language, L(G), by defining a way to derive all legal strings in the language. We will look at this for a (very) small subset of English.

2.1.1 Context-free Grammar for English

2.1.2 Context-free Grammar for Programming Languages