1 Parser Combinator for R-SQL

1.1 About

  • Daniel McCrevan and Taro Kuriyama
  • RC Fall 1 Batch last week presentation

1.2 R-SQL

  • R-SQL
  • RC-SQL
  • Our-SQL
  • Toy SQL subset
  • Written for Haskell toy database group project

1.3 Parser Combinator

  • Define parsers for tokens
  • Combine parsers for groups of tokens
  • A chain (or tree) of parsers
  • Any failure along the way yields ParseError

2 How does it parse?

2.1 Haskell Definition

-- Everything is an expression; no recursion required
data Expr
  = Create Table [Column]
  | Drop Table
  | Select FieldSelect Table [Condition]
  | Insert Table [FieldValue]
  | Delete Table [Condition]
  deriving (Show, Eq)

2.2 Expr Parser Top-Level

exprP :: Parser Expr   -- Type signature
exprP =                -- Function definition
  try selectP <|>      -- Alternative
  try dropP <|> 
  try createP <|> 
  try insertP <|> 
  try deleteP

parseExpr :: String -> Either ParseError ExprparseExpr string = parse exprP "" string

2.3 Insert

-- Insert Into myTable [1, True, "name"];
insertP :: Parser Expr
insertP = do              
  L.reserved "Insert"     -- Match "insert" and return nothing
  L.reserved "Into"       -- Match "into" and return nothing 
  name <- L.identifier    -- Match a string and save it to name
  fvs <- L.brackets $ L.commaSep fieldValue -- Combine parsers
  L.semi                   -- Match semicolun and return nothing 
  return $ Insert name fvs -- Construct Insert with parsed values

2.4 Parse Field Values

fvs <- L.brackets $ L.commaSep fieldValue

L.brackets: match brackets and spaces, return inner
L.commaSep: match commas and spaces, return list
fieldValue: another parser combinator

2.5 Parse Field Value

fieldValue :: Parser FieldValue
fieldValue = boolValue <|> intValue <|> textValue
...
intValue :: Parser FieldValue
intValue = do
  n <- L.integer
  return $ FvInt (fromInteger n)

3 Demo