Skip to content
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

Construct NFAs for regex matching inside text #464

Open
Adda0 opened this issue Nov 18, 2024 · 0 comments
Open

Construct NFAs for regex matching inside text #464

Adda0 opened this issue Nov 18, 2024 · 0 comments
Labels
For:library The issue is related to library (c++ implementation) Module:nfa The issue is related to Nondeterministic Finite Automata Type:discussion A discussion of some particular topic in wider audience

Comments

@Adda0
Copy link
Collaborator

Adda0 commented Nov 18, 2024

As of #459, we skip ^, $, \b etc. in regexes, as they are irrelevant for our precise regex matching NFAs (accept only the specified regex and nothing more).

However, regex a{2}b can have two interpretations: it should match aab and only aab, but it can also match aab inside fffaabfff. The first approach is just an automaton matching a{2}b precisely, the other is .*a{2}b.*, which is what normal regex matchers do. We should have a flag (by default, set to the first approach), where the user can define which matching approach they want (what kind of NFA they get from the regex). Then, the ^ and $ will play a role. In the first approach, they are irrelevant, in the second, they must be accounted for.

Originally posted by @Adda0 in #459 (comment)

The EndOfLine vs EndOfText could be related with whether multi-line mode is enabled or not, by default I think it is disabled.

Originally poster by @jurajsic in #459 (comment).

@Adda0 Adda0 added For:library The issue is related to library (c++ implementation) Module:nfa The issue is related to Nondeterministic Finite Automata Type:discussion A discussion of some particular topic in wider audience labels Nov 18, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
For:library The issue is related to library (c++ implementation) Module:nfa The issue is related to Nondeterministic Finite Automata Type:discussion A discussion of some particular topic in wider audience
Projects
None yet
Development

No branches or pull requests

1 participant