To easily express grammar rules there is the Definite Clause Grammar notation. With the DCG notation it becomes easy to implement formal grammars in Trinc-Prolog. A grammar in the correct DCG notation is automatically translated by the Trinc-Prolog compiler to a Prolog program which can be executed immediately.
A formal grammar rule is of the form:
head --> body
Such a rule says: whenever a symbol like 'head' appears in a string then it can be replaced by the symbol(s) after the -->/2 operator, thus 'body'. A grammar rule can also be called a production rule as it produces 'body' from 'head'.
A grammar consist of one or more grammar rules. With a grammar it is possible to generate a sequence of symbols called a sentence. The generation of a sentence always starts with a starting non-terminal symbol. A non-terminal symbol is a symbol that produces output. A simple example of a grammar is:
| house --> [foundation], floor, [roof]. floor --> [first_floor], [second_floor]. floor --> [first_floor]. |
Terminal symbols are enclosed by brackets and non-terminal symbols are not. This grammar can produce two kinds of houses if the start symbol is 'house', a house with two floors or with just one floor. The two possible sentences are:
| 1. foundation, first_floor, second_floor, roof. 2. foundation, first_floor, roof. |
A grammar can also be used to recognize sentences of symbols. In recognition it starts with the sentence of symbols and then starts applying the grammar rules in the opposite direction. If the sentence contains a sub-sentence which matches the right-side of a grammar rule then that complete sub-sentence is replaced by the 'head' of the same grammar rule. The recognition process stops when it successfully has reduced the complete sentence to the non-terminal starting symbol. Example of recognizing a sentence of symbols:
| sentence #1: foundation, first_floor, roof action: replace 'first_floor' by 'floor' sentence #2: foundation, floor, roof action: replace 'foundation, floor, roof' by 'house' sentence #3: house action: finished because 'house' is a non-terminal starting symbol |