Giới thiệu tính năng parser combinator của Scala
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, đó là (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 còn 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 là gì?
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 scala
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 đó là sau khi parse được cái gì nên convert ngay cái đó. Vì convert từng chú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".
>> Tham khảo thêm: Chiêu thức DefaultsTo trong Scala
