-
-
Notifications
You must be signed in to change notification settings - Fork 52
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
lx doesn't always return the longest match #111
Comments
After trying out #116 on all the existing
|
That's correct, and it isn't something I'd considered when designing the generated code. I think it should be possible, but I don't like the possibility for the unbounded case. Hm. I'm not sure what I want to do here. I do agree that it'd be a nice feature (read: less surprising behaviour). I'm calling this a feature request rather than a bug, because the current code generation didn't attempt to cater for this. |
What do you think of having lx identify this situation and erroring about it? Much like it does for ambiguous patterns (where they share a common intersection). In this case I think we'd strengthen that test to error if a pattern one-or-more-times shares an intersection with another pattern. |
Oh, is "one-or-more-times shares" an equivalent way of describing this? I could believe that. Interesting! I think that always returning an error would be unfortunate. For ambiguous patterns, it's always possible to rewrite the input to lx to eliminate the ambiguity, right? I think that's never possible for longest-match problems while still matching the same tokens, so always reporting an error limits what languages lx can work with. (I'm pretty sure the one I care about right now, for the C11 preprocessor, can't be rewritten to avoid this.) I'd rather see three code-gen options which resemble the token-buffer options.
That said... so long as the error is only reported by the C codegen option, and GraphViz/JSON output succeeds even for languages which need more lookahead, I guess I don't personally care? |
I'd be very uncomfortable if .lx source were used to generate lexers which behaved differently, for different implementations. I think I agree that the dynamic resizing buffer does make sense. Dynamic allocation is something I wanted to avoid for FSM, but lx does already do that, because tokens themselves are variable lengths. |
I'm not proposing that any lexer specification behave differently on different implementations. I'm only observing that some implementations are less capable than others, in exchange for having simpler and/or more efficient implementations. If two lx backends are both capable of implementing a particular .lx specification, then I agree that they should both match the same language, but I think it's perfectly reasonable to have implementations that can't handle some .lx specifications, so long as a user who tries to use such a specification with such a backend gets an appropriate error instead of getting a broken lexer. Anyway, I think this is the same situation as for token buffers, because lx doesn't support token buffers at all by default, and allows the user to request either a fixed-size or a dynamically-growing buffer if they need that extra capability. |
I think I want to keep the tokens which did match, when moving past them (in this case We still need to buffer the spelling to use for the next call, but this would tell us which was the longest match that we moved past, before finding a failure. |
Given this input to
lx
,running the generated
-l dump
program against the string..
(no trailing newline or other characters) outputs:Running it against
..\n
outputs:In both cases I expected to see two
<DOT '.'>
tokens, followed by either<EOF>
or an error that the newline character is lexically uncategorised, respectively.I'm pretty sure language specifications like this require more than one character of lookahead/backtracking. An error transition needs to walk back to and return the most recent accepting state, which may be more than one transition ago.
I think a straightforward graph analysis can tell you the upper bound on the number of characters you might need to buffer. For each accepting state in the DFA, find all states that are reachable from it without hitting another accepting state. If the resulting subgraph does not contain cycles, then its maximum path length is one less than the necessary amount of lookahead. If it does contain cycles then it can require unbounded lookahead.
If I have this right, then
lx_ungetc
isn't sufficient in general, but at least you can detect at compile time when it isn't enough. You could even report example strings which take an error transition more than one step after the last accepting state.The text was updated successfully, but these errors were encountered: