4 ms·
The question is raised at the end about the undecidability of ambiguity of CFLs, and whether, under certain restrictions, the problem becomes decidable. As the
by cvoss 2y ago
The question is raised at the end about the undecidability of ambiguity of CFLs, and whether, under certain restrictions, the problem becomes decidable.
As the author points out, Regular Language ambiguity (among many other properties) is decidable.
One of my favorite language facts that I always keep in my back pocket is the existence of Visibly Push Down Languages and the related Finite Tree Automata, which reside in between Regular Languages / FA and CFLs / PDA in the inclusion hierarchy. Whereas Regular Languages give you a limited, tail-recursive or looping structure, VPLs / FTA give you the kind of full recursion you'd expect as a programmer without compromising decidability of all the essential questions (intersection, emptiness, negation, ...).
VPLs are very expressive, and many languages which you hitherto thought were general CFLs often turn out to be VPLs!
The key distinguishing feature of VPLs as a restriction of CFLs is that you can always tell where the recursive term boundaries are, with bounded lookahead, by detecting sentinel "call" and "return" tokens, such as open/close parentheses or other hints. This makes all kinds of questions decidable because parsing algorithms don't have to indefinitely defer decisions about where to place term boundaries.
I'm not sure whether VPLs can assist the author in this particular application because 1) I haven't determined whether an expression grammar with operator precedence is a VPL (though I suspect it is... when reading left to right you are never held in suspense about the implicit grouping for very long, and the explicit grouping is, well, explicit.) and 2) I don't know for a fact that ambiguity is one of the advertised decidable questions for VPLs (but again, I suspect it is, as all these properties seem to stand and fall together).
Edit: I was a bit sloppy when referring to ambiguity. Of course, it's a property of a grammar, that is, one particular representation of a language as an explicit machine of sorts, not a property of the language itself.
- xelxebar 2y agoWhoa. I've wondered about that exact question for a while, whether a proper class exists between RL and CFL. Relevant Wikipedia link, for posterity: https://en.wikipedia.org/wiki/Nested_word https://en.wikipedia.org/wiki/Nested_word Thanks for sharing!
- nsajko 2y agoAnother "proper class" are the operator precedence languages, AKA Floyd's languages (R. W. Floyd). They include the "visibly pushdown languages", which are really just a rediscovery of the input-driven languages. Floyd's languages are the languages parsed using the shunting yard algorithm.
- ysofunny 2y agoif I could be a researcher, this would be one of my main topics. I have personal reasons to be interested in languages with alphabets that have "very special symbols" such as the parenthesis. in general, i'm curious about how as you progress up the type language hierarchy it becomes necessary to keep adding specialized symbols to keep up. most interestingly, i wonder about how one pair of symbols (open and close) add a lot of expressive power but I suspect adding more different types of pairs of symbols won't significantly augment the expressiveness but I don't know for sure. this is also reminiscent of dyck languages and their corresponding automata, which can recognize and match open and closing parenthesis. I did not know visibly push down was sufficient to recognize parenthesis, I thought a stack was sufficient. but given a stack is more powerful than the unidirectional "stack" of a VPLs it all makes sense
- nsajko 2y ago"Visibly pushdown automata" are just a rediscovery of input-driven pushdown automata. It's sad that the authors of the VPL papers never acknowledged this AFAIK, even while writing more papers on the same topic.
- cvoss 2y agoIt's a reflection on the state of the field, I think, that there is such a volume of lesser known good work hiding among an even larger volume of noise and fluff that neither the authors nor the reviewers caught such an oversight. (And reviewers are usually pretty aggressive about suggesting related work.)