Although Attribuate Grammars were introduced thirty years ago, their lack of expressiveness has resulted in limited use outside the domain of static language processing. With the new notion of a Dynamic Attribute Grammar defined on a Grammar Couple, informally presented in a previous paper, we show that it is possible to extend this expressiveness and to describe computations on structures that are not just trees, but also on abstractions allowing for infinite structures. The result is a language that is comparable in power to most first-order functional languages, with a distinctive declarative character. In this paper, we give a formal definition of Dynamic Attribute Grammars and show how to construct efficient visit-sequence-based evaluators for them, using traditional, well-established AG techniques (in our case, using the FNC2 system The major contribution of this approach is to restore the intrinsic power of Attribute Grammar and re-emphasize the effectiveness of analysis and implement- ation techniques developed for them.