grammar
A formal definition of the syntactic structure of a language
(see {syntax}), normally given in terms of {production rule}s
which specify the order of constituents and their
sub-constituents in a {sentence} (a well-formed string in the
language). Each rule has a left-hand side symbol naming a
syntactic category (e.g. "noun-phrase" for a {natural
language} grammar) and a right-hand side which is a sequence
of zero or more symbols. Each symbol may be either a
{terminal symbol} or a non-terminal symbol. A terminal symbol
corresponds to one "{lexeme}" - a part of the sentence with
no internal syntactic structure (e.g. an identifier or an
operator in a computer language). A non-terminal symbol is
the left-hand side of some rule.
One rule is normally designated as the top-level rule which
gives the structure for a whole sentence.
A grammar can be used either to parse a sentence (see
{parser}) or to generate one. Parsing assigns a terminal
syntactic category to each input token and a non-terminal
category to each appropriate group of tokens, up to the level
of the whole sentence. Parsing is usually preceded by
{lexical analysis}. Generation starts from the top-level rule
and chooses one alternative production wherever there is a
choice.
See also {BNF}, {yacc}, {attribute grammar}, {grammar
analysis}.