We present a novel way to implement hierarchical structure and test its learnability in an artificial language involving structure-dependent, long-distance agreement relations. In Experiment 1, the grammar was exclusively cued by phonological and prosodic markers similar to those found in natural languages. Experiment 2 contained additional semantic cues in the form of a reference world. At the group level, successful generalization of the phrase structure rules to new words was found in both experiments. Analyses of individual profiles show that a subset of participants also generalized their knowledge to novel phrase structure rules, instantiating a natural extension of the training grammar, based on recursion of coordination. Rule induction improves across-the-board in the presence of semantic cues. It is concluded that adults are able to develop, to some extent, abstract knowledge of hierarchical, structure-dependent representations despite impoverished input data and minimal training.