1
$\begingroup$

I'm planning to implement a lexical analyzer by either simulating NFA or running DFA using the input text. The trouble is, the input may arrive in small chunks and the memory may not be enough to hold one very long token in the memory.

Let's assume I have three tokens, "ab", "abcd" and "abce". The NFA I obtained is this: enter image description here

And the DFA I obtained is this: enter image description here

Now if the input is "abcf", the correct action would be to read the token "ab" according to the maximal munch rule and then produce a lexer error token. However, both the DFA and the NFA have state transitions even after "ab" has been read. Thus, the maximal munch rule encourages to keep on reading after "ab" and read the "c" as well.

How do maximal munch lexers solve this issue? Do they store the entire token in memory and do backtracking from "abc" to "ab"?

One possibility would be to run the DFA with a "generation index", potentially multiple generations and multiple branches within generation at a time. So, the DFA would go from:

{0(gen=0,read=0..0)},

read "a",

{1(gen=0,read=0..1)},

read "b",

{2+(gen=0,read=0..2,frozen), 2+(gen=0,read=0..2), 0(gen=1,read=2..2)},

read "c",

{2+(gen=0,read=0..2,frozen), 3(gen=0,read=0..3)},

read "f",

{2+(gen=0,read=0..2,frozen)}.

Then the lexer would report state 2+, and since there is no option to continue, would report an error state. Not sure how well this idea would work...

For "abcd", it would work like this:

{0(gen=0,read=0..0)},

read "a",

{1(gen=0,read=0..1)},

read "b",

{2+(gen=0,read=0..2,frozen), 2+(gen=0,read=0..2), 0(gen=1,read=2..2)},

read "c",

{2+(gen=0,read=0..2,frozen), 3(gen=0,read=0..3)},

read "d",

{2+(gen=0,read=0..2,frozen), 4+(gen=0,read=0..4,frozen), 4+(gen=0,read=0..4), 0(gen=1,read=4..4)}.

Now of these, it's possible to drop the first (there is a longer match) and the third (there are no state transitions out), leaving:

{4+(gen=0,read=0..4,frozen), 0(gen=1,read=4..4)}.

Then the lexer would indicate "match: 4+" and continue reading input from state 0 using generation index 1.

Is this idea of mine, running DFAs nondeterministically, how maximal munch lexical analyzers work?

$\endgroup$
  • $\begingroup$ @D.W.: That's not really true. Here's a simple, occurs-in-the-wild lexical analysis issue: a language in which . and ... are both tokens. If we're just about to start tokenising and the next input character is ., then we need to consider both possibilities. If the second character is also ., we still need to consider both possibilities. If the third character is not ., we need to report a . token and backup the input so that the second dot will be the first character of the next token. If the third character is ., of course, we can just report a ... token. $\endgroup$ – rici Sep 15 '18 at 23:22
  • $\begingroup$ @D.W.: Maximal munch can affect the construction of the DFA, but it mostly affects how you use the DFA. You need to run the DFA until no more transitions are possible and then back up to the last accepting state. (Of course, you only need that complexity if your lexical grammar actually might backup. If the DFA has no transitions from an accepting state to a non-accepting state, then backup is never possible. Hence my specific example, which exhibits this problem.) What actually modifies the DFA is typically not maximal munch, but the "first alternative wins" tie-breaking rule. $\endgroup$ – rici Sep 15 '18 at 23:44
2
$\begingroup$

There are two ways to handle this issue:

  1. The most common implementation (the one used in lex, flex and other similar scanner generators) is to always recall the last accept position and state (or accept code). When no more transitions are possible, the input is backed up to the last accept position and the last accept state is reported as the accepted token.

    If you're trying to do streaming input, you will need a fallback buffer to handle this case.

  2. Alternatively, if the scan reaches an accepting state but another transition is available, we can start performing two scans in parallel: one on the assumption that the transition will be taken, and the other on the assumption that it will not. The second thread may need to fork again, although there is a maximum number of forks, as with generalised LR parsing. In this model, we need to keep a buffer of possible "future" tokens which will be processed if the optimistic thread fails.

I don't know of a practical implementation of the second strategy in a general purpose scanner generator, although there are some papers about how you might do it. Apparently it can be done in time and space linear to the size of the input, which is (in theory) better than the quadratic time consumption of backtracking.

However, it is pretty rare that you find a token grammar which needs to allow unrestricted backtracking. The most common cause of unrestricted backtracking is failing to take into account the fact that things like quoted strings might not be correctly terminated in an incorrect program, so you end up with just the rule:

["]([^"]|\\.)*["]   { Accept a string }

instead of the pair of rules

["]([^"]|\\.)*["]   { Accept a string. }
["]([^"]|\\.)*      { Reject an unterminated string. }

(Maximal munch will guarantee that the second rule will only be used if the first rule cannot match.)

So while the second strategy may have some theoretical appeal, it seems to me that it's of little practical use. Flex even has some options which will help you to identify rules which could backup on failure, and this can help you craft your lexical grammar to avoid the problem. It's not always easy to eliminate 100% of backing up (although it often is, and if you manage to do so, flex will reward you by generating a faster lexer), but it's pretty rare to find a lexical grammar which requires more than a few characters of back-up, and the cost of a small fallback buffer is really not worth worrying about, in comparison with the complexity of the alternative (which, of course, also needs extra memory.)

I have seen intermediate strategies for particular grammars. If you know your grammar well enough, you could hand-build the speculative tokenisation in order to avoid backing up. I've seen that, years ago, in SGML lexers which eliminate the rescan of > following a tagname by including a redundant rule which recognised a tag immediately followed by a > and handled both tokens at once. That must have saved a few cycles, but it's hard to believe that it really made a huge difference, and the difference would likely be even less significant today. Still, if you are the type who obsesses about saving every possible cycle, you could do it.

$\endgroup$
  • $\begingroup$ I now agree, indeed the most common backtracking is things like "0" (token), "0x" (not a token) and "0x0" (a token). Now I probably need an algorithm for determining maximum backtrack amount to determine the buffer size but it shouldn't be hard... Do you have some references for the papers about the second approach? I might write a paper about what I'm doing, and references about the approach that could have been selected but wasn't selected would be great. $\endgroup$ – juhist Sep 16 '18 at 6:43
  • $\begingroup$ The maximum backtrack is the maximum non-accepting chain between accepting links; unlimited if there's a non-accepting loop. You can compute it by first finding the strongly connected components (of the non-accepting states); then you do the non-cyclic longest path (which is not NP) between accepting states. If you find a path with a SCC, you have unlimited backup. It's pretty straightforward. $\endgroup$ – rici Sep 16 '18 at 7:01
  • $\begingroup$ Another numeric backtrack is eg. 2.6E+. C/C++ avoid these by allowing such things to be ppnumbers. $\endgroup$ – rici Sep 16 '18 at 7:05
  • $\begingroup$ A recent paper is here; @sepp2k found it during a discussion on SO (here.) I've probably written half a dozen SO answers about maximal munch. Maybe more. $\endgroup$ – rici Sep 16 '18 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.