In linguistics, the influence of the results by Tesnière cannot be under-estimated: above all, he introduced the concepts of dependency and valency, which had a considerable influence in the development of linguistics by the second half 20^th century. However, his Structural Syntax remains still uninvestigated in most parts: in particular, there is still no grammar formalism directly inspired by it, that is suitable for theoretical and practical applications in Artificial Intelligence and computational linguistics. The aim of this paper is to fill this gap, in proposing a formal grammar that adopts Tesnière's intuitions and concepts of Structural Syntax—as much as possible—in adapting them to the needs of contemporary linguistics, notably natural language processing. The result of this modelling process is a new formalism derived from Tesnière's, where natural language grammars are expressed in constructive mathematical terms (and therefore suitable for computational treatment) where the abstract notion of adposition is of the greatest importance. For these reasons, they are called Constructive Adpositional Grammars (CxAdGrams). This paper explains the linguistic and formal reasons of CxAdGrams, with a special regard to the heritage of Tesnière and its relations with existing dependency grammar formalisms in terms of similarities and differences.