Some remarks are necessary before answering such a question. CFGs have been an important step in the history of formal grammars, but it is not exactly the example we want to follow in DG and in natural language modelling in general. CFGs are string rewriting systems, that is, grammars that generate sets of strings of words. But to speak English is not to be able to generate all the acceptable strings of words in English. To speak English is to be able to understand English sentences, that is, to associate a meaning to appropriate strings of words. Or conversely, to express every meaning we want to express, that is to associate a string of words to a meaning (excluding phonology, prodosy and so on). (This point was already stated by Tesnière 1959, ch. 6, §4: "speaking a language involves transforming structural order to linear order, and conversely, understanding a language involves transforming linear order to structural order.")
CFGs have been successful because the derivation of a string can be interpreted as a constituency tree. But the CFG itself does not really generates the constituency tree. This problem was solved with the tree grammars, and the most famous of them, TAG (Joshi et al. 1975). Such grammars are interesting because they simultaneously generate a string of words and a tree structure. This is a good step in the direction we want to follow to model natural languages and define formal DGs.
Now we can answer the question. We can propose grammars generating strings whose derivations can be interpreted as dependency trees. It is even possible with CFGs (see the strong equivalence between Hays' grammars and "lexicalized" CFGs in gaifman 1965). But it is not really what we want. It is simpler and more useful to define grammars that directly generates linearly ordered dependency trees (which is more or less equivalent to transductive grammars associating strings (= linear order) to dependency trees). A very simple way to generate a linearly ordered dependency tree is to generate it by pieces, like TAG with constituency trees. The simplest DG we can imagine as only to kind of rules:
lexical rule generating nodes, for instance (Mary, N), (Peter, N), (loves, V) …
dependency rules generating dependecies, for instance (V, N, subj, <), (V, N, obj, >) …
The rule (Mary, N) says that "Mary" is a noun (N).
The rule (V, N, subj, <) says that between a V and N we can generate a subject dependency where the dependent (N) is before (<) the governor.
Such a grammar generates "Mary loves Peter" and its dependency tree.
For the details and the generative as well as the transductive interpretation of such a grammar, see my paper: KAHANE Sylvain, 2001, What is a natural language and how to describe it? Meaning-Text approaches in contrast with generative approaches, Invited talk, Computational Linguistics, Proc. CICLing, Mexico, Springer Verlag, 1-17.
The previous grammar is very simple. It only works if we suppose that the dependency tree is projective. To generate non projective depednency trees we need a more complicated formalism, such as topological grammars (GERDES Kim & KAHANE Sylvain, 2001, Word order in German: A formal dependency grammar using a topological hierarchy, ACL, Toulouse)
The previous grammar cannot control the subcategorization. To do that we can extend the locality domain of the rules and to have rules corresponding to bigger pieces of the tree than just one node or one dependency (Kahane S. (2006) Polarized Unification Grammars, Coling-ACL, Sydney). Note that this last formalism, PUG, is a "paradigmatic" formalism which allows to define a wide paradigm of grammars.