fcard/vimscript_parser.vim

## vimscript_parser.vim
" Command: Command
"
" A different take on command creation,
" Command creates a namespace for which
" its implementation functions can be
" stored in. The command name also comes
" first, followed by its argument type
" in parentheses, to mimic function
" definitions. name  Anything preceding a ':='
" command body.
" Using a '!' in the Command is the same
" as giving it the -bang option. It's not
" possible to overwrite a Command.
"
" By default a commands namespace is local to the script,
" but you can make it global by prepending 'g:' before the
" command's name.
"
" Usage: Command[!] [g:]<Name>([<argtype>]) [<options...>] := <body>
"

command -nargs=1 -bang Command execute s:CommandFactory(<q-args>, '<bang>'=='!')

function s:CommandFactory(string,bang)
  let name = ""
  let args = ""
  let opts = ""
  let body = ""
  let scope = "s"

  "Variable to keep track of the current position of the line"
  let index = 0

  "Ignore whitespace until start of the name is found"
  while a:string[index] == ' '
    let index += 1
  endwhile

  "Capture name, until '(' is found. Ignore whitespace before ("
  let found_whitespace = v:false
  while a:string[index] != '('
    if !found_whitespace
      if a:string[index] == ' '
        let found_whitespace = v:true
      else
        let name  .= a:string[index]
      endif
      let index += 1
    else
      "
      " If whitespace is found after the name but before the '(',
      " any other character after that before the '(' must also be
      " whitespace or it will be an error.
      "
      if a:string[index] == ' '
        let index += 1
      else
        throw "Command names can't have whitespace in them!"
      endif
    endif
  endwhile

  "Extract namespace scope information if present"
  if name =~ '\v^[sg]:'
    let scope = name[0]
    let name = name[2:-1]
  endif

  "Capturing the argument type"
  let index += 1
  if a:string[index] != ')'
    let args   = a:string[index]
    let index += 1
  endif
  let index += 1

  "Capturing possible options"
  let searching_opts = v:true
  while searching_opts
  "Look for a possible end of the options"
    while a:string[index] != ':'
      let opts  .= a:string[index]
      let index += 1
    endwhile
    "Maybe we found it"
    let index += 1
    if a:string[index] == '='
      "We did!"
      let index += 1
      let searching_opts = v:false
    else
      "We didn't, false alarm."
      let opts  .= ':'
      let opts  .= a:string[index]
      let index += 1
    endif
  endwhile

  "If the Command was defined as Command!, then
  "add -bang as an option
  if a:bang
    let opts .= " -bang "
  endif

  "Everything else is the body"
  let body = a:string[index:-1]

  "Now we build the command definition"
  let command  = "command "
  let command .= opts
  if args != ""
    let command .= " -nargs=".args
  endif
  let command .= " ".name
  let command .= " ".body

  "Creating the command's namespace"
  let namespace_command = "let ".scope.":".name." = {'name': '".name."', 'type': 'ModularCommand'}"
  return namespace_command." | ".command
endf

" Command: ModularFunction
"
" Initializes a Modular Function by creating a s:FunctionName dictionary
" mostly a sign of what the function is going to be like: A function
" with many subfunctions to auxiliate it.
"
" Usage: ModularFunction <function-name>
"

Command ModularFunction(1) := execute "let s:<args> = { 'name' : '<args>', 'type' : 'ModularFunction' }"

" Command: CmdFromFunction
"
" Creates a simple command from
" a function.
"
" Usage: CmdFromFunction <cmdname> <funcname> [<argtype>]
"
" <argtype> can be empty, q or f, to determine how the arguments
" are to be passed to the function.
"
Command CmdFromFunction(+) := execute s:CmdFromFunction.Create(<f-args>)

function s:CmdFromFunction.Create(cmdname,funcname,...)
  let argtype   = get(a:, 1, "")
  let argprefix = argtype == "" ? "" : argtype."-"

  let cmd  = "command "
  let cmd .= "-nargs=* "
  let cmd .= a:cmdname
  let cmd .= " call ".a:funcname."(<".argprefix."args>)"

  return cmd
endf

