-
Notifications
You must be signed in to change notification settings - Fork 18
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
Use the fancy_regex crate instead of regex #191
Comments
Hi @ethindp, |
@jsinger67 Thank you for that, I didn't know that regex-automata allowed that already. I completely understand the performance angle. I'm looking forward to giving Parol a try to see if it can handle (or help me help it handle) the particular grammar I have (which is quite complicated). |
Parol is definitely worth a try 😄 |
Thanks! (Parol is attempting to comulcate k for my grammar.... It's taking a while to do that so I honestly am wondering if K might be infinite... I hope not but if so, I might need to left-factor.) The grammar I'm working with is ambiguous (I'm working on writing an Ada compiler) but getting it to parse would be great! |
Try to start with small pieces. |
@jsinger67 You aren't the only one to tell me to do this, and I'm trying to do that. But the grammar (mainly the name rule) is ambiguous and left-recursive, and almost everything (minus a few constructs) depends on that rule. I wonder if left-factoring can break that cycle. |
One good technique is to comment out some less important alternatives of a certain non-terminal near the start symbol of your grammar. This will temporarily cut off a great portion of your grammar. I can offer you to have a look at your grammar. |
Any help would be appreciated. The majority of left-recursive rules are indirectly left-recursive; the rule they all have in common is |
I will have a look at this soon. |
@jsinger67 I know, I'm planning on eliminating those later once I get this to work. The name rule is a tangled mess. |
At least, the ones I can (e.g. reference_object_name). Might also be able to take care of prefix too. |
@ethindp, there are about twenty recursive non-terminals in this grammar. |
I removed all left-recursions successfully. |
Thanks! I'll look at the changes -- I'll definitely look at modifying the grammar further to get it to stop complaining. (It'd be nice if LL(k) supported direct/indirect left recursion, but from what I understand this inherently isn't possible.) |
You're right. LL parsers can't handle left recursions. |
If it wouldn't take a significant amount of time, could you do it during code generation? (Also, another alternative that could be used to disambiguate things, if necessary, would be something like an interception function that you define that's called on rules you know are ambiguous, which would allow you to influence which path is taken based on arbitrary lookahead; Coco/R does this, and it's quite neat.) |
@ethindp The computation of your grammar for a limit of k <= 3 finished after about ten minutes on my machine with no solution found. Maybe some very powerful computer could calculate a solution with k in the range of 5..10. To make a long story short. I think, parol is not able to handle such grammars effectively at this stage of its development. |
@jsinger67 It's alright, I completely understand. I've been struggling to find a good way of implementing this grammar for a while now. I've thought about using parser combinators, but the way Nom and such work don't exactly give me confidence in my ability to translate the grammar into a form that Nom/combine/pom would like. |
Would it be possible to use the fancy_regex crate over regex? It adds features like lookbehind/lookahead, which a grammar I'm writing needs (I need to ensure an identifier is (not) a keyword). It also supports character classes.
The text was updated successfully, but these errors were encountered: