10
$\begingroup$

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?

$\endgroup$
  • 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 Ito Sep 1 '10 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$ – Jakob Sep 2 '10 at 12:27
5
$\begingroup$

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$.

$\endgroup$
  • $\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$ – Jakob Oct 15 '10 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$ – reinierpost Apr 1 '11 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$ – Sylvain Apr 3 '11 at 20:37
3
$\begingroup$

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.

$\endgroup$
  • $\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$ – Jakob Sep 9 '10 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$ – DaniCL Sep 9 '10 at 16:36
  • $\begingroup$ "you can decide whether this grammar is LR(k)" for fixed k. $\endgroup$ – Sylvain Oct 14 '10 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$ – reinierpost Apr 1 '11 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$ – reinierpost Apr 1 '11 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.