In the French Encyclopedia (1765, Volume 14), Beauzée made a clear distinction between the notion of government (Fr. rection) (one word imposes a special form on another) and the notion of complement. Except for the subject, Beauzée’s complementation corresponds to the modern notion of dependency and is illustrated by complete dependency trees, but by means of verbal description and not diagrams. Starting from the seminal work of Port-Royal (1660), which redefined the aim of syntax, we show how Beauzée’s clear vision of syntactic structure developed in the previous century. Three other authors are discussed: Buffier (1709), though unfortunately using an awkward terminology, was probably the first to propose a detailed dependency-based analysis of sentences and a dependency-based definition of parts of speech; Girard (1747), preferring a more constituency-based analysis, proposed a definition of the notions of government and syntactic functions and a remarkable formalization of word order rules; Du Marsais (1754), in his contribution to the first articles of the Encyclopedia, synthesized the main ideas of his predecessors on the notions of complement, heralding Beauzée’s clear-cut formalization.