Parsing with respect to grammars based on hyperedge replacement (HR) is NP-hard in general, even for some fixed grammars. In recent work, wehave devised predictive shift-reduce parsing (PSR), a very efficientalgorithm that applies to a wide subclass of HR grammars. In thispaper, we extend PSR parsing to contextual HR grammars, a moderateextension of HR grammars that have greater generative power, and aretherefore better suited for the practical specification of graph anddiagram languages. Although the extension requires considerablemodifications of the original algorithm, it turns out that theresulting parsers are still very efficient.