grammar

A formal definition of the syntactic structure of a language

(see syntax), normally given in terms of production rules

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 naturallanguage 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, grammaranalysis.