More PEG Practices

In my previous blog post, I introduced PEG to everyone. However, perhaps I didn’t provide very practical examples that people commonly use. Also, there were probably too many technical terms in the last post, which interested readers could find interesting, but others may have just liked it and moved on. So in this post, I want to provide two more examples. The first example is to validate whether a Chinese mainland ID card number conforms to the rules. In my experience, many people have matched it in some way.

Among all the options people have, regular expressions are probably the most commonly used matching method. For the completeness of this article, here is a regular expression for an 18-digit ID number:

^[1-9]\d{5}(19|20)\d{2}((0[1-9])|(1[0-2]))(([0-2][1-9])|10|20|30|31)\d{3}[0-9Xx]$

Regular expressions have one feature — they are easier to write than to read. Of course, for people who don’t have the skill of regular expressions, both may not be easy. And copying and pasting from the internet is often the way to cope with such work. The more complex the regex written by the person who seems very capable online, the more reliable it is generally considered. However, this is ultimately not as reassuring as understanding it yourself before using it.

This regex will match

• Starting with 1–9, followed by five digits
• Year of birth between 1900–2099
• The last four digits are 3 digits followed by a check digit, which is 0–9 or X

ID card numbers. Such a simple logic is written as a regular expression, which takes up 81 characters. Of course I’m not saying it’s long, it’s not long, it’s just a bit information dense. Perhaps you’ve heard that some programming languages in this world don’t need spaces between tokens, and regular expressions are a kind that you can’t add spaces even if you want to.

However, as you can see, since the logic of the above regex is quite simple, the matching rules for ID cards are not very strict. For example,

100000190001010000

This obviously fake ID card, which even a complete programming novice can randomly generate, can easily pass. In some application scenarios, this may not meet the user’s needs.

In practice, my colleague has used over 100 lines of code to validate ID cards more strictly. But with PEG, perhaps it retains the conciseness of regular expressions while having better extensibility. Let’s take a look at my code:

re = require('re')

arr_int = { 7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2 } 
arr_ch = { '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2', '1' }

defs = {
  parity = function(_, pos, p1, p2)
    local tbl = { p1:byte(1, 17) }
    local total = 0
    for i = 1, 17 do
      total = total + arr_int[i] * (tbl[i] - 48)
    end
    return arr_ch[total % 11] == p2
  end
}

idcard = re.compile([[
  idcard <- ({ prov %d^4 date %d^3 } { [0-9] / 'X' }) => parity !.
  prov   <- '1' [1-5] / '2' [1-3] / '3' [1-7] / '4' [1-6] 
            / '5' [1-4] / '6' [1-5]
  date   <- year month day
  year   <- ('19' / '20') %d^2  
  month  <- '0' [1-9] / '1' [0-2]
  day    <- '0' [1-9] / [12] %d / '3' [01]
]], defs)

To be honest, I’ve always hoped for a pattern matching that can use regex for a while, use functions for a while, and backtrack when needed. PEG just happens to meet my expectations.

In the above code, it can be easily seen that the first 17 digits of the idcard grammar are captured, and the last 1 digit is captured in another capture, then a match-time capture is done with these two captures, passed to the parity function to determine if the capture was truly successful. The parity function is just the function familiar to everyone to calculate the last digit from the first 17 digits of the ID card and compare it with the actual last digit.

Compared to regular expressions, LPeg is like a professional typesetting tool (such as Adobe InDesign) compared to Microsoft Word. What I mean is that using the former to match strings is actually a bit of a waste, but its convenience in matching complex rules is self-evident.

The first example is a warm-up. The second example is an interesting task I came across recently, which is to parse Chinese numerals. Recently in the programmer community, a repo that has attracted widespread attention from everyone is the nascent Classical Chinese programming language. Parsing Chinese numbers is one of the components, and it looks simple but is not simple. In this example I did not implement full rule judgments either, and only limited to integers.

re = require('re')

