Introduction to Extended Affix Grammars
Parser generators are quite well known: They process a context free grammar specification to generate a parser.
The generated parser processes an arbitrary input text deciding whether this text is a sentence of the language described by the context free grammar the parser generator has generated the parser for. And if so, it almost generate a parse tree representing the input structurally.
A compiler generator, however, consist of an parser generator accompanied with an evaluator generator. The constructed parstree built by the generated parser is passed to the generated evaluator which performs semantic checks and generates the output in the specified target language.
However, what is the input to a compiler generator?
It must be partly a context free grammar specification. But this is not sufficient! Almost all real compilers are written for languages (like all general purpose programming languages) which are not context free, they are context-sensitive.
The specification for an compiler generator must belong to the class of context-sensitive grammars to be powerfull enough to define a context-sensitive language.
A quite famous context-sensitive language example which is not context-free is
{ anbncn | n ≥ 1 } = { abc, aabbcc, aaabbbccc, … }
E.g., words of this language are "abc", "aabbcc", "aaabbbccc" and so on. The number of "a", "b" and "c" characters is always equal in a word that belongs to that language.
This cannot be specified by a context-free grammar!
Let’s try to describe this language using a context-free grammar. We will use a formalism similar to the BNF grammar formalism.
S: A B C. A: "a" A | . B: "b" B | . C: "c" C | .
Possible word derivation using that grammar are
S →* aaabbbccc
S →* aaabbc
Both words are part of the language defined by our context-free grammar. However, the second word is not part of our context-sensitive language { anbncn | n ≥ 1 } — the number of "a", "b" and "c" characters are not equal! The language defined by this context free grammar has "more" words than the context-sensitive one we are looking for.
So, the the context-free grammar from above is not sufficient to describe our language. We somehow need to "count" the "a", "b" and "c" characters and compare the counts.
The Unary Numeral System is probably the first numeral system at all. Any child is starting to count using its fingers — its first unary numeral system. The first humans have probably used it. And in Germany they are counting the beers in the pub that way.
Here is an example using tally marks and a second using "i" for counting:
0: 0: 1: | 1: i 4: |||| 4: iiii
This kind of counting can be expressed by a context free grammar:
N → 'i' N . N → .
The nonterminal N derives to either a leading 'i' followed by a recursive application of the same nonterminal N, or it derives to the empty alternative. The final dot just marks the end of rule, especially helful for seeing empty alternatives.
This grammar defines the infinite language of all countable 'i’s. Formally:
L(GN) = { i, ii, iii, … } = { in | n ≥ 0}
We will come back to that later on.
But back to our context sensitive example anbncn. As we have figured out, we need to count the "a", "b" and "c" characters to compare the equality of their counts.
Let’s first do it naively by setting up a context free grammar for our language which represents the number of to be recognized characters of "a", "b" and "c" as part of the nonterminal name. The number of the characters is expressed as the corresponding number of "i"s.
We would start with the S, the start symbol of the grammar.
S → Ai Bi Ci . S → Aii Bii Cii . S → Aiii Biii Ciii . ...
We would need to add one rule for each natural number where the number of "i" behind the A, B and C nonterminal references corresponds to a natural number.
The same for the A rule:
A → . Ai → "a" A . Aii → "a" Ai . Aiii → "a" Aii . ...
Informally, here the number of "i" on the left side of the grammar rule corrsponds to the number of recognized "a" characters when all nonterminal gets resolved. This has been done similar for rules B and C.
Yes, this leads to an infinite number of rules. So it cannot be written down! But this infinite grammar extactly defines our language in questions.
Nevertheless, let’s verify this on a example by writing down the grammar derivation steps for a particular sentence of our language. The example sentence is
aabbcc
We start at the grammars start symbol trying to derive the example sentence. The grammar rules applied for the current derivation step is given in paranthesis behind:
S → Aii Bii Cii → aAi Bii Cii [Aii → ”a” Ai .] → aaA Bii Cii [Ai → ”a” A .] → aa Bii Cii [A → .] → aa bBi Cii [Bii → ”b” Bi .] → aa bbB Cii [Bi → ”b” B .] → aa bb Cii [B → .] → aa bb cCi [Cii → ”c” Ci .] → aa bb ccC [Ci → ”c” C .] → aa bb cc [C → .]
This shows that the sentence aa bb cc can be derived from the start symbol S and therefore this sentence is part of the language defined by the infinte grammar from above.
Still, the grammar is infinite. It cannot be written down. How to overcome this?
To get rid of it we will apply 2 tricks.
First, lets add <> parenthesis to the rule names to separate the original nonterminals from the context free grammar from the "i" counting name parts:
S → A<i> B<i> C<i> . S → A<ii> B<ii> C<ii> . S → A<iii> B<iii> C<iii> . ...
The added <> paranethesis can just be taken as part of the rule names and nothing will change from grammar and sentence derivation point of view. The nonterminal names just got longer. The grammar is still inifinite.
The second trick is to introduce a second grammar, called the Meta Grammar, and embedd it into the first one. … That’s where the term "two level grammar" is coming from.
You probably remember the grammar for the Unary Numeral System from our excursion:
N → 'i' N . N → .
Anyone of the sequences of "i" in the grammar with <> parenthesis is a sentence of the language build by the Unary Numeral Sytem grammar.
N →* i N →* ii N →* iii N →* iiii ...
So each occurence of "i" in the grammar with <> parenthesis could be replaced by the nonterminal N if N is treated as the start symbol for a sentence of the second grammar, the meta grammar. While the <> parenthesis are treated as real paranthesis separating the first grammar from the second grammar parts.
If we do this for all the infinite number of grammar rules they become a finite number.
The start symbol rules of S
S → A<i> B<i> C<i> . S → A<ii> B<ii> C<ii> . S → A<iii> B<iii> C<iii> . ...
shrinks together to the one following rule if sequences of "i" are substituted by the start symbol of the Unary Numeral System grammar N:
S → A<N> B<N> C<N> .
We call the grammar parts in the parenthesis an Affix and more specifc, the nonterminal of the meta grammar inside an Affix Variable. It’s a variable as it stands for an arbitrary sentence of the meta grammar language. In our case it can be an arbitrary number of "i".
And here a major constraint of our formalism comes into play: If an affix variable occurs several times in a rule, it must be derived to the same sentence of the meta grammar language. Here it means that all N behind A, B and C must derive to the same number of "i". This coinstraint is later on ensure by the implementation of the compiler generator. We call it, the Principle of Consistent Substitution.
We do it similar for the A rule as an example. It may be done similar for B and C. They are structurally equivalent.
A<> → . A<i> → "a" A . A<ii> → "a" A<i> . A<iii> → "a" A<ii> . ...
becomes
A<> → . A<"i" N> → "a" A<N> .
That way, we got only 2 rules for A. Here the same constraint is applied. But as the number if "i" on the left and the right hand side of the rules are different, only part of the "i" can be substituted by an N because N must be derived to the same number of "i" inside one rule according to the Principle of Consistent Substitution.
So one "i" on the left hand side of the rule remains. But this just represents the counting of an "a" from the right hand side of the rule.
This becomes more clear when we try to derive a sentence of the langue using our 2-level grammar. Let’s try to derive again the sentence "aabbcc" as we have done already before.
Note, the rule in the brackets below are the one which got applied for the derivation step result shown on the left. So, the previous derivation state the rule got applied to is shown one line above. And, the character "ɛ" is Epsilon, the empty word.
S → A<N> B<N> C<N> [S → A<N> B<N> C<N>] → A<iN> B<N> C<N> [meta: N → "i" N.] → A<iiN> B<N> C<N> [meta: N → "i" N.] → A<ii> B<N> C<N> [meta: N → .] → A<ii> B<iN> C<N> [meta: N → "i" N.] → A<ii> B<iiN> C<N> [meta: N → "i" N.] → A<ii> B<ii> C<N> [meta: N → .] → A<ii> B<ii> C<iN> [meta: N → "i" N.] → A<ii> B<ii> C<iiN> [meta: N → "i" N.] → A<ii> B<ii> C<ii> [meta: N → .] → aA<i> B<ii> C<ii> [A<"i" N> → ”a” A<N> . | with N →* i ] → aaA<> B<ii> C<ii> [A<"i" N> → ”a” A<N> . | with N →* ɛ ] → aa B<ii> C<ii> [A<> → .] → aa bB<i> C<ii> [B<"i" N> → ”b” B<N> . | with N →* i ] → aa bbB<> C<ii> [B<"i" N> → ”b” B<N> . | with N →* ɛ ] → aa bb C<ii> [B<> → .] → aa bb cC<i> [C<"i" N> → ”c” C<N> . | with N →* i ] → aa bb ccC<> [C<"i" N> → ”c” C<N> . | with N →* ɛ ] → aa bb cc [C<> → .]
So, the derivation is done the same way for a 2 level grammar as for a one level grammar, just derivation rules get applied. Some more rule steps have to be applied, however.
This shows that this approach is not just a trick but a formal method!
The grammar with affix in paranethesis is called Hyper Grammar.
Time to get the compiler generator to run on our example.
The BNF like grammar of our 2-level grammar language given in the Gamma grammar language notation may be looked up at abc-bnf.eag. It has the following content:
N = "i" N | .
S<+ N: N>: A <N> B <N> C <N>.
A<+ "i" N: N>: "a" A <N>.
A<+ : N> : .
B<- "i" N: N>: "b" B <N>.
B<- : N>:.
C<- "i" N: N>: "c" C <N>.
C<- : N>: .The rules of the meta grammar are given in a simple BNF syntax with the equal sign for separating the left hand side of the rule from the left hand side. Rule alternatives may be separated by the pipe operator. A rule is always finishied with a dot. Terminals are surrounded by double quotes.
N = "i" N | .The syntax for the hyper-rule of the start symbol S is very similar to the notation we used above. However, the left hand side of of the hyper-rule is separated from the right hand side of the rule by a colon. The rule is finished by a dot.
S<+ N: N>: A <N> B <N> C <N>.The first hyper rule nonterminal in the grammar specification is always treated as the start symbol of the grammar. It also becomes the name of the executable compiled by the D compiler.
The start symbol is also requiring an output affix that gets the result of the compilation, a formal constraint of the Gamma compiler generator formalism. It will be printed out on a compiler on the console. An output affix is always marked with a "+" sign. Each affix is also marked with it’s affix type — the type of the meta nonterminal it represents — separated by a colon from the affix form. It’s also called the affix signature.
S<+ N: N>The rules for the nonterminal A is similar. It is separated in two rules for the 2 needed alternatives, the rule which "counts" the "a" characters and the rule which drives to the empty word.
A<+ "i" N: N>: "a" A <N>.
A<+ : N> : .The string "i" N is a non-empty affix of the affix type N representing the first rule alternative of the N rule (see above). While the second rule of A specifies an empty affix form, the second rule alternative of the N rule. Both have the plus sign in front of, means, they represent an output affix.
Hyper rule alternatives can also be specified more conise using the pipe operator as for the meta rule and by using an EBNF formalism. But about that later, in another article.
In the following we have prepared an online development environment based on Gitpod.
Click on the following link and a development environment will be opened with the Gamma compiler generator pre-compiled and the Gamma grammar specification for our abc grammar opened in the editor:
|
DISCLAIMER
|
A free registration at ink:https://www.gitpod.io[gitpod.io] is required when following the link! |
Execute the following command will generate and compile a compiler for our language as shown in the following console screen shot:
gitpod /workspace/gamma (strumenta-talk-2021-10) $ ./gamma -s example/abc-bnf.ea info: Epsilon 1.02 JoDe/SteWe 22.11.96 info: SOAG-Evaluatorgenerator 1.06 dk 14.03.98 info: Analysing S info: S grammar is valid info: Analyser: no warnings on S's hyper-nonterminals info: predicates in S: 0 info: ELL(1) testing S info: S grammar is ELL(1) info: SLAG testing S info: S grammar is SLAG info: LexGen writing S info: ELL(1) writing S info: +rc +ct dmd S.d SLex.d -g include/runtime.d src/io.d src/log.d src/epsilon/soag/listacks.d gitpod /workspace/gamma (strumenta-talk-2021-10) $
The compiler code will be generated in the build/ directory with some D source code files and associated tables. It will also compile an executable S what we will go to invoke on an example to get our compiler run.
|
NOTE
|
Epsilon is the predecessor of Gamma which originally was implemented in Module-2. It’S name is still in code… |
Let’s start with a good case. The compiler executable is a real Unix tool, it accepts piped input. So we can redirect input on the command line directly into the compiler executable invocation:
gitpod /workspace/gamma (strumenta-talk-2021-10) $ echo aaabbbccc | ./S info: S compiler (generated with epsilon) i i i gitpod /workspace/gamma (strumenta-talk-2021-10) $
The innvocation does not fail with an error. The input "aaabbbccc" is part of our language. As result the compiler issues the compilation result, the numer of counted "a", "b" and "c" characters expressed as an equally numbered sequence of "i".
Another example, for a sentence not part of the langue, we just remove one "c" at the end.
gitpod /workspace/gamma (strumenta-talk-2021-10) $ echo aaabbbcc | ./S
info: S compiler (generated with epsilon)
error: analysis in C failed
stdin:2:1
^
info: errors detected: 1
gitpod /workspace/gamma (strumenta-talk-2021-10) $
The compiler run fails as expected with an error complaining that the (semantic) analysis fails for nonterminal C. Which is right as the number of "c" characters in the input sequence is not equal to the number "a" and "b" characters.
|
NOTE
|
The "^" character is intended to mark the error position. This works better on real files but not quite well on piped input. Ignore it for now, please. |
If we remove another "b" character, we will get 2 errors:
gitpod /workspace/gamma (strumenta-talk-2021-10) $ echo aaabbcc | ./S
info: S compiler (generated with epsilon)
error: analysis in B failed
stdin:1:6 aaabbcc
^
error: analysis in C failed
stdin:2:1
^
info: errors detected: 2
gitpod /workspace/gamma (strumenta-talk-2021-10) $
This makes it obvious: The count of "a" characters is always treated as the "right" count. We will not get error for a wrong number of "a" characters. This is determined by how the analysis may be formally controlled. To understand why this is the case, we need to examine the other rules for B or C. The rules for B are defined as follows:
B<- "i" N: N>: "b" B <N>.
B<- : N>:.When we look closer the only difference to the A hyper-rule, beside all the b characters in upper and lower case, is the minus character in front of the affix form. Here is the A hyper rule again for comparision:
A<+ "i" N: N>: "a" A <N>.
A<+ : N> : .The minus character defines an affix as to be an input affix. The direction of affix, input and output, specifies the data flow of the affix values inside the compiler and implcitely define where the comparisions take place to ensure the Principle of Consistent Substitution holds true.
When specifying a compiler with Gamma, we mainly think in terms of affix value flows which are attached to the hyper nonterminals of our grammar.
Sometimes and in a first approach, it is easier to think of the alternatives of a hyper nonterminal as one method declaration: The left hand side of a rule is a method signature, output affix are ouptut paramaters. The right hand side of the rule is a method body, terminals are used to decide which alterntive to choose.
Let’s examine this at the A rules, first. Here, we could imagine it as the following method declaration:
void A(out N affix) {
if (is("a") {
A(affixOfRecursion)
affix = "i" affixOfRecursion
}
else
affix = ɛ // return the empty word
}So, the A method implements a recursion which in its termination case returns the empty word. And, in its recursive case it constructs the result of the current iteration by adding "i" in front of the result of the recursion.
However, when looking at representing the B rules as method the affix parameter becomes an input parameter which needs to be decompositioned:
void B(in N affix) {
if (is("b") {
assert(affix == "i" N)
let ("i" affixOfRecursion) = affix // decomposition
B(affixOfRecursion)
}
else
assert(affix == ɛ) // the empty word
}At the recursion case, the incoming affix gets checked to be structurally equal to sentence form corresponding to the first grammar rule alternative of the meta nonterminla N. And, it gets implicitelly decompoitioned into a leading "i" and representation of an N value which gets passed down into the recursion call.
At the recursion termination case it is checked whether the empty word has been passed in.
That way, the whole sentence of passed in "i" gets decompositioned and checked whether for each an "b" can be counted.
|
NOTE
|
This representation of the affix flow semantic and of the hyper rules as methods is a meaningful apporach to reason about the grammar specifacation. However, not alle affix dependency graphs created by affix flows can be repesented that way and result in a method-like implementation. If possible, the Gamma compiler generator will generate methods in that way. However, for more sophisticated affix dependency graphs it is able to generate more elaborated affix evaluation mechanisms. |