" Command: Class
"
" Creates a dictionary imitating an OOP class
" A very light abstraction meant to add getters
" and setters setters topreexisting dictionary.
"
" Usage: Class Name
"
" To add methods to the class, use:
"
"   :function g:Class.Name.MethodName()
"   :  echo self.field1
"   :  echo self.field2
"   :endf
"
" Static methods start with '_'. They are not transfered to instances.
"
"   :function g:Class.Name._StaticMethod()
"   :  echo 30
"   :end
"
" To create an instance:
"
"   :let instance = g:Class.Name.New({'field1': 10, 'field2': 20})
"   :call instance.MethodName()
"   10
"   20
"   :call g:Class.Name._StaticMethod()
"   30
"   :echo has_key(instance, "_StaticMethod")
"   0
"
"
Command g:Class(1) := call g:Class.Init(v:false, <q-args>)

function g:Class.Init(global, name)
   let newclass = {'type': 'Class', 'name': a:name}
   function newclass.New(dict)
     let result = {}
     call extend(result, a:dict)
     for key in keys(self)
       if key[0] =~ '[A-Z]' && key != "New"
         let result[key] = self[key]
       endif
     endfor
     if has_key(result, "type")
       throw "Initialization dictionary for class cannot have key 'type'!"
     endif
     let result.type = self.name
     return result
   endf
   let g:Class[a:name] = newclass
endf

" Command: Optional
"
" Syntactic sugar for optional arguments.
" Each usage consumes an argument.
"
" Usage: Optional <name> <default>[[,] <name> <default>]*
"
" Meant to only be used once per function.
"
Command Optional(+) := execute s:Optional.Create(<f-args>)

function s:Optional.Create(...)
  "  Where 'our' refers to this current function,
  "  and 'their' refers to the function where this
  "  will be executed
  "
  let our_argument_index   = 1
  let their_argument_index = 1
  let let_statements = []
  let number_of_our_arguments = a:0

  while our_argument_index < number_of_our_arguments
    let varname = get(a:, our_argument_index)
    let default = get(a:, our_argument_index+1)

    "extract comma from default value if it's there"
    if default[-1] == ","
      let default  = default[1:-2]
    endif

    call add(let_statements, s:Optional.LetVar(varname, default, their_argument_index))

    let our_argument_index   += 2
    let their_argument_index += 1

    "Ignore optional comma"
    if our_argument_index < number_of_our_arguments && get(a:, our_argument_index) == ','
      let our_argument_index += 1
    endif
  endwhile

  return join(let_statements, " | ")
endf

function s:Optional.LetVar(name, default_value, index)
  return "let a:".a:name." = get(a:, ".a:index.", ".a:default_value.")"
endf

" Command: LetTmp, UnLetTmp
"
" LetTmp stores the previous value of a variable before assigning it a new value.
" The previous value is restored with UnLetTmp.
"
" If no previous value exists LetTmp behaves as a normal let and UnLetTmp
" behaves as an unlet.
"
" Usage:
"   LetTmp var value
"   UnLetTmp var
"
Command g:LetTmp(+) := execute g:LetTmp.Create(<f-args>)
Command UnLetTmp(+) := execute s:UnLetTmp.Create(<f-args>)

function g:LetTmp.Create(var, value)
  if a:var == "Create"
    throw "hey don't try to trick me!!"
  endif
  let code  = "if !exists('".a:var."')\n"
  let code .= "  let g:LetTmp['".a:var."'] = ".a:value."\n"
  let code .= "endif\n"
  let code .= "let ".a:var." = ".a:value
  return code
endf

function s:UnLetTmp.Create(var)
  if a:var == "Create"
    throw "nasty nasty!"
  endif
  let code  = "if has_key(g:LetTmp, '".a:var."')\n"
  let code .= "  let ".a:var." = g:LetTmp['".a:var."']\n"
  let code .= "  unlet g:LetTmp['".a:var."']\n"
  let code .= "else\n"
  let code .= "  unlet ".a:var."\n"
  let code .= "endif"
  return code
endf

" Function: CloseParens
"
" Get the character that closes the given parens. e.g. CloseParens('(') == ')'
"
" Usage: CloseParens(<string>)
ModularFunction CloseParens

let s:CloseParens.closers = {
  \ '(': ')',
  \ '[': ']',
  \ '{': '}'
\}

