CHKDEBUG = false

# parseChecker function summary
# =============================
# (parseChecker tokenlist) - to check if the tokenlist represents a correct program
# (parseChecker tokenlist component position) - to check if a set of tokens beginning
#    at the specified positon represents the indicated type of program component
#
# a parsing-checker for the IttyBitty language
#    checks if a source code program is syntactically correct
# expects three parameters:
#      the overall token list for the source code
#      the type of language component we are checking for next in the token list
#          (defaulting to an entire program)
#      the token list position parsing for the component should begin at
#          (defaulting to the start of the list)
# returns two values:
#     if the component passes syntax checking
#        it returns true and the position of the token immediately after the component
#     otherwise
#        it returns false and the position originally passed to the function
def parseChecker(tokenlist, component="Program", position=0)

if CHKDEBUG then
   puts "\n---parsing #{component} from position #{position} (#{tokenlist[position]}) ---"
end

    # make sure we're not off the end of the token list
    if tokenlist.length <= position then
       return false,tokenlist.length
    end

    # make sure we can recognize the next token
    tok = tokenlist[position]
    if tok[0] == 'unknown' then
       puts "Error: unknown token encountered #{tok[1]}"
       return false,position
    end

    # based on the component type, try to parse the tokenlist appropriately
    case component
        when "Program"
            # Only one rule can buld a program:
            #    Program --> StatementList
            parsetree,pos = parseChecker(tokenlist, "StatementList", position)
            if parsetree == false then
               return false, position
            elsif tokenlist.length > pos then
               puts "---parsing successful(?) but unused tokens from position #{pos} ---"
               return false, position
            end
            return true, pos

        when "StatementList"
            # Two rules can build a StatementList:
            #    StatementList --> Statement
            #    StatementList --> Statement StatementList

            # both rules begin with a Statement, so if that fails
            #    then this is not a StatementList
            parsetree,pos = parseChecker(tokenlist, "Statement", position)
            # StatementList --> Statement
            if parsetree == false then
               return false,position
            else
               # The second rule assumes there are more Statements,
               # so try to recurse on StatementList, if the recursion
               #    succeeds we can simply return,
               # but if it fails we must be able to "roll back" and
               #    return the success of the first rule

               # StatementList --> Statement StatementList
               backuppos = pos
               backuptree = parsetree
               parsetree,pos = parseChecker(tokenlist, "StatementList", pos)
               if parsetree == false then
                  return backuptree,backuppos
               else
                  return parsetree,pos
               end
            end

        when "Statement"
           # A Statement can be build by any one of four rules:
           #     Statement --> Print
           #     Statement --> VarAssign
           #     Statement --> Loop
           #     Statement --> Conditional
           # Check each rule in turn, quit and return true if one succeeds,
           #    return false only if all four rules fail

           # Statement --> Print
           parsetree,pos = parseChecker(tokenlist, "Print",position)
           if parsetree != false then
              return true,pos
           end

           # Statement --> VarAssign
           parsetree,pos = parseChecker(tokenlist, "VarAssign",position)
           if parsetree != false then
              return true,pos
           end

           # Statement --> Loop
           parsetree,pos = parseChecker(tokenlist, "Loop",position)
           if parsetree != false then
              return true,pos
           end

           # Statement --> Conditional
           parsetree,pos = parseChecker(tokenlist, "Conditional",position)
           if parsetree != false then
              return true,pos
           end

           # all four rules failed to build a Statement
           return false,position

        when "VarAssign"
           # only one rule builds a VarAssign:
           #    VarAssign --> variable = Expression

           # if there aren't enough tokens we can bail out now
           if tokenlist.length < position+3 then
              return false,position
           end

           # the variable and operator are just one token each, grab them
           var = tokenlist[position]
           op = tokenlist[position+1]

           # check those for validity, and if valid then see if an Expression follows
           errFound = false
           if var[0] == 'variable' then
              if op[0] == 'assignop' then
                 parsetree,pos = parseChecker(tokenlist, "Expression",position+2)
                 if parsetree != false then
                    return true,pos
                 end
                 puts "Error: unrecognized expression after #{op[1]}"
                 errFound = true
              end
              if !errFound then
                 puts "Error: invalid handling of variable #{var}"
              end
           end
           return false,position

        when "Print"
           # we can bail out now if there are not enough tokens left to build a Print
           if tokenlist.length < position+2 then
              return false,position
           end

           # all the print rules begin with a print token, check that next
           prt = tokenlist[position]
           if prt[0] != 'keyword' or prt[1] != 'print' then
              return false,position
           end

           # there are two rules that can build the print operands:
           #    Print --> print Text
           #    Print --> print Value

           # try the Value rule first, if it fails then try the Text rule
           parsetree,pos = parseChecker(tokenlist, "Value", position+1)
           if parsetree != false then
              return true,pos
           end
           # Print --> print text
           parsetree,pos = parseChecker(tokenlist, "Text", position+1)
           if parsetree != false then
              return true,pos
           end

           # here we know there's an error: we had a print token but no valid operands
           puts "Error: invalid print attempt after #{tokenlist[position+1]}"
           return false,position

        when "Value"
           # we know we need at least one token for the Value
           if tokenlist.length < position+1 then
              return false,position
           end

           # there are two rules for building a Value:
           #    Value --> variable
           #    Value --> integer

           # grab the next token, and see if it matches either of the two allowable types
           tok = tokenlist[position]

           # Value --> variable
           if tok[0] == 'variable' then
              return true,position+1

           # Value --> integer
           elsif tok[0] == 'integer' then
              return true,position+1
           end

           # the token does not represent a Value
           return false,position

        when "Conditional"
           # only one rule builds a Conditional:
           #    Conditional --> if Condition Block

           # grab and check the token that should match 'if':
           if tokenlist.length <= position then
              return false,position
           end
           iftok = tokenlist[position]
           if iftok[0] == 'keyword' and iftok[1] == 'if' then
              # we do have an 'if', so check the Condition portion
              parsetree,newpos = parseChecker(tokenlist, "Condition",position+1)
              if parsetree != false then
                 # the Condition also passed, check the Block
                 parsetree,lastpos = parseChecker(tokenlist, "Block",newpos)
                 if parsetree != false then
                    return true,lastpos
                 else
                    puts "Error: invalid block with if statement"
                 end
              else
                 puts "Error: invalid condition in if statement"
              end
           end
           return false,position

        when "Loop"
           # only one rule builds a Loop:
           #    Loop --> while Condition Block

           # grab and check the token that should match 'while':
           if tokenlist.length <= position then
              return false,position
           end
           whiletok = tokenlist[position]
           # Loop --> while Condition Block
           if whiletok[0] == 'keyword' and whiletok[1] == 'while' then
              # we do have a 'while', so check the Condition portion
              parsetree,newpos = parseChecker(tokenlist, "Condition",position+1)
              if parsetree != false then
                 # the Condition also passed, check the Block
                 parsetree,lastpos = parseChecker(tokenlist, "Block",newpos)
                 if parsetree != false then
                    return true,lastpos
                 else
                    puts "Error: invalid block with while loop"
                 end
              else
                 puts "Error: invalid condition in while loop"
              end
           end
           return false,position

        when "Condition"
           # only one rule builds a Condition:
           #    Condition --> ( Value comparisonop Value )

           # the condition should be 5 tokens long, check we have them
           if tokenlist.length < position+5 then
              return false,position
           end

           # capture and check the opening bracket
           br1 = tokenlist[position]
           errFound = false
           if br1[0] == 'bracket' and br1[1] == "(" then
              # we have an opening bracket, check the first Value
              parsetree,pos = parseChecker(tokenlist, "Value",position+1)
              if parsetree != false then
                 # the first Value is also ok, check the comparison operator
                 op = tokenlist[position+2]
                 if op[0] == 'compop' then
                    # the operator is also ok, check the second value
                    parsetree,lastpos = parseChecker(tokenlist, "Value",position+3)
                    if parsetree != false then
                       # everything else is ok, check for a closing bracket
                       br2 = tokenlist[position+4]
                       if br2[0] == 'bracket' and br2[1] == ')' then
                          return true,position+5
                       else
                          puts "Error: closing ) expected in condition"
                          errFound = true
                       end
                    else
                       puts "Error: invalid value in condition"
                       errFound = true
                    end
                 end
              end
              if !errFound then
                 puts "Error: invalid condition syntax"
              end
           end
           return false,position

        when "Block"
           # only one rule builds a Block:
           #    Block --> { StatementList }

           # check the opening bracket
           if tokenlist.length < position+1 then
              return false,position
           end
           br1 = tokenlist[position]
           if br1[0] == 'delimiter' and br1[1] == '{' then
              # we have an opening bracket, check the statements inside the block
              parsetree,pos = parseChecker(tokenlist, "StatementList",position+1)
              if parsetree != false then
                 if tokenlist.length < pos+1 then
                    return false,position
                 end
                 br2 = tokenlist[pos]
                 # we have a valid list of statements, the closing bracket should be next
                 if br2[0] == 'delimiter' and br2[1] == '}' then
                    return true,pos+1
                 else
                    # whatever was after the statement list was not a closing bracket
                    puts "Error: } expected at end of block"
                 end
              else
                 # we had an opening bracket but no valid statement(s)
                 puts "Error: invalid statement in block"
              end
           else
              # we expected a { to begin the block
              puts "Error: { expected with block"
           end
           return false,position

        when "Expression"
           # there are two rules that build an Expression:
           #    Expression --> Value
           #    Expression --> Value mathop Expression

           # Both rules begin by grabbing a value, so capture and check that
           parsetree,pos = parseChecker(tokenlist, "Value",position)
           if parsetree != false then
              # if there is nothing left then the value was the end of the expression and is ok
              if tokenlist.length <= pos
                 return true,pos
              end

              # if we had a value, we should check and see if there is more to the expression,
              #    but if that fails we still need to remember the first Value worked ok
              backuppos = pos
              backuptree = parsetree
              # Expression --> Value mathop Expression
              op = tokenlist[pos]
              if op[0] == 'mathop' then
                 parsetree,pos = parseChecker(tokenlist, "Expression",pos+1)
                 if parsetree != false then
                    # we got the sub expression as well
                    return true,pos
                 end
                 # if there was a value and operator but no further expression
                 #    then we know there's an error
                 puts "Error: invalid expression after #{op[1]}"
              end

              # the original Value was ok, but there was no further expression
              return true,backuppos
           end
           return false,position

        when "Text"
           # only one rule builds a block of text:
           #    Text --> " WordList "

           # it must begin with a quote, so check that
           if tokenlist.length <= position then
              return false,position
           end
           q1 = tokenlist[position]
           if q1[0] == 'quote' then
              # there must be a word list inside the quotes, check that
              parsetree,pos = parseChecker(tokenlist, "WordList",position+1)
              if parsetree != false then
                 if tokenlist.length <= pos then
                    # whatever follows the quote is not a valid word list
                    puts "Error: unexpected end of quoted string"
                    return false,position
                 end
                 # the text must end with a quote, so check that
                 q2 = tokenlist[pos]
                 if q2[0] == 'quote' then
                    return true,pos+1
                 else
                    puts "Error: not a quote after text block #{q2[1]}"
                 end
              end
              puts "Error: invalid quoted string content"
           else
              puts "Error: not a quote to begin text block #{q1[0]}"
           end
           return false,position

        when "WordList"
           # two rules build a WordList:
           #    WordList --> text
           #    WordList --> text WordList

           # both require the next token to be of type 'text', so check that
           if tokenlist.length <= position then
              return false,position
           end
           word = tokenlist[position]
           if word[0] == 'text' then
              # if the first token is ok, check if there are more
              parsetree,pos = parseChecker(tokenlist, "WordList",position+1)
              if parsetree != false then
                 # we successfully grabbed more words
                 return true,pos
              end
              # there weren't any more words, just the first one
              return true,position+1
           end
           return false,position

        else # this else is for the overall component case
           puts "Error, invalid component type specified: #{component}"
           return false,position
    end

    # return the results of parsing as the suggested component type
    #    should not be reachable?
    puts "---???Reached default end of parse???---"
    return parsetree,position
end