Giới thiệu tính năng parser combinator của Scala
Scala
50
compiler
10
White

Ngoc Dao viết ngày 20/03/2016

Trong bài về Leex và Yecc, chúng ta đã tìm hiểu công cụ cho phép viết tokenizer và parser của Erlang. Trong bài viết này, chúng ta sẽ tìm hiểu sơ lược công cụ tương tự của Scala. Erlang cần đến 2 bước độc lập (1) viết tokenizer, (2) viết parser, còn Scala gộp chúng làm một, tiện hơn. Thậm chí Scala cho phép gộp thêm cả bước compile, thành 3 trong 1 luôn!

Để minh họa, chúng ta sẽ viết chương trình calculator tính kết quả của biểu thức chỉ chứa 2 toán tử cộng và trừ. Ví dụ cho chuỗi: "1 + 2 - 3", kết quả phải ra 0.0. Có thể hiểu là ta compile chuỗi "1 + 2 - 3" thành con số 0.0.

Parser

Trước tiên ta ôn lại khái niệm về parser.

Đầu vào là chuỗi. Tokenizer dựa vào qui định trong grammar nào đó sẽ cắt chuỗi thành chuỗi những token. Token là những phần tử nguyên tố, không thể chia nhỏ được hơn trong grammar. Cũng dựa vào grammar, parser sẽ sắp xếp biến đổi chuỗi token chỉ có cấu trúc 1 chiều thành dữ liệu có cấu trúc thường phức tạp hơn, có hơn 1 chiều.

Mấu chốt vấn đề là, giả sử chương trình viết bằng Scala, tuy cấu trúc phức tạp hơn nhưng đối với chương trình nhưng lại dễ xử lí hơn (ví dụ ở bước compiler) vì cấu trúc này là native trong ngôn ngữ Scala (ví dụ Map, List v.v.).

Ví dụ có chuỗi kí tự JSON (viết căn hàng thẳng lối cho dễ đọc, chứ độc giả cần hiểu dưới đây chỉ là chuỗi kí tự bình thường):

{
  "address book": {
    "name": "John Smith",
    "address": {
      "street": "10 Market Street",
      "city"  : "San Francisco, CA",
      "zip"   : "94111"
    },
    "phone numbers": ["408 338-4238", "408 111-6892"]
  }
}

Sau khi parse:

Map(
"address book" -> Map(
  "name"    -> "John Smith",
  "address" -> Map(
      "street" -> "10 Market Street",
      "city"   -> "San Francisco, CA",
      "zip"    -> "94111"),
  "phone numbers" -> List("408 3384238", "408 1116892")))

Map và List là cấu trúc dữ liệu chuẩn của Scala, nên dữ liệu sau khi parse có cấu trúc dễ xử lí hơn chuỗi kí tự gốc.

Parser combinator

Xây dựng parser thủ công từ con số 0 là bài toán thú vị. Erlang giúp làm việc này dễ hơn bằng công cụ Leex và Yecc. Nhưng xây dựng parser mới bằng cách kết hợp những parser có sẵn lại với nhau (và bổ sung tự viết thêm parser khi cần thiết) như xếp hình LEGO là bài toán thú vị hơn! Công cụ này gọi là parser combinator, trong Scala có sẵn.

Với bài toán calculator đã nêu, ta làm như sau:

import scala.util.parsing.combinator.JavaTokenParsers

object Calculator extends JavaTokenParsers {
  private def op = "+" | "-"

  private def exp = floatingPointNumber ~ rep(op ~ floatingPointNumber) ^^ {
    case number ~ list =>
      // text: "1 + 2 - 3" => list: List((+~2), (-~3))
      println("1: " + list)

      // Convert to numbers
      val numbers = list.map { case o ~ n =>
        if (o == "+") n.toDouble else -n.toDouble
      }
    
      // text: "1 + 2 - 3" => numbers: List(2.0, -3.0)
      println("2: " + numbers)

      number.toDouble + numbers.sum
  }

  def parse(text: String) = {
    val ret = parseAll(exp, text)
    println("3: " + ret)
    if (ret.successful) Some(ret.get) else None
  }
}