function CloseParens(parens)
  return s:CloseParens.closers[a:parens]
endf

" Function: ParseAST
"
" Creates a AST from a string representing Vimscript code.
" Returns a structure of the form:
"
" {
"   'head' : <string representing what type it is>
"   'nodes': <child nodes that compose the structure>
"   'ex'   : <bool telling if the expression was in EX position>
" }
"
" Usage: ParseAST(<string>)
"

"Init"
ModularFunction ParseAST

"Helper class ParserState"
Class ParserState

" Methods of ParserState
"
LetTmp s:ps g:Class.ParserState

function s:ps._Create(string, status, root_node)
  let lines = g:Class.ParserState._ObtainLines(a:string)
  return g:Class.ParserState.New({ 'lines': lines, 'status': a:status, 'node': a:root_node, 'block': [] })
endf

function s:ps._ObtainLines(string)
  let lines_intermediary = split(a:string, "\n")
  let lines = []
  let i = 0
  let e = len(lines_intermediary)
  while i < e
    let line = lines_intermediary[i]
    let i += 1
    while i < e && lines_intermediary[i] =~ '\v^\s*\\'
      let line .= substitute(lines_intermediary[i], '\v^\s*\\(.*)$', '\1', '')
      let i += 1
    endwhile
    call add(lines, line)
  endwhile
  return lines
endf

function s:ps.FromMe(new_params)
  let params = {}
  for p in ['lines', 'status', 'node', 'block']
    let params[p] = ( has_key(a:new_params, p) ? a:new_params[p] : self[p] )
  endfor
  return g:Class.ParserState.New(params)
endf

function s:ps.EnterNode(node)
  return self.FromMe({'node': a:node})
endf

function s:ps.StartBlock(node, block)
  return self.FromMe({'node': a:node, 'block': a:block})
endf

function s:ps.EndBlock()
  let self.block = ['ended']
endf

function s:ps.EndedBy(cmd)
  return count(self.block, a:cmd) != 0
endf

function s:ps.Children()
  return self.node.children
endf

function s:ps.AddChild(node)
  call add(self.node.children, a:node)
endf

function s:ps.PrependChild(node)
  call insert(self.node.children, a:node)
endf

function s:ps.AppendChildren(nodes)
  call extend(self.node.children, a:nodes)
endf

function s:ps.LastChild()
  return self.node.children[-1]
endf


function s:ps.PopChild()
  return remove(self.node.children, -1)
endf

function s:ps.ReplaceLastChild(node)
  let self.node.children[-1] = a:node
endf

function s:ps.Line(...)
  Optional start 0, end -1

  return self.lines[self.status.line][a:start:a:end]
endf

function s:ps.Char()
  return self.lines[self.status.line][self.status.index]
endf

function s:ps.LineIndex()
  return self.status.line
endf

function s:ps.CharIndex()
  return self.status.index
endf

function s:ps.SetCharIndex(index)
  let self.status.index = a:index
endf

function s:ps.GetToken(match)
  call self.IgnoreWhitespace()
  let line  = self.Line()
  let word  = ""
  let index = self.CharIndex()
  while line[index] =~ a:match
    let word  .= line[index]
    let index += 1
  endwhile
  call self.SetCharIndex(index)
  return word
endf

function s:ps.IgnoreWhitespace()
  let line  = self.Line()
  let index = self.CharIndex()
  while line[index] =~ '\s'
    let index += 1
  endwhile
  call self.SetCharIndex(index)
endf

function s:ps.LineRest()
  let line = self.Line(self.CharIndex())
  call self.NextLine()
  return line
endf

function s:ps.NextLine()
  let self.status.index = 0
  let self.status.line += 1
endf

function s:ps.NextChar()
  let self.status.index += 1
endf

function s:ps.BackTrackChar()
  let self.status.index -= 1
endf

function s:ps.HasChars()
  return len(self.Line()) > self.CharIndex()
endf

function s:ps.HasLines()
  return len(self.lines) > self.LineIndex()
endf

UnLetTmp s:ps

"Helper class CommandTree
Class CommandTree

LetTmp s:ct g:Class.CommandTree

