Lập trình shell

Biểu thức chính qui (Regular Expression)

Nguyễn Hải Châu (nhchau@gmail.com)
Trường Đại học Công nghệ, ĐHQGHN

Định nghĩa biểu thức chính qui

  • Một biểu thức chính qui là một chuỗi ký tự chứa các ký tự bình thường và các ký tự đặc biệt:
    • Các ký tự bình thường mô tả chính các ký tự đó
    • Các ký tự đặc biệt mô tả các nhóm ký tự và tính chất kèm theo như: số lượng ký tự trong nhóm, vị trí ký tự hoặc kiểu ký tự
  • So khớp mẫu (pattern matching) là việc tìm các nhóm ký tự được mô tả bởi một biểu thức chính qui

Các loại engine của biểu thức chính qui

  • Có hai loại engine chính của biểu thức chính qui: DFA (Deterministic Finite Automaton) và NFA (Nondeterministic Finite Automaton). DFA thường nhanh hơn nhưng thiếu một số tính năng so với NFA
  • NFA được chia thành hai kiểu chính: truyền thống và POSIX
  • DFA so sánh mỗi ký tự của dữ liệu vào với biểu thức chính qui (viết tắt REGEX). Do mỗi ký tự được so sánh nhiều nhất một lần nền DFA có tốc độ thực hiện cao
  • NFA truyền thống và POSIX: So sánh mỗi phần tử của REGEX với dữ liệu vào

Ký tự đặc biệt trong REGEX

  • Viết tắt ký tự đặc biệt: Một số ký tự đặc biệt được viết tắt:
    • \n = ký tự xuống dòng (mã ASCII=10 trong UNIX/Linux hoặc mã ASCII=13 trong Windows)
    • \b thường dùng với ký tự backspaceword boundary (phân cách từ): Nhập nhằng
  • Biểu diễn ký tự qua số hệ 8: \ooo trong đó ooo là một số nguyên viết ở hệ 8, ví dụ `\012'
  • Tương tự có thể biểu diễn ký tự hệ 16: \xnum, \x{num} và Unicode \unum, u{num}, ví dụ \x12, \u1234
  • Các ký tự điều khiển: \cchar, ví dụ \cH = Control-H

Nhóm ký tự

  • Nhóm ký tự trong REGEX được chỉ ra như sau:
    • Nhóm thông thường: [...]: Một trong các ký tự nằm trong cặp dấu [][^...]: các ký tự không phải là các ký tự nằm trong cặp []
    • .: Bất kỳ ký tự nào không phải là ký tự xuống dòng
    • Một số nhóm ký tự có thể viết tắt: \w (một từ), \d (số), \s (dấu trắng) và các phủ định tương ứng \W, \D, \S. Lưu ý nhóm ký tự từ có thể khác nhau với các loại ngôn ngữ khác nhau
  • Nhóm ký tự theo POSIX: [:xxx:], trong đó xxx có thể nhận các giá trị:
    • Alnum: Chữ và số
    • Alpha: Chữ
    • Blank: Dấu trắng hoặc tab
    • Cntrl: Ký tự điều khiển

Nhóm ký tự (tiếp)

  • Nhóm ký tự theo POSIX: [:xxx:], trong đó xxx có thể nhận các giá trị:
    • Digit, Xdigit: Các số hệ 10, 16
    • Lower, Upper: Chữ viết thường, viết hoa
    • Graph, Print: Các ký tự in được, bao gồm (không bao gồm) dấu trắng
    • Punct: Các ký tự in được, trừ chữ và số
    • Space: Dấu trắng
  • Nhóm ký tự Unicode: \p{properties}, \P{properties}, trong đó properties là:
    • L: Chữ
    • Ll: Chữ thường, Lu: Chữ hoa
    • N: Số

So khớp vị trí ký tự

  • Anchors và *zero-width assertions` dược dùng để định nghĩa/so khớp vị trí các ký tự, nhóm ký tự:
    • Bắt đầu một dòng/chuỗi: ^, \A
    • Kết thúc một dòng/chuỗi: $, \Z, \z (phụ thuộc bản cài đặt)
    • Bắt đầu vị trị khớp/tìm thấy: \G
    • Ngăn cách từ: \b, \B (phủ định của \b), \<, \>
  • Cấu trúc lookaround:
    • Lookahead: (?=...) và phủ định (?!...).
    • Lookbehind: (?<=...) và phủ định (?<!...)
    • Ví dụ: foo(?bar) tìm foo trong foobar nhưng không trong food

