Nom Parser và Parser Combinator

Parsing là kĩ thuật phân tích cú pháp để trích xuất thông tin và chuyển đổi một tập dữ liệu cho trước về một dạng dữ liệu có cấu trúc để dễ làm việc hơn.

Có rất nhiều kĩ thuật parsing khác nhau, trong bài này chúng ta nói về kĩ thuật Parser Combinator, chi tiết các bạn đọc trong Wikipedia.

Hiểu nôm na Parser Combinator là kĩ thuật kết hợp nhiều parser nhỏ lại với nhau theo một quy tắc nào đó để có thể parse một nội dung lớn hơn và phức tạp hơn. Quy tắc dùng để kết hợp các parser nhỏ được đưa ra dựa trên cú pháp của nội dung đầu vào. Việc chia thành nhiều parser nhỏ hơn như thế này cũng giúp chúng ta sử dụng lại code tốt hơn và dễ dàng thực hiện unit test hơn.

Nom là một thư viện cung cấp cho chúng ta rất nhiều công cụ để kết hợp và build parser sử dụng kĩ thuật Parser Combinator. Ưu điểm của Nom đó là nhanh và an toàn, nhờ vào khả năng hạn chế cấp phát bộ nhớ (từ thao tác copy string).

Khi sử dụng Nom, một parser sẽ là một hàm nhận vào một dữ liệu kiểu I, và trả về một dữ liệu kiểu nom::IResult<I, O, E> trong đó E là kiểu dữ liệu cho thông báo lỗi. Trong một số trường hợp, ta có thể bỏ qua kiểu E, và viết thành nom::IResult<I, O>. Nội dung trả về sẽ là một tuple có dạng (I, O), với I là nội dung còn thừa sau khi chạy parser, và O là kết quả sau khi trích xuất nội dung.

Ví dụ parser sau đây trích xuất các kí tự số trong một string slice, chuyển nó thành kiểu i32 rồi trả về phần còn thừa:

fn parse_number(input: &str) -> IResult<&str, i32> {
    map_res(digit1, |c: &str| c.parse::<i32>()).parse(input)
}

let (left_over, number) = parse_number("123abc")?;
// left_over = "abc"
// number = 123

Ở đây, hàm digit1 là một parser do Nom cung cấp, có chức năng match tất cả các kí tự số có trong chuỗi, hàm map_res(P, Fn) được dùng để truyền kết quả trả về từ parser P vào hàm Fn để lấy ra một giá trị mới. Ở đây ta truyền kết quả parse từ digit1 vào một closure để convert về kiểu i32.

Ta có thể sử dụng hàm parse_number để phát triển thành một parser mới phức tạp hơn, ví dụ viết một parser để phân tích một biểu thức dạng "A+B", ”A-B”, ”A*B” hoặc ”A/B”.

Trước khi viết code, chúng ta sẽ phân tích một tí, các biểu thức trên sẽ có dạng chung gồm 3 thành phần, như bảng sau:

Left Operator Right
10 + 3
9 - 5
2 * 3
6 / 2

Trong đó, leftright là các kí tự số, có thể parse bằng hàm parse_number đã viết ở trên. Còn operator sẽ là một trong 4 kí tự ”+”, ”-”, ”*” hoặc ”/”. Quy tắc kết hợp của biểu thức cần parse sẽ là:

left + (+ - * /) + right

Để cho đơn giản, ta có thể bỏ qua trường hợp có các khoảng trắng có trong biểu thức. Ta cần viết một hàm parse_expression trả về một tuple có dạng (i32, i32, &str) tương ứng với (left, right, operator).

fn parse_expression(input: &str) -> IResult<&str, (i32, &str, i32)> {
	tuple((
        parse_number,
        alt(( tag("+"), tag("-"), tag("*"), tag("/") )),
        parse_number
   )).parse(input)
}

Ở trong đoạn code trên, chúng ta sử dụng các parser mà Nom đã build sẵn, ví dụ:

Chạy thử với biểu thức 10*6, việc parsing diễn ra theo thứ tự như sau:

Đến khúc này nhiều bạn sẽ hỏi là: làm sao để biết được có những parser nào mà xài, và lúc nào nên sử dụng parser có sẵn, lúc nào build mới? Câu trả lời là tham khảo trang List of parsers and combinators, cái nào có sẵn rồi thì mình xài thôi.

Phần lớn thời gian khi sử dụng Nom, chúng ta sẽ sử dụng các parser build sẵn này rất nhiều, có khi là dùng trực tiếp, nhưng thông thường là để kết hợp nhiều parser lại với nhau tạo thành parser mới.

Hôm nay viết đến đây thôi, ở bài sau chúng ta sẽ ứng dụng Nom để viết parser cho công cụ nhắc việc như Reminder.app của MacOS. Mong các bạn đón đọc.

Tags: rust
    Gõ xong nhấn Ctrl + Enter để gửi. Bạn không thể xóa comment sau khi gửi.