function s:ct._Create()
  return g:Class.CommandTree.New({'root': {}})
endf

function s:ct.Add(cmd)
  if type(a:cmd) == type([])
    let cmd = {'name': a:cmd[0], 'args': a:cmd[1], 'block': (len(a:cmd)>2 ? a:cmd[2] : [])}
  else
    let cmd = a:cmd
  endif

  let node = self.root
  for i in range(0, len(cmd.name)-1)
    let char = cmd.name[i]
    if !has_key(node, char)
      let node[char] = {}
    endif
    let node = node[char]
  endfor
  let node.value = cmd
endf

function s:ct.AddAll(cmdlist)
  for cmd in a:cmdlist
    call self.Add(cmd)
  endfor
endf

function s:ct.Get(cmdname)
  let node = self.root
  for i in range(0, len(a:cmdname)-1)
    let char = a:cmdname[i]
    if !has_key(node, char)
      throw "No command with name '".a:cmdname."'"
    endif
    let node = node[char]
  endfor
  while !has_key(node, 'value')
    if len(node) == 0
      throw "No command with name '".a:cmdname."'"
    elseif len(node) > 1
      throw "Command '".a:cmdname."' is ambiguous"
    else
      let node = values(node)[0]
    endif
  endwhile
  return node.value
endf

UnLetTmp s:ct

Class OperatorTree

LetTmp s:ot g:Class.OperatorTree

function s:ot._Create()
  return g:Class.OperatorTree.New({'root': {}})
endf

function s:ot.Add(op)
  let node = self.root
  for i in range(0, len(a:op)-1)
    let char = a:op[i]
    if !has_key(node, char)
      let node[char] = {}
    endif
    let node = node[char]
  endfor
  let node.value = a:op
endf

function s:ot.AddAll(ops)
  for op in a:ops
    call self.Add(op)
  endfor
endf

function s:ot.TryGet(state)
  let chars_moved = 0
  let found_at_index = 0
  let node = self.root
  let result = {'got': v:false, 'value': ''}
  let possible_values = []
  let finished = v:false
  while !finished && a:state.HasChars()
    if has_key(node, a:state.Char())
      let chars_moved += 1
      let node = node[a:state.Char()]
      if has_key(node, 'value')
        let result.got = v:true
        let result.value = node.value
        let found_at_index = chars_moved
      endif
      call a:state.NextChar()
    else
      let finished = v:true
    endif
  endwhile
  if chars_moved > found_at_index
    while chars_moved > found_at_index
      call a:state.BackTrackChar()
      let chars_moved -= 1
    endwhile
  endif
  return result
endf

let s:ParseAST.cTree = g:Class.CommandTree._Create()

call s:ParseAST.cTree.AddAll([
  \['call', 'expr'],
  \['let', 'expr'],
  \['echo', 'expr*'],
  \['command', '*'],
  \['function', 'expr', ['endf','endfunction']],
  \['if', 'expr', ['elseif','else','endif']],
  \['elseif', 'expr', ['elseif','else','endif']],
  \['else', '0', ['endif']],
  \['for', 'expr,<in>,expr', ['endfor']],
  \['while', 'expr', ['endwhile']],
  \['try', '0', ['catch','finally','endtry']],
  \['catch', '0', ['finally', 'endtry']],
  \['finally', '0', ['endtry']],
  \['endf', '0'],
  \['endfunction', '0'],
  \['endfor', '0'],
  \['endif', '0'],
  \['endwhile', '0'],
  \['endtry', '0']
\])

let s:ParseAST.opTree = g:Class.OperatorTree._Create()

call s:ParseAST.opTree.AddAll([
  \'+', '-', '*', '/', '.', ':',
  \'+=', '-=', '*=', '/=', '.=', '=',
  \'==', '!=', '=~', '!~', '>=', '<=','<','>',
  \'&&', '||'
\])

let s:ParseAST.opPriority = {
  \'+': 4, '-': 4, '.': 6, '*': 5, '/': 5, ':': 3,
  \'+=': 2, '-=': 2, '*=': 2, '/=': 2, '.=': 2, '=': 2,
  \'==': 1, '!=': 1, '=~': 1, '!~': 1, '>=': 1, '<=': 1, '<': 1, '>': 1,
  \'&&': 0, '||': 0
\}