Thay đổi chế độ làm việc

  • i: Không phân biệt chữ hoa, thường: (?i:bash) sẽ khớp với bash, Bash, BASH...
  • x: Cho phép các khoảng trắng và comment trong biểu thức chính qui. Ví dụ: (?#...) = comment và #: Từ vị trí sau đó đến cuối dòng = comment
  • s: Cho phép . khớp được với dấu ngăn cách dòng

Gộp nhóm, tham chiếu nhóm, điều kiện và điều khiển

  • Cặp () có tác dụng gộp nhóm và tham chiếu:
    • Các ký tự được khớp với phần REGEX trong cặp () sẽ được "bắt" và được tham chiếu để sử dụng sau đó. Các nhóm được đánh số từ 1, 2, ... bắt đầu từ dấu ( ngoài cùng bên trái và được tham chiếu là \1, \2...
    • Gộp nhóm, không tham chiếu: (?:)
    • Gộp nhóm tham chiếu theo tên: (?<name>...)
  • Điều kiện: (?(if)then |else)
  • Lượng từ: *, +, ?, {n, m}:
    • *: Lặp lại 0 đên n lần
    • +: Lặp lại 1 đến n lần
    • {n, m}: Lặp lại từ n đến m lần

Một số use-case của biểu thức chính qui (1)

  • Xóa dấu trắng ở đầu dòng:
    • sed: 's/^\s\+//'
    • grep: '^\s\+'
  • Xóa dấu trắng ở cuối dòng:
    • sed: 's/\s\+$//'
    • grep: '\s\+$'
  • Lưu ý:
    • sedgrep cần đưa \+ để hiểu là + (lặp lại ít nhất 1 lần)
    • awk chỉ cần +

Một số use-case của biểu thức chính qui (2)

  • Tìm số nguyên từ 0 đến 999999:
    • sed: '/[0-9]\{1,6\}/p' dùng với option -n
    • grep: '[0-9]\{1,6\}'
    • awk: /[0-9]{1,6}/
    • sed, grepawk không hiểu \d là số
  • Tìm chuỗi có dạng đường dẫn thư mục trên Linux:
    • sed: '/.*\//p' dùng với option -n
    • grep: '.*/'
    • awk: /.*\//
  • Lưu ý: awk dùng được {} nhưng sedgrep phải dùng \{\}

Một số use-case của biểu thức chính qui (3)

  • Tìm chuỗi có định dạng giờ:phút:giây:
    • sed: '/\s[0-9]\{1,2\}:[0-5]\{1,2\}:[0-9]\{1,2\}\s/p'
    • grep: \s[0-9]\{1,2\}:[0-5]\{1,2\}:[0-9]\{1,2\}\s
    • awk: /\s[0-9]{1,2}:[0-5]{1,2}:[0-9]{1,2}\s/
  • Tìm các địa chỉ email:
    • sed: '/\w[a-zA-Z]\([a-zA-Z0-9_+]\)\+@\([_a-zA-Z][a-zA-Z0-9+_-]\+\.\)\+[a-zA-Z]\{2,4\}\w/p'
    • grep: '\w[a-zA-Z]\([a-zA-Z0-9_+]\)\+@\([_a-zA-Z][a-zA-Z0-9+_-]\+\.\)\+[a-zA-Z]\{2,4\}\w'
    • awk: /\w[a-zA-Z]([a-zA-Z0-9_+])+@([_a-zA-Z][a-zA-Z0-9+_-]+\.)+[a-zA-Z]{2,4}\w/

So sánh biểu thức chính qui của sed, grepawk

  • awk sử dụng DFA
  • grep dùng cả DFA và NFA tùy theo ngữ cảnh
  • sed dùng NFA
  • Với các ký tự viết tắt:
    • awksed hỗ trợ: \a, \f, \n, \r, \t, \v, \xhex, \ddecimal, \cchar
    • awk hỗ trợ \b, \octal
    • \sed hỗ trợ \ooctal, \w
    • grep hỗ trợ ^, $, \<, \>, \w
    • Tham khảo Biểu thức chính qui sed, grep, awk
    • Lưu ý: Các phần mềm thường xuyên thay đổi --> Cần thử nghiệm

Công cụ thử nghiệm biểu thức chính qui

  • Công cụ online:
    • http://www.regexpal.com/
    • Cách sử dụng: Đưa vào một văn bản và biểu thức chính qui, kết quả tìm kiếm trong văn bản được highlight
  • Công cụ offline:
    • Phần tìm kiếm của sed, grep, awk
    • Sử dụng hệ soạn thảo vim trên Linux: dùng lệnh tìm kiếm / hoặc thay thế :s của vim và đưa vào các biểu thức chính qui
  • Có thể sử dụng biểu thức chính qui với các ngôn ngữ lập trình thông dụng như PHP, Python, Java, JavaScript

Thực hành biểu thức chính qui

  • Cho file grepdata.txt:
head -6 grepdata.txt
## Sep. 17, 2013
## Esperanza High School
## 1830 N. Kellog Dr.
## Anaheim, CA 92807-1281
## Steve Marshal
## 714-555-7870 X7310
  • 7.1. Hãy tìm các số điện thoại có dạng ddd-ddd-dddd trong file
  • 7.2. Hãy tìm các số điện thoại có dạng ddd-ddd-dddd và có extension (ví dụ x1234)
  • 7.3. Hãy sử dụng biểu thức chính qui và sed để chuyển một file có nhiều dòng dài (longline.txt) thành file có các dòng với độ dài nhỏ hơn hoặc bằng một giá trị cho trước, chẳng hạn 70 ký tự

Thực hành biểu thức chính qui

  • 7.4. Hãy tìm các số điện thoại dạng dddddddddd trong file tel.csv và in ra nhóm ddd bắt đầu từ vị trí thứ 4 (vị trí đầu là 1)
  • 7.5. Hãy thay đổi tham chiếu [1], [2]... trong một file thành tham chiếu dạng LaTeX \cite{1}, \cite{2}...
  • 7.6. Tải nội dung của một trang web và in ra danh sách các ảnh của trang web có trong thẻ <img>. Sử dụng ứng dụng wget để tải nội dung trang web.

Tài liệu tham khảo

  1. J .E. F. Friedl, Mastering regular expression 3rd edition, O'Reilly, 2006.