Definition:Formal Grammar
Contents |
Definition
Let $\mathcal L$ be a formal language whose alphabet is $\mathcal A$.
The formal grammar (or syntax) of $\mathcal L$ is the set of rules of formation which determine whether words in $\mathcal A$ belong to $\mathcal L$ or not.
Rules of Formation
The rules of formation of $\mathcal L$ are the rules which define how to construct words in $\mathcal L$ which are well-formed.
That is, the rules of formation tell you how to build strings consisting of symbols from the alphabet $\mathcal A$ which are part of the formal language $\mathcal L$.
The rules of formation of a formal language constitute its syntax.
Top-Down
A top-down grammar is one whose rules of formation allow the user to build well-formed words from a single metasymbol, in the following way:
- A metasymbol may be replaced by an element of a specified collection of concatenations of metasymbols and signs.
- A metasymbols may be replaced by a primitive symbol.
From the words thus generated, those not containing any metasymbols are the well-formed words.
Bottom-Up
A bottom-up grammar is one whose rules of formation allow the user to build well-formed words from primitive symbols, in the following way:
- Primitive symbols are well-formed words.
- A collection of specified concatenations of well-formed words and signs are also well-formed words.
