Sử dụng parser combinator trên scala (phần 1)
Scala
50
White

huydx viết ngày 27/05/2015

Bài toán

Chắc mọi người cũng đã xem qua bài của bạn @viethnguyen viết về cách sử dụng parser trên haskell. Bài của bạn @viethnguyen khá là nâng cao nên mình viết bài này sẽ kĩ hơn một chút cho người mới bắt đầu.
Bài toán tóm tắt như sau:

cho biểu thức logic
(TRUE AND NOT (TRUE OR FALSE))
Hãy parse và evaluate kết quả biểu thức trên

Bài toán trên có cách làm đơn giản nhất là làm giống như chúng ta đã được học hồi đại học, là biến biểu thức về đảo balan, rồi nhét vào stack, evaluate lần lượt từ trên xuống dưới.
Tuy nhiên cách làm đó không áp dụng được cho nhiều bài toán rộng hơn, nên mình đã tiếp cận với cách sử dụng parser, với công cụ là bộ thư viện parser combinator trên scala.

Parser là gì?

Dịch tiếng Việt một cách thô thiển ra thì parser là "phân tích ngữ pháp". Bài toán parser thường gặp nhất ở những bạn làm compiler.
Mình có một Ví dụ đơn giản:

  • Bạn có một ngữ pháp (hay hiểu đơn giản là "rule" X), ví dụ như là: <mèo sợ chó>
  • Bạn có một dữ liệu đầu vào, giả sử là <catty sợ doggy>, bạn "áp" dữ liệu đầu vào đấy vào rule bạn vừa qui định ở trên, thì bạn có thể suy đoán được catty là mèo còn doggy là chó.

Parser cũng giống như vậy, chỉ đơn giản là bạn "áp" một bộ dữ liệu và một bộ rule, và suy đoán ra rất nhiều thứ.

Vậy Parser dùng để làm gì? Ứng dụng lớn nhất của parser là vào trong việc "dịch" ngôn ngữ, sử dụng cho các compiler. Nếu không có parser thì khi ném một đoạn code C vào máy tính, máy tính sẽ không thể hiểu, đâu là biến, đâu là biểu thức, đúng không :).

BNF

Như ở trên mình đã nói, parser nghĩa là áp dụng một bộ "rule" với dữ liệu đầu vào. Bộ rule đó cũng giống như ngôn ngữ, nghĩa là cần có một bộ kí hiệu để mô tả rule.
Nếu các bạn đã từng học qua compiler sẽ biết về BNF (Backus–Naur Form), đây chính là một bộ kí hiệu dùng nhiều nhất để mô tả rất nhiều các "rule"

Các bạn có thể tìm hiểu kĩ hơn về BNF trên wiki :
http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form

Mình khuyên các bạn nên đọc qua về BNF để hiểu kĩ hơn về đoạn dưới đây

Giải quyết bài toán

Suy nghĩ về BNF

Chúng ta cần có một bộ rule để diễn tả một biểu thức logic dạng như trên:

(TRUE AND NOT (TRUE OR FALSE))

Một biểu thức logic bất kì có thể biểu diễn dưới dạng BNF như sau:

<bool> ::= "TRUE" | "FALSE"
<factor> ::= <bool> | "(" <expr> ")"
<notfactor> ::= "NOT" <factor>
<term> ::= factor | notfactor
<operator> ::= ("AND" | "OR") <term>
<expression> ::= <term> {<operator>}*

Chắc có bạn sẽ hỏi, làm thế nào để suy ra một biểu thức BNF từ yêu cầu về biểu thức logic trên? Các bạn hãy tự thử suy nghĩ nhé, mình sẽ trả lời ở bài viết sau.

Sử dụng scala combinator parser

Bài viết này mình sẽ không đi vào giải thích các khái niệm cơ bản của scala, mà đi luôn vào cách dùng.
Scala combinator parser là một bộ thư viện đi kèm với scala (2.10), và tách riêng thành thư viện độc lập từ 2.11. Bộ thư viện này giúp chúng ta có thể áp những bộ "rule" vào một chuỗi đầu vào một cách cực kì dễ dàng.
https://github.com/scala/scala-parser-combinators

Bộ rule ở đây chính là BNF mà mình vừa nói ở trên. Điều đó tóm tắt lại có nghĩa là gì: bạn có BNF rule, bạn có chuỗi đầu vào, những thứ còn lại hãy để cho thư viện giải quyết :D.

Cụ thể về cách sử dụng mình sẽ viết trong phần tiếp theo :D.

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

huydx

118 bài viết.
1047 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
164 15
Introduction (Link) là một cuộc thi ở Nhật, và cũng chỉ có riêng ở Nhật. Đây là một cuộc thi khá đặc trưng bởi sự thú vị của cách thi của nó, những...
huydx viết 2 năm trước
164 15
White
148 14
Một ngày đẹp trời, bạn quyết định viết một dịch vụ web dự định sẽ làm thay đổi cả thế giới. Dịch vụ của bạn sẽ kết nối tất cả các thiết bị di động ...
huydx viết 2 tháng trước
148 14
White
133 15
Happy programmer là gì nhỉ, chắc ai đọc xong title của bài post này cũng không hiểu ý mình định nói đến là gì :D. Đầu tiên với cá nhân mình thì hap...
huydx viết hơn 3 năm trước
133 15
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
White
1 0
(Bài viết hơi khó hiểu, dành cho bạn nào có hứng thú với type programming trong scala với các thư viện như shapeless chẳng hạn) Thông thường với m...
huydx viết hơn 2 năm trước
1 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

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


White
{{userFollowed ? 'Following' : 'Follow'}}
118 bài viết.
1047 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á!