[NEXT] [PREV]    HANDBOOK / GENTLE PRIMER / Describing Syntax /

Syntax Definitions


Using this grammatical interpretation of rules we can write

   'rule' Program : Declarationpart Statementpart
which states that a Program is given by a Declarationpart and a Statementpart.

We also need basic symbols of the language that are not defined by rules. These symbols are called terminal symbols or tokens and are written as strings denoting themselves. For example,

   'rule' Statement : "IF" Expression "THEN" Statement "ELSE" Statement
Here, "IF", "THEN", and "ELSE" are terminal symbols.

Grammatical symbols such as Statement that are defined by rules are called nonterminal symbols.

A grammar not only describes what is a valid text of a language, but also imposes a structure on the text. A grammar is given by a set of terminal symbols, a set of nonterminal symbols, and a set of rules. Rules have the form:

  • 'rule' A : B1 B2 ... Bn
where A is a nonterminal and the Bi are terminal or nonterminal symbols. A valid phrase of class A can be constructed by replacing each Bi by a valid phrase of Bi (if Bi is a terminal, the valid phrase is the terminal itself).

Given the rule for Statement and assuming that x>y is an expression and that x:=x-y and y:=y-x are statements, we can construct the more complex statement

   IF x>y THEN x:=x-y ELSE y:=y-x
The distinction between tokens and nonterminals reflects the fact that the analysis of the input text is generally decomposed into two (interleaved) steps: First the input is partitioned into tokens (lexical analysis), then the token stream is structured into hierarchical phrases (syntax analysis). Different techniques are used for each task.