LL and LR in Context: Why Parsing Tools Are Hard (2013)
blog.reverberate.org
blog.reverberate.org
I tried several time to explain why I think people should use parser generators and the conclusion of this article express my point of view perfectly. The fact that we have a very good parser generator in OCaml (and Coq!)[1] really helps here.
I still think that ambiguities of the third kind, "Type/variable ambiguity", are a design issue and your grammar should be changed, because it's going to be completely ambiguous for humans too.
loop @a
...
endloop
loop
@a
...
endloop
You just end up making a grammar with really weird rules about where newlines can or cannot be put, and comments that this should not be changed. Oh, and a BIG test suite.
Once you've dealt with the grammar then you'll only have bugs in the compiler and runtime semantics to emulate, and language implementations often have an exciting set of those.
Edit: this is actually explained much better in the article.
Incorrect. The choice is explicit. Ambiguity gone, period. If the order makes some of the branches unreachable, it can be easily statically proven. In practice this is more than enough and does not require nearly as much effort as all the other parsing approaches.
As Meredith and Sergey explain in their talk[1] at 28c3, Turing complete input and parsers that don't validate the input are creating a "weird machine" just waiting to be programmed in malicious and unexpected ways.
[1] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit...
Do you think the use of parser generators is practical also for performance-critical binary data? For example video streams? (I've never parsed one but I imagine they could be so optimized that it could be impractical to do it with a generic parser generator).
What formats are examples of complex structure where parser generators are practical?
For my personal needs, I've been getting along very well with plain text relational data. Like
numPersons 2
numAncestors 1
person john "John Doe"
person jane "Jane Dane"
ancestor john jane
If I leave away the num* fields above, the parser would need one token of lookahead. What type of grammars are these two versions?
That's not a question I consider very important, because prioritizing performance over correctness (safety) is irresponsible.
That said, using a parser generator shouldn't have a significant impact on performance. When a network is involved, the parser isn't going to be the bottleneck anyway.
> video
I am not very familiar with the details of video formats, but I would suggest trying the parser combinator library Meredith mentions in the talk in my previous [1], known as "hammer"[2]. It's very easy to use, and it has specific support for bit-level parsing of binary formats.
> numPersons 2
I highly recommend not using formats like this, because it's more complex than deterministic context-free. Using a length field requires that the parser remember state. It's also redundant information, creating the possibility of a miss-match between the number specified in "numPersons" and the actual number of rows.
A format that uses s-expressions would be safer and more easier to implement:
(ancestry
(ancestor
(person john "John Doe")
(person jane "Jane Doe")
)
)
> That's so trivial that I would never want to depend on a parser generator
Is it really "trivial"? Or is your parse that you write in 10 minutes accepting ambiguous or invalid data? Is it actually checking for all of the error conditions? For most real-world grammars, it's unlikely you will catch all of the subtle ambiguities, interactions, and edge cases.
The benefit of using a parser generator is that those entire classes of bugs are impossible.
> check (relational) integrity
In the trivial example you gave, you shouldn't have a grammar that requires checking relational integrity. In a more complex grammar, such checks would be the job of whatever is walking the AST that the parser returns. Parsers interpret syntax, not semantics.
> If I leave away the num* fields above, the parser would need one token of lookahead.
You need at least one token of lookahead anyway. Including the num* fields means the parser needs to remember and manage state.
> I highly recommend not using formats like this, because it's more complex than deterministic context-free.
Barely. It avoids the complexity of look-ahead and reallocating growing buffers.
> A format that uses s-expressions would be safer and more easier to implement:
Trees are unsuitable for almost anything computationally, at least as authoritative representation. Prefer flat. (Widget hierarchies are one of a few counterexamples where the tradeoffs are different).
This s-expression you gave is much more complex to parse. Granted, you get parsing as a tree for free. But then you have to go inside the tree and see what's there. That there are two persons per ancestor, etc. Navigating trees is hard.
> Is it really "trivial"? Is it actually checking for all of the error conditions?
Yes. Yes. Of course. It's the most boring code in the world. Parse numbers, allocate arrays correspondingly, parse each following table in a loop corresponding to the numbers parsed. You can do it all using scanf. Bail out as soon as a bad line comes in. 20 lines.
> The benefit of using a parser generator is that those entire classes of bugs are impossible.
Yeah. Well, they are not impossible. They are only possible in the parser generator. And interfacing a parser generator is itself not necessarily trivial. Plus, dependencies are a maintenance burden.
The other approach is to make the design so simple (like the relational example) to make them (the classes) nonexistent.
> You need at least one token of lookahead anyway.
Not in the example I gave.
> Including the num* fields means the parser needs to remember and manage state.
I would hardly call that state. It's an immutable number, initialized in sequential code without real data dependencies (the data dependencies are resolved in the format -- you can not go wrong parsing it).
struct Model {
int numPersons;
int numAncestors;
struct Person *person;
struct Ancestor *ancestor;
};
struct Model {
int numPersons;
int numAncestors;
struct string *personname;
struct string *persondesc;
struct string *ancestorancestor;
struct string *ancestordescendant;
};
With stuff like your problem, I can never be sure the data is clean, so I always default to a format like CSV or JSON and use standard library tools. I would shudder to have to work with that kind of data in C / C++ for the very reason you're asking these questions in this thread. It's low-level code for a high-level task. You're bound to fuck it up eventually and not foresee an edge case.
But it would depend on what you want to do with the data. If you're walking trees, then you're going to want to store them in memory as trees. Whichever memory structure would be the most efficient in the algorithm you've got planned.
Personally, since it's relational, I wouldn't bother with file storage at all and just dump it into a relational database, even if it's just SQLite. That would give you the most flexibility.
Come on, what can you mess up splitting lines into fields?
I'm not specific to C/C++. It's just often the easiest/most straightforward thing to do as opposed to popular opinion. C structs are a good tool for concise description of data inter-relations. (Ownership or mutability are totally orthogonal questions).
Conversely, how do you check integrity of JSON inputs (meaning the tree as it was returned from a JSON parser library)? The odds are not. Much more work since you don't know at each step precisely what has to come.
Yeah, sqlite3 is a popular option. But it's more an alternative answer to the question of in-memory storage. It's not particularly suited as a human-friendly data interchange format.
But unknown numbers of captures indicates a non-regular grammar. You should simplify the grammar so you don't need them. I'd have each line adhere to /^(\w+) (.*)$/, and use the first capture to determine which regex you use to read the rest of the line. But this will break if there are newlines in the input. Hopefully it will error out if it gets a bad line, and even if it does, it will pass bad data in that case.
> Come on, what can you mess up splitting lines into fields?
Really depends on how clean your inputs are. A short list of things that can mess you up: newlines in your data, encoding inconsistencies, delimiters in your data. You have to handle all these manually if you write your own parser or risk unclean data entering the boundaries of your system. If you're in full control of your input, sure, go nuts, but I'd prefer a more robust solution because you never know what you're going to want to feed into it in the future.
A standard format may have inconsistencies in implementation, but the format itself bakes in the solution to these problems, and also tends to have somewhat-useful error messages when they break.
> Yeah, sqlite3 is a popular option. But it's more an alternative answer to the question of in-memory storage. It's not particularly suited as a human-friendly data interchange format.
My suggestion would be to treat these as separate problems and not expect one solution to provide both of them. Why do you need human-friendliness? To me, the usual way to provide that is with an application and not a data format. I could knock one of those up pretty quickly with Rails and an admin backend, I'm sure you'd have your own way of doing that that you're comfortable with. I will use command-line applications if Rails is too heavyweight, I do this for a lot of my utility apps.
> I think using flat file human-readable serialization for relational data is the real kludge, but I guess that's just me.
Look into your /etc and tell me which of the files in there are a kludge, and which ones are not plain text relational (or key/value, for that matter).
> newlines in your data
Well, what I do is I split at newlines :). Very practical since it guarantees fields don't contain them. (In the rare cases where you want them, do percent-encoding, hex encoding, C string style, whatever).
> encoding inconsistencies
Parse at an abstract character level of your choice. In scripting languages you get basic Unicode sanity for free. In C I would not want to deal with Unicode. It's too big for my head. UTF-8 goes out of its way so I can ignore it (newlines etc. still work). C strings means no longer having to deal with painful questions like "is c.isspace() only for U+0020 or for also other characters in Unicode classes which I never even heard of (or which don't even exist yet)?". ASCII/C locale text fits in my head. I don't want to be concerned with more abstraction (~ additional semantic baggage) throughout most of a system.
> delimiters in your data
same as above.
> you never know what you're going to want to feed into it in the future.
You better have a rough idea. I don't see why you couldn't commit to non-whitespace user-ids now, for example. Conversely, if you don't want to enforce sensible constraints now, you end up with code which never quite knows what it can assume (and often it can not assume properties that are needed for a sensible implementation).
> To me, the usual way to provide that is with an application and not a data format.
Can I email that application to someone else? Can I grep it as easily as my text files? Can I version-control it? Can I quickly whip up a script, import the application into Excel or maybe sqlite and visualize or extract some relationships? Will that application server still serve my data in 10 years? Will that application still build next year? How do I access it when I don't have a stable connection?
Now, it seems to me that being easier to use and understand is an inherent advantage - I can't see how easier to understand doesn't make bugs easier to understand and so-forth.
Moreover, constructing a recursive descent parser involves understanding and transforming your language, an exercise which can also discover ambiguities and give a "deeper" understanding as well. It's hard for me to see Bison commands + code fragments as the ultimate in illumination concerning one's language's properties.
However, have you tried parser combinators? Parsec (a Haskell library) is really nice if it fits your grammar.
Here is one guy who simulated that in Python, also very nice:
* attoparsec remains the king of speed, generating parsers competitive in speed with C
* trifecta remains the king of error messages, generating gorgeous clang-style errors
* earley is a newcomer but deals with context-free grammars, while other parser combinatory are basically recursive descent parsers
* and good old alex+happy for direct yacc+bison equivalent
* I should probably mention that in certain simple cases you don't even need a parser combinator library to parse things. Just a good old `StateT (Text, r) [] ()` or similar can do wonders.
This has been used, quite famously, in standards conforming XML parsers which have some very ugly backtracking issues dealing with entities and entity references. More commonly, people who decide to add regular expression validation to their APIs are often surprised to discover that an attacker can take up all sorts of server time while the API is trying to validate a carefully crafted degenerate case message. Many regular expression libraries out there are NFA, including the ones built into some popular high-level language runtimes.
An NFA does not use backtracking - at least in a sensible implementation. The problem is that most implementors of RE engines prefer "obvious hands-on" implementation that uses backtracking instead of understating the elegant theory behind NFAs. Here is how to implement an NFA without using backtracking:
> https://swtch.com/~rsc/regexp/regexp1.html
Addendum: And it is also a bad idea to convert am NFA to an DFA for parsing because the number of necessary states can explode exponentially by this transformation.
There is a key insight there: that it is in fact bounded, and you can plan around these bounds. It's not the tight constraint a DFA gives you (where the number of operations is constant, and runtime varies only by hardware details like L1 cache misses), but it's still good enough for most cases.
If by quadratic runtime you mean O(len(regex) * len(input)), then fine. (I think it's a bit strange to call that quadratic, since the size of the regex is constant.) If by quadratic runtime, you mean O(len(input)^2)), then I contest that. My guess is that you probably do indeed mean the former.
And certainly, "linear additional memory usage" is not relative to the input either.
> There is a key insight there: that it is in fact bounded, and you can plan around these bounds. It's not the tight constraint a DFA gives you (where the number of operations is constant, and runtime varies only by hardware details like L1 cache misses), but it's still good enough for most cases.
Sure, but now you have to deal with exponential state blow up. :-)
You can skirt around that with a lazy DFA, and you're now technically back to O(mn) (same as the NFA algorithm in the worst case), but in the common case, you end up pretty close to the performance of a DFA constructed offline.
As "evidence" of my claim, you might peruse these unscientific benchmarks: https://github.com/jneem/regex-benchmarks (The first group uses an offline DFA and the latter two groups are both lazy DFAs. Of course, this is just an anecdote!)
My view on this is pretty biased because my goal is not to just be able to deal with untrusted input, but to also deal with untrusted regexes. It's hard to satisfy the latter case with an offline DFA. :-/
I think he rather means O(len(regex)^2 * len(input)). For the reason: The number of states of an NFA is O(len(regex)) =: m. When parsing with an NFA (standard algorithm) you iterate through all states we are currently in (up to m). On the current input character each state we are in can go into up to m new states for the next state. This is up to m^2 transformations to check.
In a "real" implementation, when computing the next set of states to visit for some position in the input, you explicitly avoid re-visiting states you've already seen for that position in the input. Cox talks about this quite a bit in his articles.
The guarantee of the NFA algorithm as presented by Cox is that each NFA state is visited at most once for each position in the input.
Of course, I don't think there's an actual regular expression that would produce that automaton using Thompson's algorithm.
Let's just look at code already.
Here's the loop over states at input i: https://github.com/rust-lang-nursery/regex/blob/master/src/n...
If we match a character at input i, then we follow epsilon transitions: https://github.com/rust-lang-nursery/regex/blob/master/src/n...
If we visit a state that we've already seen, skip it: https://github.com/rust-lang-nursery/regex/blob/master/src/n...
If that first state visits all states, then `nlist` (which is maintained while following all states at any position in the input) will contain all states. In each subsequent iteration (line 165), even if the state wants to visit all states, it will be immediately stopped at the first check in line 300. No additional states for that state are followed.
In other cases (e.g. /(aa|ab|ac|ad|ae|af|ag|...)+/), you blow up to the maximum number of states immediately, and for a matching string stay in the same number of states the whole time. Therefore, it is technically correct to leave out the len(input) parameter if you are considering arbitrary regular expressions.
> You can skirt around that with a lazy DFA
This adds unwarranted complexity if you're doing ahead-of-time compilation. Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states. If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process.
That's just false for the NFA algorithm. I'm not sure where your confusion lay, unfortunately. There are no pathological cases for the NFA algorithm. Zero. Zip. Nada. It's guaranteed O(mn) time. See Cox's articles. They explain.
It is true of course that certain regexes run slower than others using the NFA algorithm, but this is because of constant factors, not because of any degradation in runtime complexity. When implementing the NFA algorithm, you can allocate all of the space you need upfront and then execute a search guaranteeing no additional allocation.
Offline DFAs do, however, have pathological cases where the number of states required is exponential. For example, `0[01]{n}$`, has an exponential number of states proportional to 2^n. (I think this is isomorphic to your example, assuming `a{11}$`.)
> This adds unwarranted complexity if you're doing ahead-of-time compilation. Perhaps the best approach there is to try to convert the regex to a DFA, but bound the number of states to some multiple of the number of NFA states. If you surpass this number, consult the requirements of the situation and either reject the expression or just use the NFA that was built in the process.
Sounds pretty complex to me. Certainly more complex and fiddly IMO than implementing a lazy DFA. (I've done both.)
I'm apparently completely failing to communicate my point here, because you seem to think I'm contradicting this. I am not. I'll maybe try to work through the example. For the purposes of this example, we have a fixed regular expression of /.+aaaaaaaaaa/.
Processing the string 'a' takes one operation. Processing the string 'aa' takes three operations. Processing the string 'aaa' takes six operations. Processing a string of 'aaaa' takes ten operations. This is a quadratic progression. The DFA, however, has only eleven states.
Yes, there is a bound to the number of operations of 11*length. Yes, this means that big-O says it's linear. No, an attacker can't simply supply a 30-character string and lock up your system the way they might be able to for a backtracking approach. That's beside the point. An attacker still has significant control over system resource usage in a way that he would not with a constant-resource approach. An attacker may still be able to exploit this in a way that would not be an issue with a DFA, e.g. by attempting to exhaust memory by issuing many simultaneous expensive requests when your system is provisioned to handle average requests.
> Offline DFAs do, however, have pathological cases where the number of states required is exponential. For example, `0[01]{n}$`, has an exponential number of states proportional to 2^n.
Yes, there are pathological cases, which is why you don't use that approach with untrusted regexes. I've never disagreed with this.
This isn't even one of them, however. The DFA would have n+3 states: an initial state, a reject-loop state, a state for when we have seen the initial zero, and one state for when we have seen each of n additional zeroes or ones. I'm not sure how one would end up with more states than that: perhaps by not consolidating equivalent states in the NFA first?
Edit: Apparently you're using the convention that one searches for a match anywhere in the input string, which while common isn't what I'm used to. This doesn't change anything: it just makes most transitions that would otherwise go to the reject-loop state go to the initial state instead.
It's possible to get a pathological DFA, but one needs to work harder at it than this.
... that's been exactly my position this entire time.
I guess I just don't understand why you are calling the NFA algorithm quadratic. Calling it quadratic because there exists a particular progression that moves the runtime complexity in a quadratic fashion up to a predetermined linear bound seems really confusing.
Overall, attackers can't make the entire algorithm run in quadratic time in the length of the input or the regex. That's what matters.
With all that said, I agree with your final conclusion of course, that the NFA algorithm is going to be slower than running a pre-built DFA. But I think attributing this to quadratic behavior is just confusing. I personally think of it more as the NFA having to maintain multiple simultaneous states and being forced to follow epsilon transitions over and over again. In contrast, a DFA will only ever be in one state and it will cache all of the epsilon transitions in its states.
> An attacker still has significant control over system resource usage in a way that he would not with a constant-resource approach.
Cox's formulation very explicitly provides an implementation of the NFA algorithm that uses constant resources (with respect to the input).
I mean, this isn't theoretical. You can go look at an implementation of the NFA algorithm by either Cox or myself, and it's pretty clear that some fixed allocation (based on the size of the compiled regex) happens up front, and no further allocation happens during the actual search. You can't make it blow up and take quadratic time.
> This isn't even one of them, however, because the NFA has no loop. The DFA would have n+3 states: an initial state, a reject-loop state, a state for when we have seen the initial zero, and one state for when we have seen each of n additional zeroes or ones.
It's exponential because it requires counting. You don't actually know when you've seen the initial zero, since you can see any number of 0s or 1s before it, and exactly N number of 0s or 1s after it, and then following that, the end of the string. (That final `$` is probably crucial to requiring an exponential number of states.)
It's a pretty standard example: https://en.wikipedia.org/wiki/Regular_expression#Expressive_...
See also: https://github.com/google/re2/blob/master/re2/testing/dfa_te...
This blurb from Wikipedia is also relevant:
> On the other hand, it is known that every deterministic finite automaton accepting the language Lk must have at least 2k states. Luckily, there is a simple mapping from regular expressions to the more general nondeterministic finite automata (NFAs) that does not lead to such a blowup in size; for this reason NFAs are often used as alternative representations of regular languages.
This exactly matches my experience and what Cox says.
> Cox's formulation very explicitly provides an implementation of the NFA algorithm that uses constant resources (with respect to the input).
Not constant, bounded. Theoretical CS doesn't care about the difference, but in practice it matters a lot. People provision hardware for the median case (really more like the 90th percentile), because provisioning for the worst case is really expensive. When something is bounded, but not constant, there exists the possibility of a resource exhaustion attack.
> It's exponential because it requires counting. You don't actually know when you've seen the initial zero, since you can see any number of 0s or 1s before it, and exactly N number of 0s or 1s after it.
I misinterpreted this one, because the convention I'm used to is that the expression is expected to match the entire input. I prefer this convention for its elegance, but it's much less common in practice than the Perl-like convention where you need to specify that you want that behavior.
I also didn't sufficiently reconsider the expression when I realized this: the terminal anchor is quite relevant, but I forgot it was there. In reality you're correct about this with the convention you are using.
If I can do this:
re = regexp(".+aaaaaaaaaaa")
state = malloc(len(re))
match1 = exec(re, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
match2 = exec(re, "aaa")
match3 = exec(re, "aaaaaaaaaaa")
...
Do you consider that constant or bounded? It looks like it's constant to me.
If you're talking about CPU resources, then the absolute worst case in the NFA algorithm is requiring `len(re)` operations per position in the input. I guess this is what you're referring to as bounded? If so, then it is a linear bound. :-) An attacker can't make matching take more than linear time.
I feel like this entire conversation has been one roundabout exploration of "DFAs are faster than NFAs." :-/
> I also didn't sufficiently reconsider the expression when I realized this: the terminal anchor is quite relevant, but I forgot it was there. In reality you're correct about this with the convention you are using.
You had me doubting myself there for a second, so kudos. :-)
edit: I guess I should have just looked that up sooner. Sorry for any hassle or aggravations.
In a "real" implementation, you also need space to store sub-capture locations. You get to reuse this space on each execution of the regex, so it's a really nice win.
There are also certain crazy people in this world who have encoded the NFA algorithm into a code generation tool, which enables it to run completely malloc-free and entirely on the stack. :-)
Of course, backreferences and other stuff take you out of the realm of regular languages. Avoid these.
You can skirt this problem using a lazy DFA with a bounded cache. (i.e., See the third article in Cox's series.)
If you're going to implement this important feature in a sane way then at SOME point you're going to need to backtrack.
And there are plenty of "real world" regex engines in wide use that don't support backreferences.
Most RE engines that are described as being an NFA (examples include Perl's, PCRE and Java's) are implemented with backtracking exactly because you can easily add in a little state and suddenly you support backreferences. Of course the language isn't really now a proper regular expression, but everyone knows what you mean when you talk about them.
And yes, I'm well aware of how many real-world regex engines there are without backreferences. However the ones with the most widespread use, do.
Yes, and it's a huge disservice to continue doing so. It doesn't make any sense to describe Perl's (or Java's, or Python's or PCRE) regex implementation as an NFA.
> but everyone knows what you mean when you talk about them
I disagree. The confusion in this space is extremely high.
The problem starts with "regular expression". Regular expressions in Java, JavaScript, Python, Perl, Ruby, or many other languages or environments, aren't regular. They support backreferences. In many of those languages, it would be a backwards incompatible change to change either the name of the engine, or its feature set. There are more users of these languages who "know" how to use regular expressions than know the actual definition. Good luck convincing Java, JavaScript and Python to make backwards incompatible changes so we can restore language terminology!
Moving on, every description of regular expressions starts with the DFA and NFA terminology. All of these regular expression engines that I named, when presented with an actual regular expression, solve it like an NFA. Admittedly with a backtracking algorithm. Even though their internal states go beyond NFA, it isn't actually wrong to say that "This RE engine uses an NFA algorithm on regular expressions."
Given that, it is hopeless either to get people to use "regular expression" in its original meaning, or to get people to stop calling their so-called (but not really) RE engines, NFA implementations.
With that said, I absolutely take issue with using the term NFA to describe anything that is NP-complete. It's just plain nonsense. The term "NFA" isn't nearly as widely used as "regular expression," and it is a very technical term with very specific technical implications.
> it isn't actually wrong to say that "This RE engine uses an NFA algorithm on regular expressions."
This is exactly the problem. It is wrong to say that Perl uses an NFA algorithm. It literally cannot be true because Perl implements features that are NP-complete.
This is exactly what happens when people get sloppy with their teminology. They start bending the meaning of words to say something that doesn't make any sense. As a result, those of us who aren't as informed end up getting extremely confused.
> or to get people to stop calling their so-called (but not really) RE engines, NFA implementations.
In a discussion like the one in this thread, where the distinction ACTUALLY MATTERS, it is absolutely worth pointing out.
> Good luck convincing Java, JavaScript and Python to make backwards incompatible changes so we can restore language terminology!
This is such a bad argument and such a huge straw man. Do you think I'm on some crusade to fix terminology? No. That's stupid and a waste of time. The only reason I brought this up is because your initial comment in this thread suggested (to me) that you were confused about the terminology being used! Why? Because wolfgke used the term NFA correctly: "An NFA does not use backtracking." But you chimed in with stuff about backreferences and "real" regex engines. What gives? I don't know, but it seemed like a clarification was in order to me.
However the most widely used RE engines in the wild use backtracking because that is the easiest way to handle the full feature set that is asked of them. That's not to say that they couldn't be implemented in a way that was able to handle strict regular expressions without backtracking, while backtracking only when they need to. (Perl makes a modest attempt in that direction, but doesn't do it completely.)
And then when programmers ask how the engine works, they start with the simple version for simple features. The naive explanation is of an actual NFA. And then someone goes off and implements one for a project, and they just follow that. Now you have an engine which is an honest NFA, and uses backtracking. It doesn't need to because it doesn't support extra features, but it is simple, it works, and if you ever needed to extend it, it is obvious how you'd go about it.
So there are two reasons other than laziness to implement an RE engine with backtracking. The first is that your RE engine supports (or might in the future) features that require it. The second is that it is easier to find and follow explanations of backtracking.
This is exactly the problem. It is wrong to say that Perl uses an NFA algorithm. It literally cannot be true because Perl implements features that are NP-complete.
Not true!
If you hand Perl's RE engine a regular expression that is actually regular, then Perl will construct a set of states that are a recognizable NFA, and then will attempt to match the NFA to the string using the obvious backtracking algorithm. Admittedly the states are decorated with fields which COULD specify non-NFA stuff. The code it passes through will have checks for whether to trigger features that an NFA can't do. But what it actually will do is construct a recognizable NFA, and attempt to match it to the string.
Now throw a non-regular "regular expression" at the same thing and you'll construct a data structure that clearly isn't a proper NFA. What the heck do you call it? It is some type of extended state machine, but it is easiest to think of it as "NFA with some extra stuff". And that is exactly how the people who do work on that code think of it. With no alternate terminology and thinking of it as an NFA, is there any wonder that they describe it as an NFA?
(As well, that is how it was described in a number of popular and widely read books. For example pick up _Mastering Regular Expressions_.)
I completely understand why it looks like an NFA.
> What the heck do you call it?
Anything but an NFA? My personal preference is unbounded backtracking (still not quite right), or just "Perl regexes."
> (As well, that is how it was described in a number of popular and widely read books. For example pick up _Mastering Regular Expressions_.)
I read that book when I was a young pup and remained hopelessly uninformed about the entire situation until my first complexity theory class during my undergraduate study almost ten years ago.
That book is fantastic if you care about optimizing Perl regexes. It otherwise does a great disservice to theory and has likely been the cause of uncountable confusion. When pointed out the inaccuracy, Friedl essentially had the same response as you. It's tragic, frankly.
PCRE's documentation even cites Friedl's book when describing their implementation by calling it the "NFA algorithm." PCRE also has a supposed "DFA," but its description makes it sound more like the actual NFA algorithm (since it maintains multiple states simultaneously).
As for _Mastering Regular Expressions_, you've demonstrated both what it says and that it is popular. And further that it affected the terminology of a widely used project which has been embedded in many other projects. (Like PHP.)
And yes, I agree that it did a lot of people a disservice. But the damage is now long-done. See for example https://msdn.microsoft.com/en-us/library/e347654k%28v=vs.110... for yet another non-NFA that is described as one somewhere that programmers are likely to believe it.
All this means is that Perl sometimes evaluates inputs using an NFA algorithm. To describe its matching engine generally as an NFA is extremely misleading.
> See for example https://msdn.microsoft.com/en-us/library/e347654k%28v=vs.110.... for yet another non-NFA that is described as one somewhere that programmers are likely to believe it.
Yes. It's sad.
I frankly can't tell you how much I see this confusion. It happens so much. I point it out when I see it in the hopes that others learn. I don't really buy the argument that we should stop educating others just because the "damage is done."
There's certainly a fine line between being an annoying pedant about this and genuinely trying to clarify it for someone who is confused. I thought I was doing the latter in this case initially. Of course, I am hyper sensitive to this topic because I maintain a regex engine! Can you guess which kind? :P
I learned a lot from this. I did take compiler theory in college, but that was pretty academic (mostly Dragon Book), and more theory than practice. This is a good explanation of why lex/yacc is not enough.
As someone who had a technical but "not real CS" curriculum, I enjoyed Parr's "Language Implementation Patterns" book [0] because it illustrates how certain grammar-forms become recognizable code-patterns and control-flow.
Granted, it's definitely got a bent towards Parr's ANTLR project and the Java language, but I still found it made things "click" a lot better than my daunting lack of progress an old "Dragon Book" [1] which IIRC tended to float along with more mathy-notations and theory than concrete examples.
[0]: http://www.amazon.com/Language-Implementation-Patterns-Domai...
[1]: https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...
Oddly you would think that sacrificing non-determinism would really hurt the power of PEGs to express languages but there are languages that are not context free (eg, `a^nb^nc^n`) that can be written as a PEG.
And if you have a sufficiently smart compiler, it'll warn you about most of the practically important cases anyway. I wrote PEG parsers for dozens of different types of languages, and never ran into problems with an explicit choice order. This anti-PEG FUD should stop at once.
Favorite new trivia bit:
"C++ has an even more extreme version of this problem since type/variable disambiguation could require arbitrary amounts of template instantiation, and therefore just parsing C++ is technically undecidable (!!)"
I'm not sure if any exist, although some people have tried to write grammars for existing markup languages.
http://roopc.net/posts/2014/markdown-cfg/
https://github.com/asciidoctor/asciidoc-grammar-prototype
https://stackoverflow.com/questions/6178546/antlr-grammar-fo...
I have a few basic reasons why I now think parser generators are a mistake for my purpose: 1) It is hard to learn all the details of a particular parser generator that you need for a complex parsing project. 2) The mix of grammar and semantic actions one has to come up with is ugly and complex. 3) The output is both ugly and hard to debug.
The most complicated part of a compiler is not recognizing good input, put doing something with it. A hand-written recursive descent parser can be a thing of beauty and simplicity that increases the joy of working on the meat of the compiler, that is semantics!
http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf
What is more, these combinators can express context-sensitive grammars: https://www.cs.york.ac.uk/plasma/publications/pdf/partialpar... (page 5).
And, by tweaking combinators, you can arrive to the wonders of stream processing parsing without (mostly) space leaks: http://www.cse.chalmers.se/edu/year/2015/course/afp/Papers/p...
It is easy to add syntax error position reporting, also it is easy to add syntax error corrections. All this can be done in under a day.
For me it offers good things from both worlds - declarative specification of parser generators and easy modifications from "parse damn thing by hand".
I actually encountered one case where that approach shines incommensurably: supporting old languages like VHDL. VHDL fits every parser formalism almost without seams but still has one place where you cannot do things either efficiently or elegantly: character literals and attributes. 'a' is a character literal, a'a is an invocation of attribute a on the object a. The ambiguity is in the lexing level, needing feedback from parsing level. Usual parsing tools cannot do that good enough, with parsing combinators it is trivial.
Here's the PEG paper: http://www.brynosaurus.com/pub/lang/peg.pdf
In practice PEGs do not have an ambiguity problem, period. Stop this FUD!
Code is here, in fact:
https://github.com/Ravenbrook/mlworks/blob/master/src/parser...
Generating Good Syntax Errors http://research.swtch.com/yyerror
[1] https://buguroo.com/why-parser-generator-tools-are-mostly-us... .
Note that Go is also moving away from yacc:
https://www.reddit.com/r/golang/comments/46bd5h/ama_we_are_t...
I used Antlr3 to create a NLP parser for entering a calendar event. For iOS, the C runtime's parse tree source was many megabytes and difficult to debug directly. For Android, the Java runtime parse tree ran out of memory and had to be broken into smaller pieces. Haven't tried Antlr4.
Current workaround is to parse a document directly into a token tree. Instead of separate lever + parser, merged a tweaked BNF with regex. Memory stays rather small and can download a revised grammar without recompiling a new binary.
As for tool, the Antlr3 C runtime was very fiddly. On the forums, I saw one developer give up on porting their working Antlr2 C++ runtime to Antler's C runtime. This may have been due to C lacking exception handing, so had to implement backtracking another way. (Still, kudos to the volunteer who implemented the C runtime; in our case, it did make it into production.)
For really simple NLP parsing, one hack is combine an Island parser with an LL parser. This is essentially what Siri used several years ago (have no idea what it uses now).
Parser generators need to get much better before that will change.
https://groups.google.com/forum/#!searchin/golang-checkins/r...
From what I recall reading about the change, it was believed it would allow them more flexibility in the frontend, and they greatly preferred to write the parser in Go instead of yacc.
Also, at this point, they felt this would also make it easier for others to contribute improvements to the project.
Any time you take native objects/data and persist them, or marshal them, you need a parser -- or a parser library. That might mean reading some CSV, parsing some XML, reading some YAML, JSON or what-not.
Then there's configuration that does more than set some variables, like for Nginx, Apache (web server), etc.
One might want to have a short-hand for defining templates -- either for general meta-programming, or just to generate a layout-language (eg: html, css). If you're doing markdown (or markdown-like) processing, you might want to have some assurances that that's all that code can do -- generate html. Or you might want do meta-programming on some higher level, like generating interfaces for some java-beans based on a CSV structure. For more on meta-programming in Java, I recommend (the now slightly dated: http://www.amazon.com/Program-Generators-Java-Craig-Cleavela... ). It's a shame he didn't name it as he claims he considered in the foreword: "Program Generators for Fun and Profit!".
And finally there's "real" programming languages - full blown DSLs of some kind. Perhaps in an effort to represent some kind of business logic (eg: authorization based on group membership, roles and time of day) in a language that is "safe" -- has no side-effects.
[1] http://fishbowl.pastiche.org/2015/11/09/java_serialization_b...
http://blog.codeclimate.com/blog/2013/01/10/rails-remote-cod...
https://github.com/YorickPeterse/oga/blob/master/lib/oga/css...
https://github.com/YorickPeterse/oga/blob/master/lib/oga/xml...
https://github.com/YorickPeterse/oga/blob/master/lib/oga/xpa...