function s:ParseAST.opPriority.LessThan(x,y)
  return self[a:x] < self[a:y]
endf

let s:ParseAST.keywordTree = g:Class.OperatorTree._Create()

call s:ParseAST.keywordTree.AddAll([
  \'in'
\])

"Implementation
"

function ParseAST(string, isexpression)
  let state = s:ParseAST.CreateParserState(a:string)
  if a:isexpression
    call s:ParseAST.Expression(state)
  else
    call s:ParseAST.Initial(state)
  endif
  return state.node
endf

"Start parsing with no context
function s:ParseAST.Initial(state)
  "A initial expression can either be a comment, a command, or a empty line.
  while a:state.block != ['ended'] && a:state.HasLines()

    if a:state.Line() =~ "^\s*$"
      call a:state.NextLine()

    elseif a:state.Line() =~ '^\s*"'
      call s:ParseAST.Comment(a:state)

    else
      call s:ParseAST.EX(a:state)
    endif
  endwhile
  if !empty(a:state.block) && a:state.block != ['ended']
    throw 'unfinished '.a:state.node.head.' '.a:state.node.value.' expression, missing ('.join(a:state.block,"|").')'
  endif
endf

function s:ParseAST.Comment(state)
  let comment_node = s:ParseAST.CreateNode('comment')
  let comment_node.value = a:state.Line(a:state.CharIndex())
  call a:state.AddChild(comment_node)
  call a:state.NextLine()
  call s:ParseAST.Initial(a:state)
endf

function s:ParseAST.EX(state)
  "  Determine which type of ex command it is and call
  "  the appropriate funcion to parse it
  "
  let cmd = a:state.GetToken('\w')

  if cmd[0] =~ '\v[A-Z]'
    call s:ParseAST.UserCommand(cmd, a:state)

  else
    call s:ParseAST.BuiltInCommand(cmd, a:state)

  endif
  call s:ParseAST.Initial(a:state)
endf

function s:ParseAST.UserCommand(cmd, state)
  let cmd_node = s:ParseAST.CreateNode('commandcall')
  let arg_node = s:ParseAST.CreateNode('string')
  let cmd_node.value = a:cmd
  let arg_node.value = a:state.LineRest()
  let cmd_node.children = [arg_node]

  call a:state.AddChild(cmd_node)
endf

function s:ParseAST.BuiltInCommand(cmd, state)
  let cmd_info = s:ParseAST.cTree.Get(a:cmd)
  let cmd_node = s:ParseAST.CreateNode('commandcall')
  let cmd_node.value = a:cmd

  let line_index = a:state.LineIndex()
  for args in split(cmd_info.args, ',')
    if args == '1'
      let arg_node = s:ParseAST.CreateNode('string')
      let arg_node.value = a:state.LineRest()
      let cmd_node.children = [arg_node]

    elseif args == '0'
      let line = a:state.LineRest()
      if line !~ '\v^\s*$'
        throw "command ".cmd_info.name." doesn't take arguments"
      endif

    elseif args =~ '\v^[*+]$'
      for arg in split(a:state.LineRest())
        let arg_node = s:ParseAST.CreateNode('string')
        let arg_node.value = arg
        call add(cmd_node.children, arg_node)
      endfor
      if args == '+' && len(cmd_node.children) == 0
        throw "command ".cmd_info.name." requires at least one argument!"
      endif

    elseif args == 'expr'
      call s:ParseAST.Expression(a:state.EnterNode(cmd_node))

    elseif args =~ '\vexpr[*+]'
      let cmd_state = a:state.EnterNode(cmd_node)
      while cmd_state.HasChars()
        call s:ParseAST.Expression(cmd_state)
        call cmd_state.IgnoreWhitespace()
      endwhile
      if args == 'expr+' && len(cmd_node.children) == 0
        throw "command ".cmd_info.name." requires at least one argument!"
      endif

    elseif args =~ '\v^\<.*\>$'
      let keyword = s:ParseAST.keywordTree.TryGet(a:state)
      if !keyword.got || keyword.value != args[1:-2] || a:state.Char() !~ '\s'
        throw "'".args[1:-2]."' expected but not found"
      endif
    endif
  endfor
  if line_index == a:state.LineIndex()
    let line = a:state.LineRest()
    if line !~ '\v^\s*$'
      throw "trailing characters"
    endif
  endif

  if cmd_info.block != []
    call s:ParseAST.Initial(a:state.StartBlock(cmd_node, cmd_info.block))
  endif

  if a:state.EndedBy(a:cmd)
    call a:state.EndBlock()
    if !empty(cmd_info.block)
      call a:state.AddChild(cmd_node)
    endif
  else
    call a:state.AddChild(cmd_node)
  endif

