The Syntax of Credit Card Numbers
Steven Pemberton, CWI, Amsterdam
The numbers on credit cards (and other similar identification numbers) consist of a string of digits. These are traditionally checked for semi-validity using the Luhn algorithm, defined in Annex B of ISO/IEC 7812-1, which is a right-to-left mathematical check-sum style algorithm that guards against common errors such as mistyping single digits, and interchanging adjacent digits.
This talk considers how although the Luhn algorithm is a mathematical function, surprisingly its effect can be expressed using a grammar, and that therefore credit card numbers actually have an internal syntax.
The talk explains the method behind how this works, and then in a number of steps, develops firstly a grammar that requires a general parser such as ixml's to verify credit card numbers, and then uses that to generate an LL1 grammar working left-to-right that achieves the same purpose.
The resultant grammar is large, of the order of a hundred rules, but is so systematic that it can be generated mechanically by a program.
It was pointed out by the late Michael Sperberg-McQueen that a function that requires the digits of a number to sum to a particular value, modulo some other value, can be represented as a grammar.
Consider: a number is divisible by 3 if the sum of its digits is also divisible by three.
The number 783 is divisible by three:
7+8+3=18
1+8=9, which is divisible by 3.
If the first character is:
Subsequent characters:
And so on.
You start in state 0, and aim to end up in state 0:
Each rule represents one state: div3 is the start state. Each
state must have a follow state, except for zero which can be
empty, since it is an acceptable terminating state.
input: (div3, -#a)+.
div3: ["0369"], zero;
["147"], one;
["258"], two.
-one: ["0369"], one;
["147"], two;
["258"], zero.
-two: ["0369"], two;
["147"], zero;
["258"], one.
-zero: ;
["0369"], zero;
["147"], one;
["258"], two.
<input> <div3>3</div3> <div3>39</div3> <div3>285</div3> <div3>123</div3> </input>
If a value is not divisible by 3, you get a syntax error:
<fail ixml:state="failed" xmlns:ixml="http://invisiblexml.org/NS">
**** Parsing failed at line 3, position 4
284
^
**** Character: (#A).
</fail>
Since they are mutually exclusive, inputs can be split into good and bad
classes. All classes are now terminating classes, but only zero is
a good terminating class:
input: ((good; bad), -#a)+.
good: zero.
bad: one; two.
-one: ["0369"], one;
["147"], two;
["258"], zero?.
-two: ["0369"], two;
["147"], zero?;
["258"], one.
-zero:["0369"], zero?;
["147"], one;
["258"], two.
Output of this looks like this:
<input> <good>3</good> <good>39</good> <good>285</good> <bad>284</bad> <good>123</good> <bad>124</bad> </input>
That example had three main states, since we are checking for modulo 3.
Modulo any other number would need an equivalent number of states. Here is an example checking for divisibility by 7:
input: ((good; bad), -#a)*. good: s0. bad: s1; s2; s3; s4; s5; s6. -s0: ["07"], s0; ["18"], s1; ["29"], s2; "3", s3; "4", s4; "5", s5; "6", s6; . -s1: ["07"], s3; ["18"], s4; ["29"], s5; "3", s6; "4", s0; "5", s1; "6", s2. -s2: ["07"], s6; ["18"], s0; ["29"], s1; "3", s2; "4", s3; "5", s4; "6", s5. -s3: ["07"], s2; ["18"], s3; ["29"], s4; "3", s5; "4", s6; "5", s0; "6", s1. -s4: ["07"], s5; ["18"], s6; ["29"], s0; "3", s1; "4", s2; "5", s3; "6", s4. -s5: ["07"], s1; ["18"], s2; ["29"], s3; "3", s4; "4", s5; "5", s6; "6", s0. -s6: ["07"], s4; ["18"], s5; ["29"], s6; "3", s0; "4", s1; "5", s2; "6", s3.
Credit card numbers (and similar identification numbers) are a string of digits, with a check-sum digit added so that the sum of the digits is divisible by ten.
One difference: starting from the right-hand end, odd-numbered digits are added in, and even-numbered digits are doubled, and the digits of the doubling are added in.
This spots a single mistyped digit, and the alternate doublings spots an omitted digit or two swapped adjacent digits (except for "90" or "09", since they map to themselves).
This permits a small amount of client-side validity pre-checking.
To take a simple example of the algorithm, the number 8862
(remember to read right-to-left):
8 8 6 2 digit
d s d s doubling state
7 8 3 2 result value
0 3 5 2 modulo state
To take another example, 32862:
3 2 8 6 2 digit s d s d s doubling state 3 4 8 3 2 result value 0 7 3 5 2 modulo state
There seems to be no indication why.
One plausible explanation: if the number is stored as a number rather than a string of characters, it is easier to extract the right-most digit, using modulo ten, than the left-most one.
This would also explain why zero maps to itself, since if the credit card number is stored as a number, it is not possible to tell how many leading zeros there are.
Since the algorithm works right-to-left, we have to write the syntax rules to reflect this.
Unlike the modulo three version where the next digit takes us into a new state, in this case we come from a state, and it is followed by a digit.
Looked at in a different way, read each rule right-to-left, so a digit takes us into a new state.
Since the algorithm uses modulo ten, you might expect the equivalent ixml to have ten states, but there are twenty: ten for the characters that are doubled, and ten for the single case.
So an s0 (a single-valued digit, giving a modulus of 0) is a
d0 followed by a 0, or a d1 followed by
a 9, or a d2 followed by an 8, and so
on:
s0: d0, "0";
d1, "9";
d2, "8";
d3, "7";
d4, "6";
d5, "5";
d6, "4";
d7, "3";
d8, "2";
d9, "1".
For a d0, it's slightly more complicated, because the digits
have to be doubled.
An s0 followed by a 0 will give a d0,
as will an s1 followed by a 9, but an s2
must be followed by a 4 (since 4×2=8 and
2+8=10), and so on:
d0: s0, "0";
s1, "9";
s2, "4";
s3, "8";
s4, "3";
s5, "7";
s6, "2";
s7, "6";
s8, "1";
s9, "5".
Thus parsing from right to left, we start from s0, and we want
to end up in a state where the modulus is zero, but we don't care if the next
character is doubled or not; so both s0 and d0 are
end states.
Here are the 20 rules, from s0 to s9, and from
d0 to d9. Creating them is fairly mechanical, and can
even be produced by a program:
input: (cc, -#a)+. cc: s0. -s0: d0, "0"; d1, "9"; d2, "8"; d3, "7"; d4, "6"; d5, "5"; d6, "4"; d7, "3"; d8, "2"; d9, "1"; . -s1: d0, "1"; d1, "0"; d2, "9"; d3, "8"; d4, "7"; d5, "6"; d6, "5"; d7, "4"; d8, "3"; d9, "2". -s2: d0, "2"; d1, "1"; d2, "0"; d3, "9"; d4, "8"; d5, "7"; d6, "6"; d7, "5"; d8, "4"; d9, "3". -s3: d0, "3"; d1, "2"; d2, "1"; d3, "0"; d4, "9"; d5, "8"; d6, "7"; d7, "6"; d8, "5"; d9, "4". -s4: d0, "4"; d1, "3"; d2, "2"; d3, "1"; d4, "0"; d5, "9"; d6, "8"; d7, "7"; d8, "6"; d9, "5". -s5: d0, "5"; d1, "4"; d2, "3"; d3, "2"; d4, "1"; d5, "0"; d6, "9"; d7, "8"; d8, "7"; d9, "6". -s6: d0, "6"; d1, "5"; d2, "4"; d3, "3"; d4, "2"; d5, "1"; d6, "0"; d7, "9"; d8, "8"; d9, "7". -s7: d0, "7"; d1, "6"; d2, "5"; d3, "4"; d4, "3"; d5, "2"; d6, "1"; d7, "0"; d8, "9"; d9, "8". -s8: d0, "8"; d1, "7"; d2, "6"; d3, "5"; d4, "4"; d5, "3"; d6, "2"; d7, "1"; d8, "0"; d9, "9". -s9: d0, "9"; d1, "8"; d2, "7"; d3, "6"; d4, "5"; d5, "4"; d6, "3"; d7, "2"; d8, "1"; d9, "0". -d0: s0, "0"; s1, "9"; s2, "4"; s3, "8"; s4, "3"; s5, "7"; s6, "2"; s7, "6"; s8, "1"; s9, "5"; . -d1: s0, "5"; s1, "0"; s2, "9"; s3, "4"; s4, "8"; s5, "3"; s6, "7"; s7, "2"; s8, "6"; s9, "1". -d2: s0, "1"; s1, "5"; s2, "0"; s3, "9"; s4, "4"; s5, "8"; s6, "3"; s7, "7"; s8, "2"; s9, "6". -d3: s0, "6"; s1, "1"; s2, "5"; s3, "0"; s4, "9"; s5, "4"; s6, "8"; s7, "3"; s8, "7"; s9, "2". -d4: s0, "2"; s1, "6"; s2, "1"; s3, "5"; s4, "0"; s5, "9"; s6, "4"; s7, "8"; s8, "3"; s9, "7". -d5: s0, "7"; s1, "2"; s2, "6"; s3, "1"; s4, "5"; s5, "0"; s6, "9"; s7, "4"; s8, "8"; s9, "3". -d6: s0, "3"; s1, "7"; s2, "2"; s3, "6"; s4, "1"; s5, "5"; s6, "0"; s7, "9"; s8, "4"; s9, "8". -d7: s0, "8"; s1, "3"; s2, "7"; s3, "2"; s4, "6"; s5, "1"; s6, "5"; s7, "0"; s8, "9"; s9, "4". -d8: s0, "4"; s1, "8"; s2, "3"; s3, "7"; s4, "2"; s5, "6"; s6, "1"; s7, "5"; s8, "0"; s9, "9". -d9: s0, "9"; s1, "4"; s2, "8"; s3, "3"; s4, "7"; s5, "2"; s6, "6"; s7, "1"; s8, "5"; s9, "0".
Here is an example of its output:
<input> <cc>8862</cc> <cc>32862</cc> <cc>12344</cc> </input>
If it gets a non-valid number, you get a parse error:
<fail ixml:state="failed" xmlns:ixml="http://invisiblexml.org/NS">
**** Parsing failed at line 1, position 5
8861
^
**** Character: (#A).
</fail>
If you're interested in the complete parse of a number, here it is for the first above:
<cc>
<s0>
<d8>
<s5>
<d7>
<s0/>8
</d7>8
</s5>6
</d8>2
</s0>
</cc>
Each closing tag shows what state we are in: we start off in
<s0/>, the first 8, takes us into state d7, the
next 8 into s5, the 6 into d8, and the final 2 into
s0, which is the end state we want to be in.
The second number above yields the following, where we start off in
<d0/> and end again in s0:
<cc>
<s0>
<d8>
<s5>
<d7>
<s3>
<d0/>3
</s3>2
</d7>8
</s5>6
</d8>2
</s0>
</cc>
We can't use the good/bad technique from the earlier div3
example, because the 'good' and 'bad' parses are not mutually exclusive, and so
all results would be ambiguous.
For instance, here is a 'bad' parse for 8862 (which we know also has a 'good' parse):
<d5>
<s9>
<d5>
<s2>
<d0/>8
</s2>8
</d5>6
</s9>2
</d5>
Evaluating a modulo works just as easily left to right, but the problem is, we don't know if the first character should be doubled or not.
Here are two results, the first assuming the first character is doubled, the second that the first character isn't doubled:
8 8 6 2 digit d s d s doubling state 7 8 3 2 result value 0 7 5 8 0 modulo state
8 8 6 2 digit s d s d doubling state 8 7 6 4 result value 0 8 5 1 5 modulo state
What we can see is that the first succeeds, and the other doesn't.
So what we can do is have two parses running simultaneously, one assuming the first digit is singled, the other assuming the first digit is doubled: only one will succeed when it reaches the last digit.
So at the top level we start the two parses, one for the next character being doubled, and the other singled:
input: (cc, -#a)+. cc: s0; d0.
The rule s0 represents that we have a modulus of 0, and are
about to treat a singled digit. The next digit will be doubled:
s0: "0", d0;
"1", d1;
"2", d2;
"3", d3;
"4", d4;
"5", d5;
"6", d6;
"7", d7;
"8", d8;
"9", d9.
The rule d0 represents a modulus of 0, and treating a doubled
digit:
d0: "0", s0;
"1", s2;
"2", s4;
"3", s6;
"4", s8;
"5", s1;
"6", s3;
"7", s5;
"8", s7;
"9", s9;
.
We must end in state d0, where the modulus is zero, and the
next character would be doubled (in other words, we have just processed a
singled character).
Here are all 20 rules:
s0: "0", d0; "1", d1; "2", d2; "3", d3; "4", d4; "5", d5; "6", d6; "7", d7; "8", d8; "9", d9. s1: "0", d1; "1", d2; "2", d3; "3", d4; "4", d5; "5", d6; "6", d7; "7", d8; "8", d9; "9", d0. s2: "0", d2; "1", d3; "2", d4; "3", d5; "4", d6; "5", d7; "6", d8; "7", d9; "8", d0; "9", d1. s3: "0", d3; "1", d4; "2", d5; "3", d6; "4", d7; "5", d8; "6", d9; "7", d0; "8", d1; "9", d2. s4: "0", d4; "1", d5; "2", d6; "3", d7; "4", d8; "5", d9; "6", d0; "7", d1; "8", d2; "9", d3. s5: "0", d5; "1", d6; "2", d7; "3", d8; "4", d9; "5", d0; "6", d1; "7", d2; "8", d3; "9", d4. s6: "0", d6; "1", d7; "2", d8; "3", d9; "4", d0; "5", d1; "6", d2; "7", d3; "8", d4; "9", d5. s7: "0", d7; "1", d8; "2", d9; "3", d0; "4", d1; "5", d2; "6", d3; "7", d4; "8", d5; "9", d6. s8: "0", d8; "1", d9; "2", d0; "3", d1; "4", d2; "5", d3; "6", d4; "7", d5; "8", d6; "9", d7. s9: "0", d9; "1", d0; "2", d1; "3", d2; "4", d3; "5", d4; "6", d5; "7", d6; "8", d7; "9", d8. d0: "0", s0; "1", s2; "2", s4; "3", s6; "4", s8; "5", s1; "6", s3; "7", s5; "8", s7; "9", s9; . d1: "0", s1; "1", s3; "2", s5; "3", s7; "4", s9; "5", s2; "6", s4; "7", s6; "8", s8; "9", s0. d2: "0", s2; "1", s4; "2", s6; "3", s8; "4", s0; "5", s3; "6", s5; "7", s7; "8", s9; "9", s1. d3: "0", s3; "1", s5; "2", s7; "3", s9; "4", s1; "5", s4; "6", s6; "7", s8; "8", s0; "9", s2. d4: "0", s4; "1", s6; "2", s8; "3", s0; "4", s2; "5", s5; "6", s7; "7", s9; "8", s1; "9", s3. d5: "0", s5; "1", s7; "2", s9; "3", s1; "4", s3; "5", s6; "6", s8; "7", s0; "8", s2; "9", s4. d6: "0", s6; "1", s8; "2", s0; "3", s2; "4", s4; "5", s7; "6", s9; "7", s1; "8", s3; "9", s5. d7: "0", s7; "1", s9; "2", s1; "3", s3; "4", s5; "5", s8; "6", s0; "7", s2; "8", s4; "9", s6. d8: "0", s8; "1", s0; "2", s2; "3", s4; "4", s6; "5", s9; "6", s1; "7", s3; "8", s5; "9", s7. d9: "0", s9; "1", s1; "2", s3; "3", s5; "4", s7; "5", s0; "6", s2; "7", s4; "8", s6; "9", s8.
Here are two examples of its output:
<cc>
<d0>8
<s7>8
<d5>6
<s8>2
<d0/>
</s8>
</d5>
</s7>
</d0>
</cc>
<cc>
<s0>3
<d3>2
<s7>8
<d5>6
<s8>2
<d0/>
</s8>
</d5>
</s7>
</d3>
</s0>
</cc>
What we are now going to do is merge the two parses above to create a single left-to-right parse.
Each state will represent the two sums, one assuming the first digit was doubled, and the other assuming it was singled.
We start off in s0d0. From there, a 0 keeps us in
s0d0, but a 1 takes us to s2d1, and a 2 to
s4d2, and so on.
At each character the sum swaps from s to d, and
d to s, since one keeps the sum starting from
s as the first character, and the other starting from
d.
The starting rule looks like this:
-s0d0: "0", s0d0;
"1", s2d1;
"2", s4d2;
"3", s6d3;
"4", s8d4;
"5", s1d5;
"6", s3d6;
"7", s5d7;
"8", s7d8;
"9", s9d9; .
There are therefore 100 rules (they were produced by a program).
Any rule name ending with d0 is a potential terminating state,
since that means the current sum is 0, and the next character would be doubled
(which means we've just had a singled character).
input: (cc, -#a)+. cc: s0d0. -s0d0: "0", s0d0; "1", s2d1; "2", s4d2; "3", s6d3; "4", s8d4; "5", s1d5; "6", s3d6; "7", s5d7; "8", s7d8; "9", s9d9; . -s0d1: "0", s1d0; "1", s3d1; "2", s5d2; "3", s7d3; "4", s9d4; "5", s2d5; "6", s4d6; "7", s6d7; "8", s8d8; "9", s0d9. -s0d2: "0", s2d0; "1", s4d1; "2", s6d2; "3", s8d3; "4", s0d4; "5", s3d5; "6", s5d6; "7", s7d7; "8", s9d8; "9", s1d9. -s0d3: "0", s3d0; "1", s5d1; "2", s7d2; "3", s9d3; "4", s1d4; "5", s4d5; "6", s6d6; "7", s8d7; "8", s0d8; "9", s2d9. -s0d4: "0", s4d0; "1", s6d1; "2", s8d2; "3", s0d3; "4", s2d4; "5", s5d5; "6", s7d6; "7", s9d7; "8", s1d8; "9", s3d9. -s0d5: "0", s5d0; "1", s7d1; "2", s9d2; "3", s1d3; "4", s3d4; "5", s6d5; "6", s8d6; "7", s0d7; "8", s2d8; "9", s4d9. -s0d6: "0", s6d0; "1", s8d1; "2", s0d2; "3", s2d3; "4", s4d4; "5", s7d5; "6", s9d6; "7", s1d7; "8", s3d8; "9", s5d9. -s0d7: "0", s7d0; "1", s9d1; "2", s1d2; "3", s3d3; "4", s5d4; "5", s8d5; "6", s0d6; "7", s2d7; "8", s4d8; "9", s6d9. -s0d8: "0", s8d0; "1", s0d1; "2", s2d2; "3", s4d3; "4", s6d4; "5", s9d5; "6", s1d6; "7", s3d7; "8", s5d8; "9", s7d9. -s0d9: "0", s9d0; "1", s1d1; "2", s3d2; "3", s5d3; "4", s7d4; "5", s0d5; "6", s2d6; "7", s4d7; "8", s6d8; "9", s8d9. -s1d0: "0", s0d1; "1", s2d2; "2", s4d3; "3", s6d4; "4", s8d5; "5", s1d6; "6", s3d7; "7", s5d8; "8", s7d9; "9", s9d0; . -s1d1: "0", s1d1; "1", s3d2; "2", s5d3; "3", s7d4; "4", s9d5; "5", s2d6; "6", s4d7; "7", s6d8; "8", s8d9; "9", s0d0. -s1d2: "0", s2d1; "1", s4d2; "2", s6d3; "3", s8d4; "4", s0d5; "5", s3d6; "6", s5d7; "7", s7d8; "8", s9d9; "9", s1d0. -s1d3: "0", s3d1; "1", s5d2; "2", s7d3; "3", s9d4; "4", s1d5; "5", s4d6; "6", s6d7; "7", s8d8; "8", s0d9; "9", s2d0. -s1d4: "0", s4d1; "1", s6d2; "2", s8d3; "3", s0d4; "4", s2d5; "5", s5d6; "6", s7d7; "7", s9d8; "8", s1d9; "9", s3d0. -s1d5: "0", s5d1; "1", s7d2; "2", s9d3; "3", s1d4; "4", s3d5; "5", s6d6; "6", s8d7; "7", s0d8; "8", s2d9; "9", s4d0. -s1d6: "0", s6d1; "1", s8d2; "2", s0d3; "3", s2d4; "4", s4d5; "5", s7d6; "6", s9d7; "7", s1d8; "8", s3d9; "9", s5d0. -s1d7: "0", s7d1; "1", s9d2; "2", s1d3; "3", s3d4; "4", s5d5; "5", s8d6; "6", s0d7; "7", s2d8; "8", s4d9; "9", s6d0. -s1d8: "0", s8d1; "1", s0d2; "2", s2d3; "3", s4d4; "4", s6d5; "5", s9d6; "6", s1d7; "7", s3d8; "8", s5d9; "9", s7d0. -s1d9: "0", s9d1; "1", s1d2; "2", s3d3; "3", s5d4; "4", s7d5; "5", s0d6; "6", s2d7; "7", s4d8; "8", s6d9; "9", s8d0. -s2d0: "0", s0d2; "1", s2d3; "2", s4d4; "3", s6d5; "4", s8d6; "5", s1d7; "6", s3d8; "7", s5d9; "8", s7d0; "9", s9d1; . -s2d1: "0", s1d2; "1", s3d3; "2", s5d4; "3", s7d5; "4", s9d6; "5", s2d7; "6", s4d8; "7", s6d9; "8", s8d0; "9", s0d1. -s2d2: "0", s2d2; "1", s4d3; "2", s6d4; "3", s8d5; "4", s0d6; "5", s3d7; "6", s5d8; "7", s7d9; "8", s9d0; "9", s1d1. -s2d3: "0", s3d2; "1", s5d3; "2", s7d4; "3", s9d5; "4", s1d6; "5", s4d7; "6", s6d8; "7", s8d9; "8", s0d0; "9", s2d1. -s2d4: "0", s4d2; "1", s6d3; "2", s8d4; "3", s0d5; "4", s2d6; "5", s5d7; "6", s7d8; "7", s9d9; "8", s1d0; "9", s3d1. -s2d5: "0", s5d2; "1", s7d3; "2", s9d4; "3", s1d5; "4", s3d6; "5", s6d7; "6", s8d8; "7", s0d9; "8", s2d0; "9", s4d1. -s2d6: "0", s6d2; "1", s8d3; "2", s0d4; "3", s2d5; "4", s4d6; "5", s7d7; "6", s9d8; "7", s1d9; "8", s3d0; "9", s5d1. -s2d7: "0", s7d2; "1", s9d3; "2", s1d4; "3", s3d5; "4", s5d6; "5", s8d7; "6", s0d8; "7", s2d9; "8", s4d0; "9", s6d1. -s2d8: "0", s8d2; "1", s0d3; "2", s2d4; "3", s4d5; "4", s6d6; "5", s9d7; "6", s1d8; "7", s3d9; "8", s5d0; "9", s7d1. -s2d9: "0", s9d2; "1", s1d3; "2", s3d4; "3", s5d5; "4", s7d6; "5", s0d7; "6", s2d8; "7", s4d9; "8", s6d0; "9", s8d1. -s3d0: "0", s0d3; "1", s2d4; "2", s4d5; "3", s6d6; "4", s8d7; "5", s1d8; "6", s3d9; "7", s5d0; "8", s7d1; "9", s9d2; . -s3d1: "0", s1d3; "1", s3d4; "2", s5d5; "3", s7d6; "4", s9d7; "5", s2d8; "6", s4d9; "7", s6d0; "8", s8d1; "9", s0d2. -s3d2: "0", s2d3; "1", s4d4; "2", s6d5; "3", s8d6; "4", s0d7; "5", s3d8; "6", s5d9; "7", s7d0; "8", s9d1; "9", s1d2. -s3d3: "0", s3d3; "1", s5d4; "2", s7d5; "3", s9d6; "4", s1d7; "5", s4d8; "6", s6d9; "7", s8d0; "8", s0d1; "9", s2d2. -s3d4: "0", s4d3; "1", s6d4; "2", s8d5; "3", s0d6; "4", s2d7; "5", s5d8; "6", s7d9; "7", s9d0; "8", s1d1; "9", s3d2. -s3d5: "0", s5d3; "1", s7d4; "2", s9d5; "3", s1d6; "4", s3d7; "5", s6d8; "6", s8d9; "7", s0d0; "8", s2d1; "9", s4d2. -s3d6: "0", s6d3; "1", s8d4; "2", s0d5; "3", s2d6; "4", s4d7; "5", s7d8; "6", s9d9; "7", s1d0; "8", s3d1; "9", s5d2. -s3d7: "0", s7d3; "1", s9d4; "2", s1d5; "3", s3d6; "4", s5d7; "5", s8d8; "6", s0d9; "7", s2d0; "8", s4d1; "9", s6d2. -s3d8: "0", s8d3; "1", s0d4; "2", s2d5; "3", s4d6; "4", s6d7; "5", s9d8; "6", s1d9; "7", s3d0; "8", s5d1; "9", s7d2. -s3d9: "0", s9d3; "1", s1d4; "2", s3d5; "3", s5d6; "4", s7d7; "5", s0d8; "6", s2d9; "7", s4d0; "8", s6d1; "9", s8d2. -s4d0: "0", s0d4; "1", s2d5; "2", s4d6; "3", s6d7; "4", s8d8; "5", s1d9; "6", s3d0; "7", s5d1; "8", s7d2; "9", s9d3; . -s4d1: "0", s1d4; "1", s3d5; "2", s5d6; "3", s7d7; "4", s9d8; "5", s2d9; "6", s4d0; "7", s6d1; "8", s8d2; "9", s0d3. -s4d2: "0", s2d4; "1", s4d5; "2", s6d6; "3", s8d7; "4", s0d8; "5", s3d9; "6", s5d0; "7", s7d1; "8", s9d2; "9", s1d3. -s4d3: "0", s3d4; "1", s5d5; "2", s7d6; "3", s9d7; "4", s1d8; "5", s4d9; "6", s6d0; "7", s8d1; "8", s0d2; "9", s2d3. -s4d4: "0", s4d4; "1", s6d5; "2", s8d6; "3", s0d7; "4", s2d8; "5", s5d9; "6", s7d0; "7", s9d1; "8", s1d2; "9", s3d3. -s4d5: "0", s5d4; "1", s7d5; "2", s9d6; "3", s1d7; "4", s3d8; "5", s6d9; "6", s8d0; "7", s0d1; "8", s2d2; "9", s4d3. -s4d6: "0", s6d4; "1", s8d5; "2", s0d6; "3", s2d7; "4", s4d8; "5", s7d9; "6", s9d0; "7", s1d1; "8", s3d2; "9", s5d3. -s4d7: "0", s7d4; "1", s9d5; "2", s1d6; "3", s3d7; "4", s5d8; "5", s8d9; "6", s0d0; "7", s2d1; "8", s4d2; "9", s6d3. -s4d8: "0", s8d4; "1", s0d5; "2", s2d6; "3", s4d7; "4", s6d8; "5", s9d9; "6", s1d0; "7", s3d1; "8", s5d2; "9", s7d3. -s4d9: "0", s9d4; "1", s1d5; "2", s3d6; "3", s5d7; "4", s7d8; "5", s0d9; "6", s2d0; "7", s4d1; "8", s6d2; "9", s8d3. -s5d0: "0", s0d5; "1", s2d6; "2", s4d7; "3", s6d8; "4", s8d9; "5", s1d0; "6", s3d1; "7", s5d2; "8", s7d3; "9", s9d4; . -s5d1: "0", s1d5; "1", s3d6; "2", s5d7; "3", s7d8; "4", s9d9; "5", s2d0; "6", s4d1; "7", s6d2; "8", s8d3; "9", s0d4. -s5d2: "0", s2d5; "1", s4d6; "2", s6d7; "3", s8d8; "4", s0d9; "5", s3d0; "6", s5d1; "7", s7d2; "8", s9d3; "9", s1d4. -s5d3: "0", s3d5; "1", s5d6; "2", s7d7; "3", s9d8; "4", s1d9; "5", s4d0; "6", s6d1; "7", s8d2; "8", s0d3; "9", s2d4. -s5d4: "0", s4d5; "1", s6d6; "2", s8d7; "3", s0d8; "4", s2d9; "5", s5d0; "6", s7d1; "7", s9d2; "8", s1d3; "9", s3d4. -s5d5: "0", s5d5; "1", s7d6; "2", s9d7; "3", s1d8; "4", s3d9; "5", s6d0; "6", s8d1; "7", s0d2; "8", s2d3; "9", s4d4. -s5d6: "0", s6d5; "1", s8d6; "2", s0d7; "3", s2d8; "4", s4d9; "5", s7d0; "6", s9d1; "7", s1d2; "8", s3d3; "9", s5d4. -s5d7: "0", s7d5; "1", s9d6; "2", s1d7; "3", s3d8; "4", s5d9; "5", s8d0; "6", s0d1; "7", s2d2; "8", s4d3; "9", s6d4. -s5d8: "0", s8d5; "1", s0d6; "2", s2d7; "3", s4d8; "4", s6d9; "5", s9d0; "6", s1d1; "7", s3d2; "8", s5d3; "9", s7d4. -s5d9: "0", s9d5; "1", s1d6; "2", s3d7; "3", s5d8; "4", s7d9; "5", s0d0; "6", s2d1; "7", s4d2; "8", s6d3; "9", s8d4. -s6d0: "0", s0d6; "1", s2d7; "2", s4d8; "3", s6d9; "4", s8d0; "5", s1d1; "6", s3d2; "7", s5d3; "8", s7d4; "9", s9d5; . -s6d1: "0", s1d6; "1", s3d7; "2", s5d8; "3", s7d9; "4", s9d0; "5", s2d1; "6", s4d2; "7", s6d3; "8", s8d4; "9", s0d5. -s6d2: "0", s2d6; "1", s4d7; "2", s6d8; "3", s8d9; "4", s0d0; "5", s3d1; "6", s5d2; "7", s7d3; "8", s9d4; "9", s1d5. -s6d3: "0", s3d6; "1", s5d7; "2", s7d8; "3", s9d9; "4", s1d0; "5", s4d1; "6", s6d2; "7", s8d3; "8", s0d4; "9", s2d5. -s6d4: "0", s4d6; "1", s6d7; "2", s8d8; "3", s0d9; "4", s2d0; "5", s5d1; "6", s7d2; "7", s9d3; "8", s1d4; "9", s3d5. -s6d5: "0", s5d6; "1", s7d7; "2", s9d8; "3", s1d9; "4", s3d0; "5", s6d1; "6", s8d2; "7", s0d3; "8", s2d4; "9", s4d5. -s6d6: "0", s6d6; "1", s8d7; "2", s0d8; "3", s2d9; "4", s4d0; "5", s7d1; "6", s9d2; "7", s1d3; "8", s3d4; "9", s5d5. -s6d7: "0", s7d6; "1", s9d7; "2", s1d8; "3", s3d9; "4", s5d0; "5", s8d1; "6", s0d2; "7", s2d3; "8", s4d4; "9", s6d5. -s6d8: "0", s8d6; "1", s0d7; "2", s2d8; "3", s4d9; "4", s6d0; "5", s9d1; "6", s1d2; "7", s3d3; "8", s5d4; "9", s7d5. -s6d9: "0", s9d6; "1", s1d7; "2", s3d8; "3", s5d9; "4", s7d0; "5", s0d1; "6", s2d2; "7", s4d3; "8", s6d4; "9", s8d5. -s7d0: "0", s0d7; "1", s2d8; "2", s4d9; "3", s6d0; "4", s8d1; "5", s1d2; "6", s3d3; "7", s5d4; "8", s7d5; "9", s9d6; . -s7d1: "0", s1d7; "1", s3d8; "2", s5d9; "3", s7d0; "4", s9d1; "5", s2d2; "6", s4d3; "7", s6d4; "8", s8d5; "9", s0d6. -s7d2: "0", s2d7; "1", s4d8; "2", s6d9; "3", s8d0; "4", s0d1; "5", s3d2; "6", s5d3; "7", s7d4; "8", s9d5; "9", s1d6. -s7d3: "0", s3d7; "1", s5d8; "2", s7d9; "3", s9d0; "4", s1d1; "5", s4d2; "6", s6d3; "7", s8d4; "8", s0d5; "9", s2d6. -s7d4: "0", s4d7; "1", s6d8; "2", s8d9; "3", s0d0; "4", s2d1; "5", s5d2; "6", s7d3; "7", s9d4; "8", s1d5; "9", s3d6. -s7d5: "0", s5d7; "1", s7d8; "2", s9d9; "3", s1d0; "4", s3d1; "5", s6d2; "6", s8d3; "7", s0d4; "8", s2d5; "9", s4d6. -s7d6: "0", s6d7; "1", s8d8; "2", s0d9; "3", s2d0; "4", s4d1; "5", s7d2; "6", s9d3; "7", s1d4; "8", s3d5; "9", s5d6. -s7d7: "0", s7d7; "1", s9d8; "2", s1d9; "3", s3d0; "4", s5d1; "5", s8d2; "6", s0d3; "7", s2d4; "8", s4d5; "9", s6d6. -s7d8: "0", s8d7; "1", s0d8; "2", s2d9; "3", s4d0; "4", s6d1; "5", s9d2; "6", s1d3; "7", s3d4; "8", s5d5; "9", s7d6. -s7d9: "0", s9d7; "1", s1d8; "2", s3d9; "3", s5d0; "4", s7d1; "5", s0d2; "6", s2d3; "7", s4d4; "8", s6d5; "9", s8d6. -s8d0: "0", s0d8; "1", s2d9; "2", s4d0; "3", s6d1; "4", s8d2; "5", s1d3; "6", s3d4; "7", s5d5; "8", s7d6; "9", s9d7; . -s8d1: "0", s1d8; "1", s3d9; "2", s5d0; "3", s7d1; "4", s9d2; "5", s2d3; "6", s4d4; "7", s6d5; "8", s8d6; "9", s0d7. -s8d2: "0", s2d8; "1", s4d9; "2", s6d0; "3", s8d1; "4", s0d2; "5", s3d3; "6", s5d4; "7", s7d5; "8", s9d6; "9", s1d7. -s8d3: "0", s3d8; "1", s5d9; "2", s7d0; "3", s9d1; "4", s1d2; "5", s4d3; "6", s6d4; "7", s8d5; "8", s0d6; "9", s2d7. -s8d4: "0", s4d8; "1", s6d9; "2", s8d0; "3", s0d1; "4", s2d2; "5", s5d3; "6", s7d4; "7", s9d5; "8", s1d6; "9", s3d7. -s8d5: "0", s5d8; "1", s7d9; "2", s9d0; "3", s1d1; "4", s3d2; "5", s6d3; "6", s8d4; "7", s0d5; "8", s2d6; "9", s4d7. -s8d6: "0", s6d8; "1", s8d9; "2", s0d0; "3", s2d1; "4", s4d2; "5", s7d3; "6", s9d4; "7", s1d5; "8", s3d6; "9", s5d7. -s8d7: "0", s7d8; "1", s9d9; "2", s1d0; "3", s3d1; "4", s5d2; "5", s8d3; "6", s0d4; "7", s2d5; "8", s4d6; "9", s6d7. -s8d8: "0", s8d8; "1", s0d9; "2", s2d0; "3", s4d1; "4", s6d2; "5", s9d3; "6", s1d4; "7", s3d5; "8", s5d6; "9", s7d7. -s8d9: "0", s9d8; "1", s1d9; "2", s3d0; "3", s5d1; "4", s7d2; "5", s0d3; "6", s2d4; "7", s4d5; "8", s6d6; "9", s8d7. -s9d0: "0", s0d9; "1", s2d0; "2", s4d1; "3", s6d2; "4", s8d3; "5", s1d4; "6", s3d5; "7", s5d6; "8", s7d7; "9", s9d8; . -s9d1: "0", s1d9; "1", s3d0; "2", s5d1; "3", s7d2; "4", s9d3; "5", s2d4; "6", s4d5; "7", s6d6; "8", s8d7; "9", s0d8. -s9d2: "0", s2d9; "1", s4d0; "2", s6d1; "3", s8d2; "4", s0d3; "5", s3d4; "6", s5d5; "7", s7d6; "8", s9d7; "9", s1d8. -s9d3: "0", s3d9; "1", s5d0; "2", s7d1; "3", s9d2; "4", s1d3; "5", s4d4; "6", s6d5; "7", s8d6; "8", s0d7; "9", s2d8. -s9d4: "0", s4d9; "1", s6d0; "2", s8d1; "3", s0d2; "4", s2d3; "5", s5d4; "6", s7d5; "7", s9d6; "8", s1d7; "9", s3d8. -s9d5: "0", s5d9; "1", s7d0; "2", s9d1; "3", s1d2; "4", s3d3; "5", s6d4; "6", s8d5; "7", s0d6; "8", s2d7; "9", s4d8. -s9d6: "0", s6d9; "1", s8d0; "2", s0d1; "3", s2d2; "4", s4d3; "5", s7d4; "6", s9d5; "7", s1d6; "8", s3d7; "9", s5d8. -s9d7: "0", s7d9; "1", s9d0; "2", s1d1; "3", s3d2; "4", s5d3; "5", s8d4; "6", s0d5; "7", s2d6; "8", s4d7; "9", s6d8. -s9d8: "0", s8d9; "1", s0d0; "2", s2d1; "3", s4d2; "4", s6d3; "5", s9d4; "6", s1d5; "7", s3d6; "8", s5d7; "9", s7d8. -s9d9: "0", s9d9; "1", s1d0; "2", s3d1; "3", s5d2; "4", s7d3; "5", s0d4; "6", s2d5; "7", s4d6; "8", s6d7; "9", s8d8.
Here's what a parse of 8862 looks like:
<cc>
<s0d0>8
<s7d8>8
<s5d5>6
<s8d1>2
<s5d0/>
</s8d1>
</s5d5>
</s7d8>
</s0d0>
</cc>
and 32862
<cc>
<s0d0>3
<s6d3>2
<s7d8>8
<s5d5>6
<s8d1>2
<s5d0/>
</s8d1>
</s5d5>
</s7d8>
</s6d3>
</s0d0>
</cc>
Note that the resulting grammar is LL1:
This talk covers a number of issues:
(There is a full paper online.)