Thử parse logical expression với Parsec (Haskell)
Haskell
18
Parsec
1
White

viethnguyen viết ngày 23/05/2015

Đề bài

Gần đây, thằng bạn tôi rảnh rỗi học cách parsing với Scala. Tôi nghe nói Scala có parser combinator khá là mạnh. Vừa hay, tôi cũng đang tìm hiểu về cách parsing bằng thư viện Parsec của Haskell. Thế nên tôi cũng bắt đầu làm thử bài tập của thằng bạn luôn (như là một hình thức so tài :)) )

Đề bài nhìn qua thì có vẻ đơn giản:

Duyệt biểu thức logic bao gồm AND, OR và dấu ngoặc và đưa ra kết quả sau khi tính giá trị. Nếu biểu thức không hợp lý thì đưa ra thông báo lỗi
Ví dụ
TRUE --> TRUE
TRUE OR FALSE --> TRUE

TRUE AND (TRUE OR FALSE) --> TRUE
TRUE AND ---> invalid expression

Tôi thử nghĩ xem dùng C/C++ hay C# (mấy ngôn ngữ tôi biết) thì thế nào, nhưng mới chỉ nghĩ ra là duyệt từng kí tự rồi ghép xâu, xử lý rẽ nhánh... Nghĩ đã thấy lằng nhằng. Nếu bạn đọc biết cách nào hay ho, nhanh chóng (ngôn ngữ gì cũng được, dùng thư viện cũng OK), thì cho tôi xin comment nhé :)

Còn bây giờ, tôi sử dụng Parsec của Haskell.

TL;DR

Parser (khoảng 100 dòng) tôi thử viết đặt tại repo này . Bạn có thể clone về nghịch :D
Bạn có thể xem thêm Bài viết này để biết cách bắt đầu với Haskell.
Bạn cần có module Parsec, có thể cài đặt qua Cabal:

$ cabal install parsec

Để biên dịch:

$ ghc -package parsec -o parse-logic parse-logic.hs

Rồi chỉ cần chạy executable file với string bạn muốn test. Tôi test thử thì thế này:

alt text

Phân tích parser

Trong phần này tôi sẽ trình bày chi tiết về đoạn code 100 dòng trên. Hi vọng sẽ không làm bạn đọc buồn ngủ.

Trước tiên là một số module cần import:

module Main where

import Control.Monad
import System.Environment 
import Text.ParserCombinators.Parsec
import Data.Bool

Tiếp đến, tôi định nghĩ kiểu dữ liệu LogicExpr như sau:

data LogicExpr = BOOL Bool
              | AND LogicExpr LogicExpr 
              | OR LogicExpr LogicExpr 
              | PARENS LogicExpr

Như vậy, một biểu thức logic có thể là: 1/ Một giá trị Bool (TRUE hoặc FALSE), 2/ Một biểu thức AND, 3/ Một biểu thức OR, hoặc 4/ Một biểu thức ngoặc. Trong khai báo trên, BOOL, AND, OR, PARENS là các data constructor cho LogicExpr, theo sau chúng là các tham số cần thiết.

Ý tưởng cơ bản của một parser là nó nhận vào input (ví dụ, một xâu kí tự), rồi nó "ăn" kí tự của xâu này cho đến khi nó hoàn tất nhiệm vụ parse của nó, và chuyển phần còn lại (chưa được parse) cho các bước kế tiếp, phần còn lại này có thể được dùng cho các parser tiếp theo.

Module Parsec của Haskell rất mạnh ở chỗ: nó cho phép người dùng định nghĩa những parser nhỏ trước, rồi hợp chúng lại những parser phức tạp hơn.

Chúng ta cùng bắt đầu parse.

Tôi định nghĩa các parser cơ bản như sau:

parseBool :: Parser LogicExpr
parseBool = lexeme $ do
  val <- string "TRUE" <|> string "FALSE"
  return $ case val of
    "TRUE" -> BOOL True
    "FALSE" -> BOOL False

parseParens :: Parser LogicExpr
parseParens = do
  lexeme $ char '('
  expr <- lexeme $ (try parseOp <|> parseBool)
  lexeme $ char ')'
  return $ PARENS expr

-- Each operand can be seen as a bool value, or an expression inside parentheses
parseBoolOrParens :: Parser LogicExpr
parseBoolOrParens = parseBool <|> parseParens