endf

function s:ParseAST.Expression(state)
  let gotexpression = v:false
  let finished = v:false

  while !finished
    call a:state.IgnoreWhitespace()

    if !a:state.HasChars()
      let finished = v:true

    elseif gotexpression
      let op = s:ParseAST.opTree.TryGet(a:state)
      if op.got
        call s:ParseAST.Op(a:state, op.value, v:true)

      elseif a:state.Char() =~ '\v[([]' && a:state.LastChild().head !~ '\v(integer|decima|string)'
        call s:ParseAST.CallIndex(a:state)

      else
        let finished = v:true

      endif
    else
      if a:state.Char() =~ '\v[([{]'
        call s:ParseAST.Parentheses(a:state)

      elseif a:state.Char() =~ '\d'
        call s:ParseAST.Number(a:state)

      elseif a:state.Char() =~ "\\v[\"']"
        call s:ParseAST.String(a:state.Char(), a:state)

      elseif a:state.Char() =~ '\v[+!-]'
        let op = a:state.Char()
        call a:state.NextChar()

        call s:ParseAST.Op(a:state, op)

      elseif a:state.Char() =~ '\v[a-zA-Z_@]'
        call s:ParseAST.Variable(a:state)
      else
        throw "Invalid expression!"
      endif
      let gotexpression = v:true
   endif
  endwhile
endf

function s:ParseAST.SubExpression(head, state)
  let head_node = s:ParseAST.CreateNode(a:head)
  let sub_state = a:state.EnterNode(head_node)
  call s:ParseAST.Expression(sub_state)
  call a:state.IgnoreWhitespace()
  return head_node
endf

function s:ParseAST.Variable(state)
  let var = a:state.Char()
  call a:state.NextChar()

  if a:state.Char() == ':'
    let var .= ':'
    call a:state.NextChar()
  endif

  if a:state.Char() =~ '\w'
    let var .= a:state.GetToken('\w')
  endif

  let var_node = s:ParseAST.CreateNode('variable')
  let var_node.value = var

  call a:state.AddChild(var_node)
endf

function s:ParseAST.Number(state)
  let number = a:state.GetToken('\d')

  let decimal = -1
  if a:state.Char() == '.'
    call a:state.NextChar()
    if a:state.Char() =~ '\d'
      let decimal = a:state.GetToken('\d')
    endif
  endif

  if decimal == -1
    let number_node = s:ParseAST.CreateNode('integer')
    let number_node.value = number
  else
    let number_node = s:ParseAST.CreateNode('decimal')
    let number_node.value = [number, decimal]
  endif
  call a:state.AddChild(number_node)
endf

function s:ParseAST.Op(state, op, ...)
  Optional binary v:false

  let op_node = s:ParseAST.SubExpression('op', a:state)
  let op_node.value = a:op

  if a:binary
    let dominant = v:false
    let top_op = {}
    let parent = {}
    while !dominant
      if op_node.children[0].head == "op"
        let next_op = op_node.children[0].value
        let dominant = s:ParseAST.opPriority.LessThan(a:op, next_op)
        if dominant
          let dominant_op = op_node
        else
          let dominant_op = remove(op_node.children, 0)
          let next_arg = remove(dominant_op.children, 0)
          call add(op_node.children, next_arg)
          call insert(dominant_op.children, op_node)
          if !empty(parent)
            let parent.children[0] = dominant_op
          endif
          let parent = dominant_op
        endif
        let top_op = (empty(top_op)? dominant_op : top_op)

      else
        let top_op = (empty(top_op)? op_node : top_op)
        let dominant = v:true
      endif
    endwhile

    call insert(op_node.children, a:state.PopChild())
    call a:state.AddChild(top_op)

  else
    call a:state.AddChild(op_node)
  endif
