Computing Dictionary
grammar definition
language A formal definition of the syntactic structure (the
syntax) of a language.
A grammar is normally represented as a set 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
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
parser (a kind of
recogniser) uses a grammar to parse a sentence, assigning 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. The opposite, generation, starts from the top-level rule and chooses one alternative production wherever there is a choice.
In computing, a formal grammar, e.g. in
BNF, can be used to
parse a linear input stream, such as the
source code of a program, into a data structure that expresses the (or a) meaning of the input in a form that is easier for the computer to work with. A
compiler compiler like
yacc might be used to convert a grammar into code for the parser of a
compiler. A grammar might also be used by a
transducer, a
translator or a
syntax directed editor.
See also
attribute grammar.
(2009-02-06)