Recently i was working on a project that is processing campaigns. I asked my self if I can improve it a bit, but not by refactoring existing code but by trying to approach it from a different angle.

Observations

I started making mind notes of things that i understand about system i’m working with. I never had time to think about grammar of this and really get into it. The system has many parts but i thought it can be reproduced in for of language that is easy to parse and nice to work with. I think i might change my current solution into more LISP looking thing just to make it easier to parse.

Observation 1

Each campaign is a sequence of actions that happens one after another. So my initial thought was “this is simple”. We can represent it by list of actions like this

 [step] -> [step] -> [step]

But this is true only for simple campaigns and most of them are NOT like this :(

Observation 2

Most of the campaigns are built around key thing. This thing is making decisions! So if i can incorporate “if” i WIN ! Lets have a look

                     /> [step]
                   (No)
                    |
  [step] -> [if a < 5] - ( yes ) -> [step]

Yes! This was it, i think this is solution to all problems, ability to represent campaign as a sequence of steps mixed with if statements essentially abstract syntax tree of campaign.

Observation 3

It is not a tree…its more a graph. But AST will make it :] it is a programming language! So this was in my head and i did not had time to work on it… but today i decided to give a try and I made first impression of AST that we would need to have to make it work.

AST

I wrote simple grammar and made a parser of a very simple “ify” language. My language starts like this…

-- Grammar
-- x is variable
-- a is artmetic thing aka number
-- n is actual number eg. 1
-- b is boolean
-- opa is arthmetic operator
-- opb is boolean operator
-- opr is comparison operator
-- S is statement
--  a   ::= x | n | - a | a opa a
--  b   ::= true | false | not b | b opb b | a opr a
--  opa ::= + | - | * | /
--  opb ::= and | or
--  opr ::= > | <
--  S   ::= x | x <- a | S1; S2 | ( S ) | if b then S1 else S2

This shows that the grammar is very simple, we can have assigments, operators to test and compare and ofc IF statement ;) this is our key to divnity!

Parser looks kinda ugly because i used parts of the code i wrote before and had i in different projects.

import System.Environment(getArgs)
import System.IO
import Control.Monad
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import Text.ParserCombinators.Parsec.Language
import qualified Text.ParserCombinators.Parsec.Token as Token

--  Grammar
-- x is variable
-- a is artmetic thing aka number
-- n is actual number eg. 1
-- b is boolean
-- opa is arthmetic operator
-- opb is boolean operator
-- opr is comparison operator
-- S is statement
--  a   ::= x | n | - a | a opa a
--  b   ::= true | false | not b | b opb b | a opr a
--  opa ::= + | - | * | /
--  opb ::= and | or
--  opr ::= > | <
--  S   ::= x | x <- a | S1; S2 | ( S ) | if b then S1 else S2 

data AExpr = Var String
            | IntConst Integer
            | Neg AExpr
            | ABinary ABinOp AExpr AExpr
              deriving (Show)

data BExpr = BoolConst Bool
            | Not BExpr
            | BBinary BBinOp BExpr BExpr
            | RBinary RBinOp AExpr AExpr
             deriving (Show)

data ABinOp = Add
            | Subtract
            | Multiply
            | Divide
              deriving (Show)

data BBinOp = And | Or deriving (Show)
data RBinOp = Greater | Less deriving (Show)

data Stmt = Seq [Stmt]
           | Assign String AExpr
           | If BExpr Stmt Stmt
           | Ident String
             deriving (Show)

languageDef =
   emptyDef { Token.commentStart    = "/*"
            , Token.commentEnd      = "*/"
            , Token.commentLine     = "#"
            , Token.identStart      = letter
            , Token.identLetter     = alphaNum
            , Token.reservedNames   = [ "if"
                                      , "then"
                                      , "else"
                                      , "true"
                                      , "false"
                                      , "not"
                                      , "and"
                                      , "or"
                                      ]
            , Token.reservedOpNames = ["+", "-", "*", "/", "<-"
                                      , "<", ">", "and", "or", "not"
                                      ]
            }

lexer = Token.makeTokenParser languageDef

identifier = Token.identifier lexer -- parses an identifier
reserved   = Token.reserved   lexer -- parses a reserved name
reservedOp = Token.reservedOp lexer -- parses an operator
parens     = Token.parens     lexer -- parses surrounding parenthesis:
integer    = Token.integer    lexer -- parses an integer
semi       = Token.semi       lexer -- parses a semicolon
whiteSpace = Token.whiteSpace lexer -- parses whitespace

whileParser :: Parser Stmt
whileParser = whiteSpace >> statement

statement :: Parser Stmt
statement =   parens statement
           <|> sequenceOfStmt

sequenceOfStmt =
   do list <- (sepBy1 statement' semi)
      return $ if length list == 1 then head list else Seq list

statement' :: Parser Stmt
statement' =   ifStmt
            <|> assignStmt
            <|> identName

ifStmt :: Parser Stmt
ifStmt =
   do reserved "if"
      cond  <- bExpression
      reserved "then"
      stmt1 <- statement
      reserved "else"
      stmt2 <- statement
      return $ If cond stmt1 stmt2


identName :: Parser Stmt
identName =
   do  varName <- identifier
       return $ Ident varName

assignStmt :: Parser Stmt
assignStmt =
   do var  <- identifier
      reservedOp "<-"
      expr <- aExpression
      return $ Assign var expr

aExpression :: Parser AExpr
aExpression = buildExpressionParser aOperators aTerm

bExpression :: Parser BExpr
bExpression = buildExpressionParser bOperators bTerm

aOperators = [ [Prefix (reservedOp "-"   >> return (Neg             ))          ]
              , [Infix  (reservedOp "*"   >> return (ABinary Multiply)) AssocLeft]
              , [Infix  (reservedOp "/"   >> return (ABinary Divide  )) AssocLeft]
              , [Infix  (reservedOp "+"   >> return (ABinary Add     )) AssocLeft]
              , [Infix  (reservedOp "-"   >> return (ABinary Subtract)) AssocLeft]
               ]

bOperators = [ [Prefix (reservedOp "not" >> return (Not             ))          ]
              , [Infix  (reservedOp "and" >> return (BBinary And     )) AssocLeft]
              , [Infix  (reservedOp "or"  >> return (BBinary Or      )) AssocLeft]
              ]

aTerm =  parens aExpression
      <|> liftM Var identifier
      <|> liftM IntConst integer

bTerm =  parens bExpression
      <|> (reserved "true"  >> return (BoolConst True ))
      <|> (reserved "false" >> return (BoolConst False))
      <|> rExpression

rExpression =
   do a1 <- aExpression
      op <- relation
      a2 <- aExpression
      return $ RBinary op a1 a2

relation =   (reservedOp ">" >> return Greater)
          <|> (reservedOp "<" >> return Less)


parseString :: String -> Stmt
parseString str =
   case parse whileParser "" str of
     Left e  -> error $ show e
     Right r -> r

parseFile :: String -> IO Stmt
parseFile file =
   do program  <- readFile file
      case parse whileParser "" program of
        Left e  -> print e >> fail "parse error"
        Right r -> return r

main = do
  args <- getArgs
  ast <- parseFile(head args)
  putStrLn $ show ast

But it works… we can parse. Now i have to make it more production ready and less unstable ;]. This is first attempt at this idea. I need to expand grammar and think about it more then just few minutes. but i think it is a good start. Next step for me is to make better grammar and parser and move to building interpreter of this mini language.

No F*cking Idea

Common answer to everything

'If' the Real Game Changer

Observations

Observation 1

Observation 2

Observation 3

AST

Comments