I have begun on a PEG parser.
The goal is to build a grammar out of trees of combinators using sequence and either. I have some mistake in my sequence implementation, because I get false
as the output from this instead of an empty stream.
-- <library> -- Forward declare helper local wrap -- e: function | string -- return: Parser (Stream -> Stream?) function expect(e) local x = e if type(e) == "string" then x = function(n) return n == e end end return wrap(function(stream) if x( stream:first() ) then return stream:rest(), stream:first() else return false end end) end -- a, b: Parser -- return: Parse (Stream -> Stream?) function seq(a, b) return wrap(function(stream) local u = a(stream) if u then return b(stream) else return false end end) end -- wrappedCall(w, ...) is the same as w(...) for a value that has been -- `wrap`pped function wrappedCall(w, ...) return w["function"](...) end -- Allows + and * to be used as aliases for `either` and `sequence`. -- function -> function+* function wrap(f) local t = {["function"] = f} setmetatable(t, { __mul = seq, __call = wrappedCall}) return t end -- Stream<element> -> element function streamFirst(list) return list[1] end -- Stream -> Stream function streamRest(list) local t = {unpack(list)} table.remove(t, 1) return Stream(t) end -- string -> Stream function Stream(list) local s = {unpack(list)} s.first = streamFirst s.rest = streamRest return s end -- </library>
-- <client> -- string -> boolean function isLetter(s) return s:sub(1, 1):lower() ~= s:sub(1, 1):upper() end local name = expect(isLetter) local open, close = expect("<"), expect(">") local void = open * name * close local tokens = Stream {"<", "img", ">"} print( void(tokens) ) -- I expect this to print `table: ABCDEF`, but I get `false` -- </client>
Does anyone else have an idea of where I made a mistake? I regret not testing more incrementally...
I found the bug -- it was a little mistake in this line:
local u = a(stream) if u then return b(stream)
Looking at it, the definition of local u
is suspicious, since u
is only used in the condition.
It should have been this:
local u = a(stream) if u then return b(u)
so that the rest of the stream after what a
takes it put into b
.
Locked by Avigant
This question has been locked to preserve its current state and prevent spam and unwanted comments and answers.
Why was this question closed?