3 ms·
His problem isn't primarily the choice of formalism, but that his grammar is wildly overcomplicated and makes it really hard to see what language it specifies i
by vidarh 2y ago
His problem isn't primarily the choice of formalism, but that his grammar is wildly overcomplicated and makes it really hard to see what language it specifies irrespective of formalism.
This is a common problem.
In this case the amount of recursion makes it hard to even guess at what it is trying to express.
If my grammar looked like that, I'd throw it away and start over, because the problem to me appears to be not quite having a clear idea of what the grammar is expressing.
EDIT: Trying to clean up his grammar into something readable
t0 = t1 | a
t1 = t3 ("==>" t1)?
t3 = (id | d)+ c? | b
a = "!!" id c "." t0
b = "%" id c "." t3
c = "::" t0
d = "(" t0 ")"
t999 in the original was left-recursive, but in this case that's a matter that can be left to the parse tree construction if he insists on keeping it that way. For your own sanity don't mix left and right-recursion in a parser, and decide how you structure the parse-tree in terms of left/right binding separately, and only express that in the grammar if your tool doesn't let you express it when building the tree, or if it actually changes the language recognised.
One thing to note, is that my first instinct when writing parsers is to look for opportunities to factor out rules that start with a terminal, because it's usually a good way of avoiding or reducing the need for lookahead. Hence the extra rules, that to me at least makes it a lot clearer. The part of the grammar to look for places where your formalism causes ambiguities is now much smaller.
This grammar still gives me hives, but without knowing his constraints and intent, it's tricky to see if it can be cleaned up further.
- chipdart 2y ago> If my grammar looked like that, I'd throw it away and start over, because the problem to me appears to be not quite having a clear idea of what the grammar is expressing. That's fine if you are working in a purely academic domain, or you're just having fun writing something on your free time. In production settings, you need to keep extending whatever language you have. The alternative is having to start to maintain two separate parsers and a migration tool, and be stuck with that for years. The point is that being able to throw away code is a luxury that virtually no one is able to afford.
- bruce343434 2y agoWhat do you mean? Stuff gets refactored all the time.
- vidarh 2y agoNo, I'm not talking about an academic setting. This is not about the language but about his expression of it in this specific instance of the grammar. As the article makes clear, he didn't understand the language, and my claim is that is to a large extent down to how it is expressed. Not throwing away this specific grammar instance is something you can't afford.
- kragen 2y agosometimes having an lalr parser generator tell you where the ambiguities are in your grammar can be a useful step to understanding the language you're trying to describe. you're probably right that once you do understand it, you should throw away the grammar given as an example and write a new one ;)
- vidarh 2y agoSure, especially for anyone not used to writing parsers using a parser generator is a good way of validating assertions about it. But for that parser, just starting by cleaning it up would be a big improvement irrespective of formalism. Even if you get an unambiguous parser, if you can't read the grammar you'll end up with nasty surprises anyway...
- kragen 2y agoagreed!
- HelloNurse 2y ago> In production settings, you need to keep extending whatever language you have. Then the hard work of leaving behind simplistic, ambiguous, imprecise, inefficient grammar specifications has already been done (mostly) and you are ready to add small new features without serious rewrites.