The thing to watch out for, is that formally, a parser is just something which can recognise a grammar with particular properties. A PEG (Parsing Expression Grammar) is simply a language grammar which can be written as a combination of the operators on the Wikipedia page. Any practical Context-Free Grammar will likely be also expressible as a PEG (though this is technically an open academic question).
The key thing to remember is that for the parser to be “complete”, it just needs to be able to take in a grammar (i.e. the definition the user writes for the parser) and the input, and either say “yes, this input follows the grammar” or “no, this input does not follow the grammar”. Hence, my statement was “now NimbleParsec can recognise any PEG grammar”, which of course is a prerequisite for “NimbleParsec can use a PEG grammar to turn binary input into some useful datastrucure”, which @OvermindDL1 is referring to. Unfortunately, this problem is far less interesting to researchers, and so “what features are missing” is probably better answered by reference to other popular PEG-style parsers rather than a paper or reference page
This is indeed how I was planning to handle XML tag closing/opening. I can see that right now @OvermindDL1 is writing an answer, but my guess is that the answer will again involve the fact that these are not really composable with the rest of the parsing definitions, but rather require a specific external function to be called (if they were composable, you could make a version of every single base combinator which also depends on or modifies some state). There’s also the local/global state thing which ExSpirit has, (I actually have no idea how that works or why it is useful though).
The academic PEG description is essentially the root math of it, but adhering to it strictly is a recipe for inefficiency and lack of abilities. What’s been learned by the industry over the past 20 years has come up with a few patterns that have become necessities.
State context handling is like think of parsing out an integer at one node, passing it ‘into’ potentially many nodes deep, where that gets added to another parsed integer, that then gets returned ‘up’ a multitude of nodes, where this is important is think about parsing a programming language where the syntax changes depending on a ‘type’ of something that got parsed or defined earlier, like think of this:
s = something()
s.blah
To determine what the s.blah should be doing, say a map lookup, a module function invocation, etc… depends on the type of s, which depends on the type of what something() is, which requires something() to have been typed prior (this is similar to how some ML languages work, not OCaml as it uses unique operators for everything though). Now imagine it is not just a simple . call but some entirely different branching structure, so you have to dispatch to different parsers based on some runtime type information of the system. In a modern PEG parser that is able to be figured out during parsing without ever needing to re-dispatch in to the parser. Like take the TreeMap in ExSpirit, it is designed as it is because it can be stored in state, so it could start empty, but then someone defines something in the language called my int and whatever comes after it should be parsed as an integer and passed in to it, all you have to do is add it to that and it ‘just works’. The Treemap (my implementation is very much a direct translation of the ones I’ve written in C++, I could write it more efficiently in a more Elixir’y way in Elixir) is also a common pattern in modern peg libraries.
A great example of a modern PEG library is C++'s Spirit2, a rewrite of Spirit1 based on everything learned prior (which made it the fastest PEG library anywhere, because it can quite literally optimize it’s constructs in very interesting ways). If you want to see a PEG library that is in heavy use and crazy efficient then that is the one to look at (Antlr is not bad though it focuses more on streaming so is not as efficient and thus different design considerations). An extra library of spirit-components is available as well that contains some less generic and more specialized pre-built elements like keyword handling (as I spoke above), confix (basically for handling things like beginning/ending tags more succinctly), distinct (like parsing if but not matching iffy based on a non-matching tail, among others, but all are built on the base Spirit library.
Spirit handles state far more cleanly than I do in ExSpirit (which I could emulate with more macro work), essentially given something like little_dword[_a = _1] >> advance(_a) >> little_dword it parses a little-endian dword (Spirit works on generic binaries, not just text, think Elixir/Erlang binary parsing with a lot more), then takes the first element of the result of it (most things only have one output, it fails to compile if you access an element that doesn’t exist for the given parser, it’s type safe), designated by the _1 and assigns it to a rule-specific ‘state value’ here names _a, which is then passed ‘into’ the advance component, which then skips that number of bytes, I.E. this parses a dword-sized ‘size’ header like 00 00 00 04 and then skips that many bytes to skip over this record, then it parses another little-endian dword (this you can do in Elixir binary matching, hence why I’m using this example to make it easy to reason about how Elixir/Erlang binary matching/parsing has similar features to modern PEG state handling).
The advance(_a) is passing the data ‘into’ the rulestack, it could be your own rule that takes the argument and uses it inside it as it wishes as well, and it returns data by packing them into result elements, this is why ExSpirit allows you to store rule specific named state that doesn’t exist in inner rules and isn’t passed up, but you can return data via result and you can pass data ‘into’ via arguments, modeling the same as C++'s Spirit.
This page on Spirit’s docs talks about the basic PEG setup, which is basically just:
Sequences: Parse the first then the second
Alternatives: Parse the first, if it fails then parse the second
Loops: Parse a number of times until the parser fails then concat all successful parses up to then
Difference: Parse something that does not match something else (this is the basic of the lookahead).
Now these are not always the most efficient, especially Difference’s performance is pretty abysmal, hence why specialized things like lookahead and made.
Spirit splits up the ‘types’ of it’s components into a few kinds:
Primitives: A simple thing like int_ that parses and returns data, it can potentially take arguments (like int_ accepts things like size, range, radix, etc… etc…) but it does not accept any components as arguments.
Compound: Like primitives but they also accept other components, so this would be like a repeat operator (repeat in ExSpirit, * or + in C++ Spirit) or even the basic sequence (which takes multiple ordered components by default, seq or |> in ExSpirit and >> in C++).
Rule: A collection of components scoped, this is like ‘naming’ a set of of components, essentially it corresponds to a function in C++ except it’s defined in the type system instead of as a runnable function (defrule in ExSpirit, rule<Iterator, return_type(rule, args, here)> in C++). This also provides a point to separate the code so the compiler can choose whether to inline it or not where used (where all compound and primitive components are force inlined for efficiency). Say you made a rule like rule<Iterator, vector<int>()> ints = int_ % ',' in C++ Spirit that parses a comma separated list of integers and returns them in an array named ints then you could use it elsewhere like any other component like "list: " >> ints >> eol or so. If the compiler doesn’t optimize it then there is a slight cost of runtime speed, however it does reduce compilation times by using more rules.
Grammar: This is a collection of rules, it adds a full synchronization point, grammars are not eligible for being inlined across other grammars. Generally you only have one grammar but if you have a huge language to parse then you can split up multiple grammars to add points where the compiler is not allowed to optimize across, which can SIGNIFICANTLY improve compilation time in complex parsers at the cost of a bit of runtime speed.
So the basic syntax of a component is component_name or component_name() (either works, though if it has arguments to pass in then you must use the component_name(args...) form).
Every component can have an associated semantic action delinated by [/], so something like int_[&blah] will call the function blah with the result of the parsed integer if the blah is typed as int blah(int), if blah is otherwise typed as int blah(context&, int) (maybe the other order, I forget…) then it gets the full context data passed in so it can access locally defined state variables, parse location (column/line/etc..) and a lot more information. The above [_a = _1] is essentially just defining an inline lambda function of [[](auto context, auto val) {context.putState<_a>(val)} ] or something like that (that’s not a spirit feature, rather a phoenix library feature, which is very often used with spirit due to the succinctness of it’s lambdas). A semantic action can be any ‘callable’ type that fits any of the proper signatures (or it fails to compile).
The basic set of components included with Spirit directly (either to significantly reduce repeated code or for efficiency reasons because the basic PEG constructs are way too inefficient) are mostly defined here. The usual ‘efficient’ ones like character and string and number parsers are of course included, among others, but the especially interesting ones are the parser directives, this includes things like:
lexeme: disables the skip parser but pre-skips
no_skip: disables the skip parser with no pre-skip
raw: Parses however but returns the entire range of source text instead, regardless of the returned values. Without this then parsing twice is necessary.
expect: Throws an exception with the currently set error if there is an error, otherwise no-op. Without this then errors will not be accurate in many cases.
repeat: Min-max specific repeating call. Without this input can be repeatedly parsed when it was not necessary.
Among many others.
Spirit also defines the concept of a skip_parser, this is a parser passed into the parse call to act as an omitted skipper that is auto-placed between every terminal component (a component that parses a base thing like ‘int_’, but something like repeat would run the skip parser between each iteration and before the first). This is often used with spaces for example, so given parse(input.begin(), input.end(), int_ % ',', blank) would parse 1 , 2 , 3, 4,5,6 , 7 the same as 1,2,3,4,5,6,7, but without the blank skip parser then only 1,2,3,4,5,6,7 would parse and any spaces would fail. This is generically useful for a lot of things and implementing it on the user-code otherwise means adding in a whole LOT of needless noise among every-single-parser that is created. The skip parser can be prevented from working via lexeme/no_skip in C++ Spirit for a given component.
So yes in general the PEG ‘spec’ is simple and doesn’t have much, but it is also crazy inefficient, modern PEG libraries have found patterns that work around it to get a more useful base set of components.
Another thing Spirit can do is also let you define a ‘parser’ that runs the other way, you feed it the data structure of whatever internal format you have and it sends out a binary stream. That is not a feature I added in yet in ExSpirit but it was open to it.
Basically yeah, there is a difference between PEG the Spec and PEG as is implemented in modern libraries, I tend to use what is done in modern libraries as that is the part that is actually useful considering how dreadfully inefficient the base Spec is.
Correct, but it is such a universal ‘convenience’ that it is often baked into about every library as it can both substantially improve error messages while also improving performance.
Eh, the first (state handling) is not so much a convenience, it is what allows PEG’s to go from Context Free parsers to Context Sensitive. There are many ways to handle state, some more efficient then others of course.
Efficient XML parsing is the traditionally ‘simple’ use-case, it is context sensitive to match the closing tag with the opening tag, otherwise you need a second pass over the complete data. Now the second pass (like using a semantic action in C++ Spirit) can of course be used to enforce this specific case, but in actual programming languages it is often common for the parser to ‘change’ based on state, and thus the XML example is a simplified form of that where the parser changes (what the ending tag matches to) based on prior state (what the opening tag was parsed as), so being able to do that without the ending pass, I.E. being able to change the actual parser functionality based on runtime state is highly important for parsing most languages efficiently (otherwise you tend to have to go to a multi-stage parser where you first tokanize, then fixup the tokens, then generate the AST, then convert the AST to the internal format, where modern PEG libraries can generate the internal format directly without needing to generate the huge amount of intermediate data).
Correct, you’ll have to verify the end tag via a function after the parsing of the (anything) end tag is complete, simple in the XML case, but not so in more complex cases like parsing branches differently based on the types of parsed data.
Super popular with interpreters, like implementing a mini language that calculates the values as it is parsed, so the returned parsed value is the result of the calculation, regardless of any variables set, scopes, etc… Local is being able to hold data within a specific rule, like what the value of the parsed opening tag was in XML so you can reuse it to adjust the parser for the closing tag.
To expand on this, say a parser for the Elixir language was made in C++ Spirit or ExSpirit, you can create a new ‘tag’ function or component that wraps the result in a 3-tuple like Elixir’s AST is, with the middle context metadata including the line and column parsing information, perhaps the byte location in the input stream, etc… This is something not currently possible in NimbleParsec as it doesn’t have such context information.
This is posible in NimbleParsec! You can add line and column metadata with no problems since about the second version came out. Are you sure you’ve looked at the most recent docs? You can also add information from the context if you wish. Tagging the generated AST with NimbleParsec, although not as convenient as with ExSpirit (IMO), is perfectly possible.
The eaisest way to explain what’s missing is to look at the spec of the post_traverse function (the new name for the old traverse function): post_traverse(combinator \\ empty(), to_post_traverse, call) the call argument is a function, which takes the parser state as an argument (including the context, of course) and it must return a 2-tuple of the form {acc, context}, where the context is the new context and acc is the result you append to the list of results. This does not allow you to consume any input. You can do things to the result depending on the input that has already been consumed and on the input you haven’t yet consumed, but you can’t consume nay new input.
This means you can’t change the input you’re consuming based on the contexts. For NimbleParsec to allow context-sensitive combinators, the call function would have to build a new combinator at runtime and apply it to the rest of the input. Let’s say you want to parse a grammar of the form <n>:<n integers separated by commas>. An example is this: 5:1,4,55,6,7. To parse this, you have to consume the character ?5, and then build a new parser that recognizes exactly 5 integers (it could fetch the number 5 dynamically from the context). This is an example of a context-sensitive language, and one which I think NimbleParsec can’t handle currently.
Now, implementing a state system like this sounds like a lot of work, because you’d have to have “dynamic” versions of the combinators (besides the “static” ones you already have). This complicats the design a lot, and stateful combinators are much harder to optimize into the kinds of pattern matches that NimbleParsec is using now.
We could have a dynamic choice, where you could choose at runtime which combinator to dispatch to:
dynamic([
foo: combinator1,
bar: combinator2,
], mfa)
And the mfa returns either :foo or :bar but it is still limited because the combinators pointed out by :foo and :bar still aren’t dynamic, so you can’t say something should happen exactly 5 times. You would still have to write a code in a way that parses n entries and then check afterwards (using post_traverse) that you had exactly 5 entries. I have no idea if this is good enough though.
And somehow the returned combinator must be interpreted at runtime by the parser (instead of compiled into something much more efficient). With a slight change to post_traverse (or with the addition of a new “primitive” combinator) I believe I could implement context-sensitive parsers as “user-level” code.
I have not apparently, when I wrote my benchmark where NimbleParsec bested ExSpirit handedly it did not exist at the time! Woot!
To be honest I find that file pretty long and unreadable, I’m not sure that’ s a good example. Lots of seemingly random functions doing things that the parser should do and so forth. I’m pretty sure I could write a set of matcher heads to parse the same in significantly shorter space? Hmm, let me write a parser how I usually did in erlang:
defmodule SimpleXML do
def parse(inp) do
{rest, [xml]} = xml({inp, 1, 1, 0})
{:ok, xml, rest}
catch s when is_binary(s) -> {:error, s}
end
def xml({"<" <> inp, l, c, o}) do
{inp, name} = tag({inp, l, c+1, o+1})
xml_head(inp, name)
end
def xml(inp), do: {inp, []}
def xml_head({">" <> inp, l, c, o}, name), do: xml_rest({inp, l, c+1, o+1}, name)
def xml_rest(inp, name, children \\ [])
def xml_rest({"</" <> inp, l, c, o}=ct, name, children) do
{inp, ^name} = tag({inp, l, c+2, o+2})
xml_done(inp, name, children)
rescue MatchError -> err(ct, "Invalid closing tag does not match start tag of #{name}")
end
def xml_rest({"<" <> _inp, _l, _c, _o} = ct, name, children) do
{ct, xml} = xml(ct)
xml_rest(ct, name, xml ++ children)
end
def xml_rest({<<_::integer-size(8), _::binary>>, _l, _c, _o} = ct, name, children) do
{ct, txt} = text(ct)
xml_rest(ct, name, txt ++ children)
end
def xml_rest(ct, name, _children), do: err(ct, "XML Parsing failure at #{name}")
def xml_done({">" <> inp, l, c, o}, name, children) do
{{inp, l, c+1, o+1}, [{name, [line: l, column: c, offset: o], :lists.reverse(children)}]}
end
def tag(inp, t \\ "")
def tag({<<ch::integer-size(8), inp::binary>>, l, c, o}, t) when ch in ?a..?z or ch in ?A..?Z, do: tag({inp, l, c+1, o+1}, <<t::binary, ch::utf8>>)
def tag(inp, t) when byte_size(t)>0, do: {inp, String.to_atom(t)}
def tag(ct, _t), do: err(ct, "Empty tag not allowed")
def text({inp, l, c, o}), do: text(inp, inp, l, c, o)
def text(orig, "\n" <> inp, l, _c, o), do: text(orig, inp, l+1, 1, o+1)
def text(orig, "<" <> _ = inp, l, c, o), do: text_done(orig, inp, l, c, o)
def text(orig, "", l, c, o), do: text_done(orig, "", l, c, o)
def text(orig, <<_::integer-size(8), inp::binary>>, l, c, o), do: text(orig, inp, l, c+1, o+1)
def text_done(oinp, inp, l, c, o) do
offset = byte_size(oinp) - byte_size(inp)
<<result::binary-size(offset), _::binary>> = oinp
{{inp, l, c, o}, [result]}
end
def err({inp, l, c, _o}, msg), do: throw "ERROR at #{l}:#{c}: #{msg}\nTrailing Data: `#{String.slice(inp, 0, 24)}`"
end
inputs = [
"<foo></foo>",
"<foo><bar></bar></foo>",
"<foo>bar</foo>",
"<foo><bar>baz</bar></foo>",
"<foo><bar>one</bar><bar>two</bar></foo>",
"<>bar</>",
"<foo>bar</baz>",
"<foo>bar</foo>oops",
"<foo>bar"
]
for input <- inputs do
IO.puts(input)
IO.inspect(SimpleXML.parse(input))
IO.puts("")
end
Which I find even shorter still and significantly more readable than both the prior. If the parser doesn’t gain any code over doing it just manually via normal pattern matching, than why use the library?
Hmm…
defmodule Testering do
use ExSpirit.Parser, text: true
def parse(input) do
parse(input,
uint()
|> put_state(:count, :result)
|> lit(?:)
|> seq([uint(), get_state_into(:count, repeat(lit(?,) |> uint(), &1-1, &1-1))])
)
end
end
Testering.parse("5:1,4,55,6,7")
Testering.parse("5:1,4,55,6,7,8,9")
As you can see in the rest it didn’t parse anything beyond the number, leaving it for later parsers. And with a simple alt I can make it handle the 0 case as well (assuming that should even be a valid parse).
Yes, I’m perfectly aware of how trivial it is to do this in ExSpirit. After al, I’ve used the context-sensitive features of ExSpirit to write a pretty cool HTML lexer which was capable of highlighting matching opening and closing tags, something which seems impossible with NimbleParsec. The question is how to implement these features in NimbleParsec’s architecture.
I guess so. But the main problem is not performance. The way NimbleParsc works is by generating an AST for a parser and then compiling the whole thing. It makes use of the fact that some things are static and others are dynamic to optimize code generation (last time I looked, it might have changed). With something like this, you have to have an anonymous function than generates a combinator at runtime, which is something compeltely different from what NimbleParsec is doing.
It might require you to have two classes of componentes, some static and some dynamic. But then again, it might not. I could see something like:
where something is a combinator that (statically) returns an expression, which the get_state_into macro would compile into something different. Basically get_state_into would be an alterantive compiler for the same kind of expressions which are compiled by defparsec.
If you’re smart when coding get_state_into, you can optimize things so that most of the work is done at compile time instead of at runtime. I haven’t seen how ExSpirit does it though (I’ll look at it ASAP, the code seems very simple).
