To reduce the likelihood of typographic errors, the digits comprising most
credit card numbers are designed to satisfy the so-called Luhn formula, standardized by ANSI in the 1960s, and named for IBM mathematician Hans
Peter Luhn. Starting at the right, we double every other digit (the secondto-last, fourth-to-last, etc.). If the doubled value is 10 or more, we add the
resulting digits. We then sum together all the digits. In any valid number
the result will be a multiple of 10. For example, 1234 5678 9012 3456
becomes 2264 1658 9022 6416, which sums to 64, so this is not a valid
number. If the last digit had been 2, however, the sum would have been 60,
so the number would potentially be valid.
Give an attribute grammar for strings of digits that accumulates into the
root of the parse tree a Boolean value indicating whether the string is valid
according to Luhn’s formula. Your grammar should accommodate strings
of arbitrary length.