parseOp :: Parser LogicExpr
parseOp = chainl1 parseBoolOrParens op
  where
    op = do
      val <- lexeme $ (string "AND" <|> string "OR")
      return  $  case val of
        "AND" -> AND
        "OR" -> OR

Ở đây tôi có 3 parser con : parseBool để parse TRUE hoặc FALSE; parrseParens để parse biểu thức ngoặc (...) , và parseOp để parse biểu thức dạng [toán hạng] [toán tử ] [toán hạng]. Mỗi parser có vài điểm cần lưu ý:

  • parseBool: sử dụng parser string có sẵn để tìm kiểm xâu "TRUE" hoặc "FALSE". Toán tử <|> của Parsec dùng để thử nhiều parser: đầu tiên nó thử parse thứ nhất trước, nếu không thành công thì thử các parser tiếp theo. Giá trị trả về của Parser có kiểu Parser String, là một Monad, tôi sử dụng <- để trích ra giá trị String bên trong và gán vào val. Tiếp đó, tùy theo giá trị của val, tôi dùng data constructor BOOL để tạo một biến LogicExpr, và wrap nó lại trong Monad Parser LogicExpr bằng return.
  • parseParens: sử dụng parser char để tìm dấu mở ngoặc. Tiếp đó thử hai parser khác là parseOpparseBool (vì trong dấu ngoặc có thể là một biểu thức hoặc một giá trị Bool). Giá trị trả về của phép thử này (kiểu LogicExpr) được gán vào expr. Tiếp đó, sử dụng parser char tiếp để tìm dâu đóng ngoặc. Kết thúc là dùng data constructor PARENS với tham số expr để tạo một biến LogicExpr, wrap nó lại bằng return.
  • parseBoolOrParens: là hợp của 2 parser hơn, vì tôi muốn toán hạng có thể là một Bool, hoặc một Parens.
  • parseOp: Một điểm khá hay ho ở đây là tôi sử dụng parser combinator chainl1, vì nó khá phù hợp ở đây: tôi muốn parse một hoặc nhiều toán hạng, phân cách bởi toán tử. Đối số của chainl1 là parser cho toán hạng (parseBoolOrParens) và parser cho toán tử (op). Nhờ chainl1 tôi có thể xử lý biểu thức dài như là TRUE AND TRUE OR FALSE OR (TRUE AND FALSE) dễ dàng. Parser op được viết dựa trên parser string, như parseBool ở trên.

Phù, đoạn ở trên khá là cồng kềnh về lý thuyết, nhưng tóm lại là tôi đã có 3 parser con để sử dụng. Tôi hợp chúng lại thành một parser to hơn, cho cả biểu thức:

-- parse an expression : combinator of three parsers above
parseExpr :: Parser LogicExpr
parseExpr = parseParens
            <|> parseOp
            <|> parseBool

-- same as above, but with leading whitespaces cut off 
parseExpr2 = do
  whitespace
  t <- parseExpr
  return t

Một trong những vấn đề phải xử lý là parse khoảng trắng (dấu cách, dáu TAB, dấu xuống dòng). Tôi xử lý như sau:

-- Skip whitespaces 
whitespace :: Parser ()
whitespace = void $ many $ oneOf " \n\t"

-- lexeme: A style in which every token parser should also consume and ignore any
-- trailing whitespaces.
lexeme :: Parser a -> Parser a
lexeme p = do
  x <- p
  whitespace
  return x

lexeme là một hình thức "bồi đắp" lên một parser đã có, bắt chúng phải "ăn" luôn cả những khoảng trắng phía sau nữa. Bạn có thể thấy, tôi có sử dụng lexeme để "bồi đắp" ở parseBoolparseOp ở trên.

Kết quả sau khi parse sẽ là LogicExpr, tôi cần phải định nghĩa cách show nó ra dưới dạng xâu kí tự nữa:

-- Tell the program how to print LogicExpr out   
showExpr :: LogicExpr -> String
showExpr (BOOL b) = show b
showExpr (AND a b) = (showExpr a) ++ " and " ++ (showExpr b)
showExpr (OR a b) = (showExpr a) ++ " or " ++ (showExpr b)
showExpr (PARENS m) = "(" ++ (showExpr m) ++ ")"

instance Show LogicExpr where show = showExpr

Đây chỉ đơn thuần là pattern matching. Để đơn giản hơn nữa, tôi tạo một instance của Show typeclass cho LogicExpr để chương trình biết cách display kiểu LogicExpr.

