En sémantique, ou en parsing sémantique, beaucoup de modèles intègrent un principe de compositionnalité. Informellement, cela signifie que l'analyse est faite récursivement, le long d'un arbre syntaxique dont chaque nœud se voit assigner une représentation sémantique partielle. Dans ce cadre, quelle classe d'arbres syntaxiques adopter, pour quel type de composition sémantique ? Bien que beaucoup de résultats portent sur l'expressivité des formalismes syntaxiques seuls en termes de langages (ensemble de phrases grammaticales), on connait moins de choses sur l'expressivité des mécanismes compositionnels en termes de relations entre expressions linguistiques (phrases) et représentations sémantiques (graphes, formules logiques) correspondantes. Nous proposons d'étudier cette question dans un cadre théorique formel, et prouvons que pour capturer certaines relations, les mécanismes s'appuyant sur une syntaxe projective doivent garder en mémoire un nombre non borné d'emplacements distincts dans la représentation sémantique en construction, alors que le recours à une syntaxe non projective permet de nous soustraire à cette contrainte. Il suit comme corollaire que des formalismes grammaticaux décrivant les mêmes langages (mais pas les mêmes structures) ne permettent pas pour autant de capturer compositionnellement les mêmes relations d'interprétation sémantique.