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

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

Phần1:

Tuần vừa rồi bận quá giờ mình mới có thời gian viết tiếp được bài về combinator.
Ở bài viết trước mình đã nói qua về 2 khái niệm cơ bản

  • Thế nào là parser
  • Giới thiệu sơ qua về BNF Bài viết trước mình mình cũng đã đề cập bài toán đơn giản cần giải quyết:

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 viết này chúng ta sẽ đi vào thực hành :D

Giới thiệu về scala parser combinator

Thông thường chắc bạn nào từng tìm hiểu về compiler sẽ biết về Anltr hay là Jacc. Cả 2 thư viện này đều có đặc điểm chung là đều là Generator. Có nghĩa là bạn cho tool một bộ rule, tool sẽ generate code hộ bạn.
Với mỗi bộ tool các bạn sẽ có các cách để hook vào các xử lý khi parse mà không phải động vào generated code, như là kế thừa...

Scala Parser Combinator là một parser đi theo một hướng khác thay vì generate code, đó là sử dụng trực tiếp code để mô tả bộ rule. Qua đó giúp cho việc hook các xử lý khi parse dễ dàng hơn nhiều. Và cũng khiến code trực quan hơn, sơ với việc bạn phải nhìn cái đống loằng ngoằng được gen ra từ jacc hay anltr.

Về mặt ngữ nghĩa, parser combinator có nghĩa là bạn kết hợp nhiều parser nhỏ, thành 1 parser to, phức tạp hơn.

Cơ bản về cách sử dụng Combinator Parser

Định nghĩa parser

Mình quote lại BNF mình đã sử dụng ở phần 1:

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

Cách sử dụng scala combinator rất đơn giản, với scala trước 2.10 thì đã nằm sẵn trong standard lib, bạn không phải làm gì, với version >= 2.11 thì bạn chỉ cần thêm vào Dependencies dưới đây vào sbt ( do bộ thư viện này đã được tách ra khỏi stl)

"org.scala-lang.modules"  %% "scala-parser-combinators" % "1.0.4"

Cách sử dụng vô cùng đơn giản, bộ combinator này được đặc trưng bởi class Parser. Mỗi một instance của Parser sẽ là kết quả trả về của một quá trình parsing của một hay nhiều bộ Parser khác nhau.
Để thực hiện quá trình parsing thì chúng ta cần có một logic nhằm "tách" các token có sẵn. Rất may mắn có một class đã làm giúp hộ chúng ta việc này là JavaTokenParser. Chúng ta chỉ cần extends class này là đã có sẵn rất nhiều bộ parser con (như parse số nguyên, parse string, parse số float)

import java.util.parsing.combinator._

class MyFirstParser extends JavaTokenParser {
 def value: Parser[Any] = floatingPointNumber
}

class MyFirstParserImpl extends MyFirstParser {
 def parse(input: String): Float = parseAll(value, input)
}

object Main extends App {
 println((new MyFirstParserImpl).parse("133.33"))
}

//[1.7] parsed: 133.33

Ở ví dụ trên mình làm một việc rất đơn giản là parse một số Float.
Nhìn ví dụ đó bạn có thể hình dung được cách thức hoạt động của scala parser combinator.
Mình tóm gọn nó lại như sau:

  • Bạn cần một class extends JavaTokenParser
  • Trong class đó bạn có các method định nghĩa các parser con
  • Bạn có thể dùng lại các parsercon để hợp lại thành một parser cha phức tạp hơn.
  • Bạn sử dụng hàm parseAll để parse một parser với một input cho trước

Hết sức đơn giản đúng không :D

Kết hợp các parser con và sử dụng kết quả parse được

Ở ví dụ trên mình có một parser con là floatingPointNumber
Vậy giả sử mình muốn parse một biểu thức gồm 2 floatingPointNumber, cách nhau bởi dấu phẩy thì mình phải làm sao . Rất đơn giản

def multipleFloatingPoint = floatingPointNumber ~ "," ~ floatingPointNumber

Bạn có thể tinh ý thấy sự xuất hiện của kí tự ~. Kí tự này có ý nghĩa là tiếp nối bới.
Vậy dịch parser ở trên ra tiếng việt:

