Deterministic context-free languages (DCFL) and visibly pushdown languages (VPL) are both sets of formal languages between context-free languages (CFL) and regular languages (REG). Is there a readable notation that can be expressed in plain ASCII like Backus-Naur-Form for CFL and regular expressions for REG?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ It might be useful to clarify the meaning of “good” in the title of the question. What is wrong with using BNF to describe a DCFL? $\endgroup$– Tsuyoshi ItoSep 1, 2010 at 13:45
-
1$\begingroup$ By good I mean that it should be easy to read and write for human beings, so it should be based on ASCII. BNF is great - regular expressions are a compact subset of BNF. But which subset of BNF defines DCFL and which defines VPL? $\endgroup$– JakobSep 2, 2010 at 12:27
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
Regarding DCFLs, I do not see a better notation than the transition function of the deterministic pushdown automaton, i.e. writing explicitly rules of form $q,z,a\to q',\gamma$ with $q,q'$ states in $Q$, $z$ a stack symbol, $\gamma$ a sequence of stack symbols, and $a$ an input symbol or the empty string. The notation itself does not enforce determinism, but it is easily checked. Using a context-free grammar kind of notation (as BNF), you are going to run into problems since DCFLs are a proper subclass of CFLs, and as noted by DaniCL, you cannot decide in general given a CFG whether its language is deterministic.
Regarding VPLs, a bracketed/parenthesis-style for CFGs would be good enough, with rules of form $A\to a\alpha b$ where $A$ is a nonterminal, $a$ a call symbol, $b$ a return symbol, and $\alpha$ a sequence of regular expression over mixed internal symbols and nonterminals. Since any VPL is also a (D)CFL you could also reuse the above notation for pushdown automata and check that the stack operations match the calls and returns, or write down the transition relation of a nested word automaton (which would be less redundant).
Edit: come to think of it, a notation for XML schemas, like the compact syntax of RelaxNG---which is an ASCII notation---, could easily be used for VPLs. You'd just need to enforce some naming conventions for tags, e.g. an opening tag "<ab>" for a call symbol $a$ matching a closing tag "</ab>" for a return symbol $b$.
-
$\begingroup$ Thanks! Regarding DCFLs I think this is a right direction. A concrete syntax would have some handy abbreviations for subsets that are parsed by regular expressions. Regarding VPLs I am not sure yet, because a VLP is allowed to have dangling call and return symbols in contrast to tree models like XML. You can better compare it with an arbitrary sub-sequence of SAX-events from an arbitrary XML tree. I doubt that RelaxNG can describe this. $\endgroup$– JakobOct 15, 2010 at 11:46
-
$\begingroup$ The remark Using ... is deterministic. is beside the point - it says nothing about whether there is a subclass of the CFG that very obviously describe all DCFLs and nothing else. Such as LR(k) grammars. $\endgroup$ Apr 1, 2011 at 15:36
-
$\begingroup$ @reinerpost: true, but (in my defense) I wouldn't consider LR(1) grammars to provide a syntactic notation, because one needs to check the LR(1) condition. $\endgroup$– SylvainApr 3, 2011 at 20:37
$\begingroup$
$\endgroup$
5
In order to find a canonical representation, consider the following: the class of DCFL is equivalent to the class of languages generated by LR(k) grammars, which again is equivalent to LR(1). This means that you can find an LR(1) grammar for every DCFL. Of course, a LR(1) grammar is still a context-free grammar, but with a special property: from LR(1) grammars, we can easily build parse tables to guide a deterministic parser (with lookahead of 1 symbol, hence LR(1)). These parse tables would be another representation, albeit somewhat less readable.
By the way, mind that it is undecidable whether a given context-free language is deterministic (Greibach's Theorem).
I must admit I have never heard of VPL.
-
$\begingroup$ Well, canonical representations are rarely easy to read, but thanks for the directions. If Greibach's Theorem states that there are languages in CFL that cannot be decided to be in DCFL - how do you specify this languages? If you have a grammar, you could express it in Backus Naur Form (BNF), so Greibach's Theorem seems to imply that there is no subset of BNF that exactely expresses DCFL? Visibly pushdown languages are also known as "nested words". This class of languages is relatively new but relevant for parsing ordered trees and similar structures. $\endgroup$– JakobSep 9, 2010 at 16:05
-
$\begingroup$ About the undecidability issue: a language is a CFL if there exists a context-free grammar (CFG) generating it. If you are given a CFG, you can decide whether this grammar is LR(k), hence deterministic. (The same applies to pushdown automata -- it's easy to check whether a given PDA is deterministic or not.) However, suppose you have a CFG that's not LR(k) -- this doesn't mean that the language is not a DCFL; you just might not be able to find an LR(k) grammar for it. $\endgroup$– DaniCLSep 9, 2010 at 16:36
-
$\begingroup$ "you can decide whether this grammar is LR(k)" for fixed k. $\endgroup$– SylvainOct 14, 2010 at 12:48
-
$\begingroup$ @Jakob: Greibach's theorem doesn't state that, and even if it did, it would only mean that arbitrary CFGs aren't a suitable notation formalisms for DCFGs, just as they aren't a good notation formalism for regular languages (whether a CFG describes a regular language is undecidable as well). There is nothing wrong however with picking a subclass of the CFGs (e.g. the regular grammars for regular languages). $\endgroup$ Apr 1, 2011 at 15:42
-
$\begingroup$ There is a tradition of sloppy wording in textbooks here: they tend to make such statements as "it is undecidable whether a CFL is regular/deterministic" when what they really mean by that is "it is undecidable whether a CFG describes a regular/deterministic language". $\endgroup$ Apr 1, 2011 at 15:44