endf

function s:ParseAST.Parentheses(state)
  let paren_type = a:state.Char()
  call a:state.NextChar()
  let parens_node = s:ParseAST.CreateNode('parentheses')
  let parens_node.value = paren_type
  let parens_finished = v:false
  let parens_state = a:state.EnterNode(parens_node)
  let gotexpression = v:false
  while !parens_finished
    call parens_state.IgnoreWhitespace()
    if !parens_state.HasChars()
      throw "unexpected end of input: unclosed '".paren_type."'"
    elseif parens_state.Char() == CloseParens(paren_type)
      let parens_finished = v:true
    elseif parens_state.Char() == ',' && gotexpression
      call parens_state.NextChar()
    else
      call s:ParseAST.Expression(parens_state)
      let gotexpression = v:true
    endif
  endwhile

  call a:state.NextChar()
  call a:state.AddChild(parens_node)
endf

function s:ParseAST.BinaryOp(state)
  let op = a:state.Char()

  call a:state.NextChar()
  if a:state.HasChars()
    if op =~ '\v[&|]'
      if a:state.Char() != op
        throw "invalid operator ".op.a:state.Char()
      endif
      let op .= op
      call a:state.NextChar()
    elseif a:state.Char() == '='
      let op .= "="
      call a:state.NextChar()
    endif
  endif

  if !a:state.HasChars()
    throw "Missing right operand!"
  endif

  if op == '!'
    call a:state.BackTrackChar()
    let finished = v:true
  else
    call s:ParseAST.Op(a:state, op, v:true)
  endif
endf

function s:ParseAST.CallIndex(state)
  let ci_node = s:ParseAST.CreateNode('?')
  let ci_state = a:state.EnterNode(ci_node)
  call s:ParseAST.Parentheses(a:state)
  let parens_node = a:state.PopChild()
  if parens_node.value == '('
    let ci_node.head = 'call'
    let ci_node.value = ''
    call ci_state.AddChild(a:state.PopChild())
    call ci_state.AppendChildren(parens_node.children)
    call a:state.AddChild(ci_node)

  elseif parens_node.value == '['
    if len(parens_node.children) != 1
      throw "invalid indexing: exactly one element required in []"
    endif
    let ci_node.head = 'index'
    let ci_node.value = ''
    call ci_state.AddChild(a:state.PopChild())
    call ci_state.AddChild(parens_node.children[1])
    call a:state.AddChild(ci_node)
  endif
endf

function s:ParseAST.String(delimiter, state)
  let string_node = s:ParseAST.CreateNode('string')
  let escaped = v:false
  let finished = v:false

  call a:state.NextChar()

  while !finished
    let ch = a:state.Char()

    if escaped
      if ch == 'n'
        let string_node.value .= "\n"
      elseif ch == 't'
        let string_node.value .= "\t"
      elseif ch == 'r'
        let string_node.value .= "\r"
      elseif ch == 'c'
        let string_node.value .= "\c"
      else
        let string_node.value .= ch
      endif
      let escaped = v:false

    elseif ch == '\' && a:delimiter == '"'
      let escaped = v:true

    elseif ch == a:delimiter
      let finished = v:true

    else
      let string_node.value .= ch

    endif

    call a:state.NextChar()
  endwhile

  call a:state.AddChild(string_node)
endf

" Helper functions
"

" Create the parserState object from a string
"
function s:ParseAST.CreateParserState(string)
  let status = {'index': 0, 'line': 0}
  let root = s:ParseAST.CreateNode('top')

  return g:Class.ParserState._Create(a:string, status, root)
endf

function s:ParseAST.CreateNode(head)
  return { 'head': a:head, 'value': "", 'children': [] }
endf

" Function: DumpAST
"
" shows an vimscript ast in a human readable format
"
function DumpAST(ast,...)
  Optional space 0
  echo repeat(' ', a:space).(a:ast.head).(empty(a:ast.value) ? '' : ": ".(string(a:ast.value)))
  for child in a:ast.children
    call DumpAST(child, a:space+2)
  endfor
endf