floatingPointNumber tiếp nối bởi dấu "," tiếp nối bởi floatingPointNumber

Việc parsing trở nên dễ dàng như bạn nói tiếng Việt vậy :D. Ngoài kí hiệu ~, scala cung cấp cho chúng ta một loạt các kĩ hiệu hữu dụng khác:

Kĩ hiệu Ý Nghĩa
` `
~> Tiếp nối về bên phải, nhưng chỉ lấy phần match ở bên phải
<~ Tiếp nối về bên phải, nhưng chỉ lấy phần match ở bên trái
opt() option: có thể có hoặc không
"..".r Sử dụng regex ở trong dấu ..
^^ Sử dụng kết quả parse được, ném vào một cái PartialFunction để case match
rep Match lặp đi lặp lại một parser nào đó cho đến khi kết thúc

Vậy chúng ta đã có trong tay một bộ tool đầy đủ đẻ parse bất kì thứ gì mình muốn rồi. Quay trở lại bài toán ở đầu bài, mình đã giải quyết bằng một bộ parser tương đối ngắn sau:

import scala.util.parsing.combinator._

abstract class BoolExpression {
  def eval(): Boolean
}

case class EntityValue(e: BoolExpression) extends BoolExpression {
  override def eval() = e.eval()
}
case class BoolValue(n: Boolean) extends BoolExpression {
  override def eval() = n
}
case class NotOperatorValue(value: BoolExpression) extends BoolExpression {
  override def eval() = {
    !value.eval()
  }
}
case class BinaryOperatorValue(op: String, v1: BoolExpression, v2: BoolExpression) extends BoolExpression {
  override def eval() = op match {
    case "and" => v1.eval() && v2.eval()
    case "or"  => v1.eval() || v2.eval()
  }
}

case class UnaryOperatorValue(op: String, value: BoolExpression)

case class FormulaValue(startValue: BoolExpression, list: List[UnaryOperatorValue]) extends BoolExpression {
  override def eval() = {
    list.foldLeft(startValue.eval()) {
      (v: Boolean, op: UnaryOperatorValue) => BinaryOperatorValue(op.op, BoolValue(v), op.value).eval()
    }
  }
}


class Logical extends JavaTokenParsers {
  def expr: Parser[BoolExpression] = term ~ rep(op) ^^ {
    case v~list => FormulaValue(v, list)
  }

  def op: Parser[UnaryOperatorValue] = ("and" | "or") ~ term ^^ {case(op~v) => UnaryOperatorValue(op,v)}

  def term: Parser[BoolExpression] = factor | notfactor
  def notfactor: Parser[BoolExpression] = "not" ~ factor ^^ {case(op~v) => NotOperatorValue(v)}
  def factor: Parser[BoolExpression] = (
    bool ^^ {case e => BoolValue(e)}
    | "("~>expr<~")" ^^ {case e => EntityValue(e)}
  )

  def bool: Parser[Boolean] = ("true" | "false") ^^ {case(n) => n.toBoolean}
}

class LogicalParser extends Logical {
  def parse(str: String): Boolean =
    parseAll(expr, str).get.eval()
}

Các bạn có thể thấy là ở trong đoạn Parser mình chỉ đơn thuần dịch từ đống BNF ở đầu bài, thành các parser con tương ứng, và kết hợp chúng lại với nhau.
Để evaluate biểu thức Logic thì cần thêm một chút "đầu tư" về việc thiết kế class nữa. Các bạn đọc kĩ một chút chắc sẽ hiểu.

Bài viết có thể hơi khó hiểu với những bạn nào mới làm quen với scala hay không có nhiều kiến thức về computer science. Nhưng các bạn chỉ cần nhớ một việc là: khi nào cần parsing, hãy nhớ đến scala parser combinator, thế là ngon rồi :D

Tham khảo

http://www.artima.com/pins1ed/combinator-parsing.html
http://booksites.artima.com/programming_in_scala_2ed/examples/html/ch33.html

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.
1051 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
149 15
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
149 15
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.
1051 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á!