deterministic dependency parsing of english text this paper presents a deterministic dependency parser based on memory-based learning, which parses english text in linear time. when trained and evaluated on the wall street journal section of the penn treebank, the parser achieves a maximum attachment score of 87.1%. unlike most previous systems, the parser produces labeled dependency graphs, using as arc labels a combination of bracket labels and grammatical role labels taken from the penn treebank ii annotation scheme. the best overall accuracy obtained for identifying both the correct head and the correct arc label is 86.0%, when restricted to grammatical role labels (7 labels), and 84.4% for the maximum set (50 labels). we propose a variant of the model of yamada and matsumoto that reduces the complexity, from the worst case quadratic to linear. our deterministic shift/reduce classifier-based dependency parsing approach offers state-of-the-art accuracy with high efficiency due to a greedy search strategy.