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 đó, left và right 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ụ:

tuple(): nhận vào một tuple gồm nhiều parser khác nhau, và trả về một tuple với các giá trị trả về theo thứ tự tương ứng.
alt(): nhận vào một tuple gồm nhiều parser khác nhau, và trả về một giá trị duy nhất ứng với một trong các parser đầu vào.
tag(): nhận vào một string slice và trả về giá trị ứng với nội dung input.

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

Đầu tiên, parser tuple((...)) sẽ chạy, nhận vào input là "10*6", bắt đầu gọi từng parser bên trong nó.
Parser thứ nhất, là parse_number nhận vào input "10*6", và match được 2 ký tự "10", chuyển nó thành kiểu i32 là 10, trả về một tuple có dạng ("*6", 10), trong đó "*6" là phần input còn thừa, sẽ được truyền tiếp vào parser tiếp theo.
Tiếp theo, parser alt((...)) sẽ nhận vào input "*6" và chạy từng parser bên trong nó:
- tag("+") sẽ fail, không match được gì cả
- Tiếp theo, tag("-") cũng fail luôn
- Đến tag("*") thì match được ký tự "*"
- Thế là alt((...)) hoàn thành, trả về tuple có giá trị là ("6", "*") để chuẩn bị truyền vô parser tiếp theo.
Cuối cùng, parse_number thứ 2 sẽ nhận vào input "6" và match toàn bộ nó, chuyển thành kiểu i32 là 6, trả về tuple ("", 6).
Mọi parser bên trong đã hoàn thành, lúc này parser tuple((...))sẽ tổng hợp các kết quả đã match được và trả về một tuple có dạng ("", (10, "*", 6)). Trong đó, chuỗi rỗng "" là phần còn lại của input, còn tuple (10, "*", 6) chính là nội dung chúng ta đã match được.

Đế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