+++ /dev/null
-function gettoken(tokenlist)
- local token = table.remove(tokenlist, 1)
- return token
-end
-
-function peektoken(tokenlist, n)
- if not n then
- n = 1
- end
- local token = tokenlist[n]
- return token
-end
-
-function expecttoken(token, expected)
- if not token then
- error("unexpected EOF", 1)
- end
- for k,v in pairs(expected) do
- if token.type == v then
- return token
- end
- end
- error("unexpected token "..token.type,1)
-end
-
-function parser_global(tokenlist, parsetree)
- -- GLOBAL = (VARIABLE | FUNCTION)
- local token = peektoken(tokenlist)
- while token do
- if token.type == "int" then
- local subtoken
- expecttoken(peektoken(tokenlist, 2), {"identifier"})
- subtoken = peektoken(tokenlist, 3)
- if not subtoken then
- error("unexpected EOF")
- end
- if subtoken.type == "(" then
- table.insert(parsetree, parser_function(tokenlist))
- elseif subtoken.type == ";" or subtoken.type == "=" then
- table.insert(parsetree, parser_variable(tokenlist))
- else
- error("unexpected token "..subtoken.type.." following 'int <identifier>'")
- end
- else
- error("unexpected token "..token.type)
- end
- token = peektoken(tokenlist)
- end
-end
-
-function parser_function(tokenlist)
- -- FUNCTION = TYPE IDENTIFIER ARGSLIST STMTLIST
- local myfunction = {}
-
- myfunction.type = "function"
- myfunction.returntype = parser_type(tokenlist)
- local token = expecttoken(gettoken(tokenlist), {"identifier"})
- myfunction.name = token.value
- myfunction.args = parser_argslist(tokenlist)
- myfunction.body = parser_stmtlist(tokenlist)
- return myfunction
-end
-
-function parser_type(tokenlist)
- -- TYPE = INT
- return expecttoken(gettoken(tokenlist), { "int" }).type
-end
-
-function parser_istype(tokenlist)
- if peektoken(tokenlist).type == "int" then
- return true
- end
- return false
-end
-
-function parser_argslist(tokenlist)
- -- ARGSLIST = ( [TYPE IDENTIFIER [, TYPE IDENTIFIER]*] )
- local token
- local argslist = {}
- local firstarg = true
- expecttoken(gettoken(tokenlist), { "(" })
- while true do
- local type, ident
- token = peektoken(tokenlist)
- if token.type == ")" then
- gettoken(tokenlist)
- return argslist
- end
- if not firstarg then
- expecttoken(gettoken(tokenlist), { "," })
- token = peektoken(tokenlist)
- end
- firstarg = false
- type = parser_type(tokenlist)
- token = expecttoken(gettoken(tokenlist), { "identifier" })
- ident = token.value
- table.insert(argslist, { type = type, name = ident })
- end
-end
-
-function parser_stmtlist(tokenlist)
- -- STMTLIST = { [( VARIABLE | STATEMENT | STMTLIST)]* }
- local token
- local stmtlist = {}
-
- stmtlist.type = "stmtlist"
- stmtlist.body = {}
- expecttoken(gettoken(tokenlist), {"{"})
- while true do
- token = peektoken(tokenlist)
- if token.type == "}" then
- gettoken(tokenlist)
- return stmtlist
- end
- if parser_istype(tokenlist) then
- table.insert(stmtlist.body, parser_variable(tokenlist))
- elseif token.type == "{" then
- table.insert(stmtlist.body, parser_stmtlist(tokenlist))
- else
- table.insert(stmtlist.body, parser_statement(tokenlist))
- end
- end
-end
-
-function parser_variable(tokenlist)
- -- VARIABLE = TYPE IDENTIFIER [ = TYPEINITIALIZER ] ;
- local variable = {}
- variable.type = "variable"
- variable.vtype = parser_type(tokenlist)
- variable.name = expecttoken(gettoken(tokenlist), { "identifier" }).value
- expecttoken(peektoken(tokenlist), { ";", "=" })
- local token = gettoken(tokenlist)
- if token.type == ";" then
- return variable
- end
- if token.type == '=' then
- if variable.vtype == "int" then
- variable.initializer = parser_getinitializer_int(tokenlist)
- else
- error("internal error")
- end
- expecttoken(gettoken(tokenlist), { ";" })
- return variable
- end
- error("internal error")
-end
-
-function parser_getinitializer_int(tokenlist)
- return expecttoken(gettoken(tokenlist), { "number" }).value
-end
-
-function parser_statement(tokenlist)
- -- STATEMENT = ; | EXPRESSION ; | (WHILE | IF)
- local token = peektoken(tokenlist)
- if token.type == ";" then
- return nil
- elseif token.type == "while" then
- return parser_while(tokenlist)
- elseif token.type == "if" then
- return parser_if(tokenlist)
- elseif token.type == "return" then
- return parser_return(tokenlist)
- else
- local result = parser_expression(tokenlist)
- expecttoken(gettoken(tokenlist), { ";" })
- return result
- end
-end
-
-function parser_while(tokenlist)
- -- WHILE = WHILE ( EXPRESSION ) CHUNK
- local result = {}
- result.type = "while"
- expecttoken(gettoken(tokenlist), { "while" })
- expecttoken(gettoken(tokenlist), { "(" })
- result.expression = parser_expression(tokenlist)
- expecttoken(gettoken(tokenlist), { ")" })
- result.chunk = parser_chunk(tokenlist)
- return result
-end
-
-function parser_if(tokenlist)
- -- IF = IF ( EXPRESSION ) CHUNK
- local result = {}
- result.type = "if"
- expecttoken(gettoken(tokenlist), { "if" })
- expecttoken(gettoken(tokenlist), { "(" })
- result.expression = parser_expression(tokenlist)
- expecttoken(gettoken(tokenlist), { ")" })
- result.chunk = parser_chunk(tokenlist)
- return result
-end
-
-function parser_return(tokenlist)
- -- RETURN [EXPRESSION] ;
- local result = {}
- result.type = "return"
- expecttoken(gettoken(tokenlist), { "return" })
- if peektoken(tokenlist).type == ";" then
- gettoken(tokenlist)
- return result
- end
- result.expression = parser_expression(tokenlist)
- expecttoken(gettoken(tokenlist), { ";" })
- return result
-end
-
-function parser_chunk(tokenlist)
- local token = peektoken(tokenlist)
- if token.type == "{" then
- return parser_stmtlist(tokenlist)
- else
- return parser_statement(tokenlist)
- end
-end
-
-function parser_expression(tokenlist)
- -- we support:
- -- ( ) + - < > == =
- -- of those, ( ) has precedence 0
- -- + - has precedence 3
- -- < > has precedence 5
- -- == has precedence 6
- -- = has precedence 13
-
- local operators = {
- ["*"] = { precedence = 2, associative = "left" },
- ["/"] = { precedence = 2, associative = "left" },
- ["+"] = { precedence = 3, associative = "left" },
- ["-"] = { precedence = 3, associative = "left" },
- ["<"] = { precedence = 5, associative = "left" },
- [">"] = { precedence = 5, associative = "left" },
- ["=="] ={ precedence = 6, associative = "left" },
- ["="] = { precedence = 13, associative = "left" }
- }
-
- -- Shunting yard algorithm
- local outstack = {}
- local opstack = {}
-
- local addopertooutstack = function(oper)
- assert(table.getn(outstack) >= 2, "attempted to add operator "..oper.value.." to stack containing "..table.getn(outstack).." elements")
- oper.right = table.remove(outstack, table.getn(outstack))
- oper.left = table.remove(outstack, table.getn(outstack))
- table.insert(outstack, oper)
- end
-
- while true do
- local token = peektoken(tokenlist)
- if token.type == "identifier" or token.type == "number" then
- gettoken(tokenlist)
-
- if peektoken(tokenlist).type == "(" then -- function call guyz!
- gettoken(tokenlist)
- local outp = { type = "funccall", name = token.value, args = {} }
- local token = peektoken(tokenlist)
- while token.type ~= ")" do
- table.insert(outp.args, parser_expression(tokenlist))
- token = expecttoken(peektoken(tokenlist), { ")", "," })
- if token.type == "," then
- gettoken(tokenlist)
- end
- end
- gettoken(tokenlist)
-
- table.insert(outstack, outp)
- else
- table.insert(outstack, { type = token.type, value = token.value })
- end
- elseif token.type == "(" then
- gettoken(tokenlist)
-
- local outp = parser_expression(tokenlist)
- expecttoken(gettoken(tokenlist), { ")" })
- table.insert(outstack, outp)
- elseif operators[token.type] then
- gettoken(tokenlist)
-
- while table.getn(opstack) > 0 and
- ((operators[token.type].associative == "left" and
- operators[token.type].precedence >= operators[opstack[table.getn(opstack)].value].precedence) or
- (operators[token.type].associative == "right" and
- operators[token.type].precedence > operators[opstack[table.getn(opstack)].value].precedence)) do
- addopertooutstack(table.remove(opstack, table.getn(opstack)))
- end
- table.insert(opstack, { type = "operator", value = token.type })
- elseif token.type == ")" or token.type == ";" or token.type == "," then
- break
- end
- end
-
- while table.getn(opstack) > 0 do
- addopertooutstack(table.remove(opstack, table.getn(opstack)))
- end
- assert(table.getn(outstack) == 1, "wrong number of objects ("..table.getn(outstack)..") on output stack after expression parse")
- return { type = "expression", value = outstack[1] }
-end
-
-function parse(tokenlist)
- local parsetree = {}
- parser_global(tokenlist, parsetree)
- return parsetree
-end
git.joshuawise.com / jwcc.git / blobdiff