num_defs = {
  digits = {
    ['零'] = 0,  ['一'] = 1,  ['二'] = 2,  ['三'] = 3,  ['四'] = 4,  
    ['五'] = 5,  ['六'] = 6,  ['七'] = 7,  ['八'] = 8,  ['九'] = 9
  },
  mults4 = { ['萬'] = 10000, ['億'] = 100000000, ['兆'] = 1e12, ['京'] = 1e16,
    ['垓'] = 1e20, ['秭'] = 1e24, ['穰'] = 1e28, ['溝'] = 1e32,
    ['澗'] = 1e36, ['正'] = 1e40, ['載'] = 1e44, ['極'] = 1e48 },
  sen   = function(v) return 1000 * v end,
  hyaku = function(v) return 100 * v end,
  juu   = function(v) return 10 * v end,
  add   = function (a, b) return a + b end,
  tmul  = function (a, b) return { a == '' and b or a*b, b, a } end,
  tadd  = function (a, b) 
    local res = { 0, b[2], 0 }
    if a[2] > b[2] then
      res[1] = a[1] + b[1] 
    elseif b[3] == '' then
      res[1] = a[1] * b[2]
    else
      res[1] = a[1] * b[2] + b[1]
    end
    return res
  end,
  elem1 = function (t) return t[1] end,
  one   = function () return 1 end,
  minus = function (v) return -v end
}

num = re.compile([[
  int_num     <- (zero -> digits / '負' pos_num -> minus / pos_num) !.
  pos_num     <- (digit_group+ ~> tadd -> elem1 small_num? / small_num) ~> add
  digit_group <- ((small_num / {''}) mult4) ~> tmul 
  small_num   <- zero? four_digit ~> add
  four_digit  <- start_digit -> sen   '千' (zero two_digit / three_digit)? / three_digit
  three_digit <- start_digit -> hyaku '百' (zero one_digit / two_digit)? / two_digit
  two_digit   <- start_digit -> juu   '十' one_digit? / one_digit
  one_digit   <- nonzero
  zero        <- '零'
  start_digit <- nonzero / '' -> one
  mult4       <- ('萬'/'億'/'兆'/'京'/'垓'/'秭'/'穰'/'溝'/'澗'/'正'/'載'/'極') -> mults4
  nonzero     <- ('一'/'二'/'三'/'四'/'五'/'六'/'七'/'八'/'九') -> digits
]], num_defs)

If this num grammar matches successfully, it will return the corresponding Arabic numerals for the Chinese numerals. The only slightly special part of this program is the use of cascading capture — which is really just reduce, the familiar concept in functional programming. It is represented by ~> (the tilde is a wave line) in LPeg.

Simply matching Chinese numerals is not difficult, but paying close attention to details is not easy. For example, the placeholder of “零”, 百 cannot be placed before 千, and 万 can be placed before 亿. Some complex rules added in require finer matching.

I wrote rules for each of the thousands, hundreds, tens and single digits so that the small_num rules can be as strict as possible. Smaller units simply cannot be placed before larger units, zeros cannot be too many but can be omitted:

一百一(101)  
一百零一十(match failure)
千百(1100)
百二十(120)

For 10,000 and above, a set of compound rules is required, adding a small_num and a large unit (万, 亿, etc.) as a digit_group to match. A group is really just a multiplication operation inside, but not exactly like that. For example, "億萬" should be interpreted as 100 million. But this omission of the "一" is subtle, because "萬億" should be interpreted as 10^12, which does not add an omitted "一" at the 亿. So I just capture the omitted "一" position as an empty string, and leave it to the tmul function to process. tmul is not a simple multiplication, it will record the result, the two multiplied numbers in a table after multiplying.

The addition of multiple tables uses the tadd function to carefully add, while retaining the unit information after multiplication, performing a reduce operation. The "carefully" is that you need to determine the units of the two, the former unit is small, it is multiplied; the former unit is large, it is added. In addition, a small point to note is that since the addition of all is still a table, I later use the function capture elem1 to get the result, and then simply add with other ordinary numbers.

Through these two examples, I believe everyone’s understanding of PEG should be closer. The diverse captures are also a feature of LPeg, if it only supports simple captures, it would be difficult to achieve complex functionality. The code for the two examples above is also included in a repo I just created recently: brynne8/lpeg_patterns. Everyone is welcome to share and discuss.