Với bài toán này, sau khi đã parse rồi thì một nhiệm vụ nữa là phải evaluate nó nữa.

-- Evaluate
eval :: LogicExpr -> Bool
eval (BOOL b) = b
eval (AND a b) = (eval a) && (eval b)
eval (OR a b) = (eval a) || (eval b)
eval (PARENS m) = eval m

-- test parser
test :: String -> String
test input = case parse parseExpr2 "abc" input of
  Left err -> "Invalid expression!"
  Right val -> "Evaluation result: " ++ show (eval val)

eval chỉ đơn giản là pattern matching và sử dụng các phép toán Boolean của Haskell để đánh giá biểu thức.

Và đây rồi, hàm test: nhận vào một xâu cần parse và trả về một xâu kết quả: "Invalid Expression" hoặc "Evaluation result:...". Điểm chú ý ở đây là hàm parse. Kiểu của nó như sau: parse :: Stream s Identity t => Parsec s () a -> SourceName -> s -> Either ParseError a. Trông hơi dài dòng một tí, nhưng ý nghĩa của nó là: nó nhận vào một Parser, một SourceName, rồi xâu sẽ parse và trả về một biến Either: hoặc là Left ParseError (không parse được) hoặc là Right a (khi parse thành công). Sử dụng case, tôi chuyển chúng thành xâu báo kết quả như trên.

Xong rồi, giờ tôi có thể gắn hàm test này vào main được rồi:

main :: IO ()
main = getArgs >>= putStrLn . test . (!! 0)

getArgs :: IO [String] là một Monad. >>= là phép toán bind của Monad. Ý nghĩa của đoạn này là lấy tất cả các tham số (getArgs) rồi truyền vào cho phần tiếp theo sau dấu >>=, phần tiếp theo này lấy tham số đầu tiên (!! 0), chạy parser trên nó (test .) rồi output string kết quả (putStrLn).

Kết luận

Parser của tôi viết khoảng 100 dòng (tôi đã thua thằng bạn viết Scala, chỉ có 59 dòng, ở đây). Tuy nhiên, tôi thấy viết parser bằng Parsec khá dễ chịu, vì nó không bắt tôi phải suy nghĩ xem xử lý từng kí tự rồi rẽ nhánh phức tạp, mà chỉ phải suy nghĩ cách tạo ra các parser con và hợp chúng lại một cách hợp lý.

Parse biểu thức logic này có vẻ còn đơn giản, nếu có thời gian tôi sẽ thử parse thứ phức tạp hơn, như là ngôn ngữ Brainfuck (cũng do thằng bạn thách thức :)) ).

Tham khảo

  1. An introduction to the Parsec library
  2. Parsing floats with Parsec
  3. Write yourself a Scheme in 48 hours
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

viethnguyen

12 bài viết.
29 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
15 4
Giới thiệu về Arduino Có thể bạn đã quen lập trình trên PC, với những ngôn ngữ như C, C++, C, Java, Python, Ruby... Nhưng bạn có biết là phần mềm...
viethnguyen viết hơn 3 năm trước
15 4
White
8 0
Trong bài viết này, tôi sẽ trình bày về một đặc tính của Haskell khá khác biệt so với các ngôn ngữ lập trình khác, đó là laziness (dịch tiếng việt ...
viethnguyen viết hơn 3 năm trước
8 0
White
6 0
Giới thiệu Quy hoạch động là một trong những kĩ thuật lập trình cơ bản được sử dụng khá nhiều trong các cuộc thi lập trình. Ý tưởng về cơ bản rất ...
viethnguyen viết hơn 3 năm trước
6 0
Bài viết liên quan
White
14 6
Người ta nói "nullable values" là cái "billion dollar mistake". Kể từ ALGOL, chúng ta không thể dùng nullable values/references như một value bình ...
Justin Le viết hơn 3 năm trước
14 6
White
3 0
Đọc hiểu được type signature là một trong các yếu tố quyết định chuyện bạn có học Haskell được hay không. Đa số chúng ta khi mới tìm hiểu thường g...
Huy Trần viết 9 tháng trước
3 0
White
4 2
Trong (Link), tôi có đề cập đến cách bắt đầu với Haskell bằng cách cài đặt Haskell Platform. Sau một thời gian mày mò không biết bao nhiêu thời gia...
viethnguyen viết hơn 3 năm trước
4 2
{{like_count}}

kipalog

{{ comment_count }}

bình luận

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


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