println("4: " + Calculator.parse("1 + 2 - 3"))

Mọi thứ công cụ đã có sẵn trong class JavaTokenParser:

  • op biểu diễn token là + hoặc -.
  • a ~ b biểu diễn sau token a sẽ đến token b, a và b đứng liên tiếp nhau.
  • rep biểu diễn phần bên trong có thể lặp đi lặp lại (0, 1, 2... lần).
  • floatingPointNumber biểu diễn số thực, là parser có sẵn trong class JavaTokenParsers.
  • floatingPointNumber ~ rep(op ~ floatingPointNumber) biểu diễn chúng ta sẽ biến đổi ví dụ chuỗi "1 + 2 - 3" thành 2 phần: phần trước là 1 phần tử, phần sau là List các phần tử trong đó toán tử +/- được gắn liền với số đi sau nó.
  • Sau ^^ là hàm biến đổi kết quả trung gian sau khi parse exp. Kết quả của hàm được dùng như kết quả cuối cùng sau khi parse exp.

Chạy sẽ hiện trên màn hình:

1: List((+~2), (-~3))
2: List(2.0, -3.0)
3: [1.10] parsed: 0.0
4: Some(0.0)

Nếu sửa lại để bỏ đi hàm biến đổi:

import scala.util.parsing.combinator.JavaTokenParsers

object Calculator extends JavaTokenParsers {
  private def op = "+" | "-"

  private def exp = floatingPointNumber ~ rep(op ~ floatingPointNumber)

  def parse(text: String) = {
    val ret = parseAll(exp, text)
    println("3: " + ret)
    if (ret.successful) Some(ret.get) else None
  }
}

println("4: " + Calculator.parse("1 + 2 - 3"))

Chạy sẽ ra:

3: [1.10] parsed: (1~List((+~2), (-~3)))
4: Some((1~List((+~2), (-~3))))

Như vậy thay vì parse xong rồi biến đổi tiếp (bước compile), ta có thể nhúng luôn hàm đó vào parser. Kinh nghiệm chung, thì sau khi parse được cái gì nên convert ngay cái đó, convert từng ít một nhìn thoáng, dễ viết, dễ hiểu, dễ debug hơn là dồn lại một cục to đùng rồi mới convert.

Đoạn mã trên mới chỉ xử lí được trường hợp bài toán chỉ chứa cộng và trừ. Hãy thử cải tiến để xử lí cả nhân và chia. Chú ý nhân chia có luật "nhân chia trước cộng trừ sau".

Đọc thêm

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Ngoc Dao

102 bài viết.
300 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
66 8
Làm thế nào để nâng cấp trang web mà không làm gián đoạn dịch vụ? Đây là câu hỏi phỏng vấn các công ty lớn thường hỏi khi bạn xin vào vị trí làm lậ...
Ngoc Dao viết hơn 2 năm trước
66 8
White
42 1
Bài viết này giải thích sự khác khác nhau giữa hai ngành khoa học máy tính (computer science) và kĩ thuật phần mềm (software engineering), hi vọng ...
Ngoc Dao viết hơn 2 năm trước
42 1
White
38 2
Nếu là team leader, giám đốc công ty hay tướng chỉ huy quân đội, vấn đề cơ bản bạn gặp phải là “hướng mọi người đi theo con đường bạn chỉ ra”. Thử...
Ngoc Dao viết hơn 2 năm trước
38 2
Bài viết liên quan
White
10 0
Kí tự Regex cơ bản Về cơ bản thì các sử lý matching của scala.util.matching.Regex sẽ được "phó thác" (delegate) cho java Regex. Bạn có thể tạo một ...
huydx viết hơn 3 năm trước
10 0
White
7 1
Trong scala kí tự _ được dùng với khá nhiều mục đích .. không liên quan đến nhau. Tạm note lại cái đã khi nào có time sẽ quay lại viết cẩn thận sa...
huydx viết hơn 3 năm trước
7 1
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
102 bài viết.
300 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!