We can express
this in an ixml grammar. The grammar accepts a series of numbers, which all
have to be divisible by three. Steven Pemberton, CWI, Amsterdam
Version: 2026-02-13.
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 paper 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, albeit complex, syntax.
The paper 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.
Cite as: Steven Pemberton, The Syntax of Credit Card Numbers, First International Invisible XML Symposium, Amsterdam, 2026.
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.
To show how this works, let us consider a simple example: an easy check to see if a number is divisible by 3 is to see if the sum of its digits is also divisible by three. The number 783 is divisible by three because the sum of its digits are 7+8+3=18, and 18 is divisible by 3 because 1+8=9, which is divisible by 3.
We can visualise how you can check this on the fly, by considering the effect of each digit in the number, working from left or right (it doesn't matter which): from the start state, if the first character is a 0, 3, 6, or 9, then you go into state 0, which is the state that represents the fact that the characters that you have met so far considered as a number is divisible by 3 (with remainder 0). If on the other hand the first character is 1, 4, or 7, then you enter State 1 which represents the number so far being divisible by 3, with remainder 1. Similarly, if the first character is a 2, 5, or 8, you enter State 2, representing a number divisible by 3, with 2 remaining.
From any state, if the next character is a 0, 3, 6, or 9, you remain in that state. However, from State 1, a 1, 4, or 7 will take you to State 2 (for instance 11 divided by 3 is 3, remainder 2). From State 2 a 1, 4, or 7 will take you to State 0 (for instance 21), and so on.
As a diagram it looks like this. You start in state 0, and aim to end up in State 0:
We can express
this in an ixml grammar. The grammar accepts a series of numbers, which all
have to be divisible by three.
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.
An output would look like:
<input> <div3>3</div3> <div3>39</div3> <div3>285</div3> <div3>123</div3> </input>
If one of the values was not divisible by 3, you would 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>
We can rewrite the grammar to classify inputs into good and bad classes,
since they are mutually exclusive. 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>
This example has 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.
This works slightly differently, effectively by dividing the number represented by the digits left-to-right, and only keeping the remainder. So "9" divided by 7 is 1 remainder 2, so we go into state 2; if the next character is another "9", then we are dividing 29 by 7, which is 4 remainder 1, so we go into state 1; if it had been an "8" then we go into state 0, and can conclude that "98" is divisible by 7; and so on.
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, with the difference that the sum is done in a different way: 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. So for even-numbered digits these are the transformations for the addition:
0→0, 1→2, 2→4, 3→6, 4→8, 5→10→1, 6→12→3, 7→14→5, 8→16→7, 9→18→9.
Since there are ten digits, and it is working modulo ten, this algorithm 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), thus allowing a small amount of client-side validity checking, before doing any lookup on the remote database.
There seems to be no indication why the algorithm is specified right-to-left, rather than left-to-right; one plausible explanation is that 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.
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
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 (or 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 other 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>
Unfortunately 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, as we have already
seen in the div3 example, but the problem is, working left to
right 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 one of them 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 individual rules look like the following. 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).
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 create a single left-to-right parse, by
merging the two parses above, where each state represents 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 would keep us in
s0d0, but a 1 would take us to s2d1, and a 2 to
s4d2, and so on; at each character the sum swaps to the other
side, 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; .
All 100 rules of the whole grammar looks like this (it was 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 this grammar is LL1, so it doesn't need a general parser like that of ixml. It also means that it runs in time linear in the length of the string.
This paper covers a number of issues: that certain arithmetic properties of
a number can be seen as, and treated as, syntactic; that credit card numbers
have an internal, albeit complicated, syntax, that despite its complications is
still LL1; and that parsing right to left is possible with a general parsing
algorithm by writing the syntax rules back to front.
[Luhn] Annex B of ISO/IEC 7812-1