Nowadays input data for parsing algorithms are not limited to be linear strings, and context-free grammars are used not only for programming languages specication. One classical example is context-free path querying for graph data bases where an input is a graph and path constraints are specied by a grammar. Graph parsing may nd an application in dierent areas: in software engineering for dynamically generated strings analysis, in graph data bases for paths querying, etc. Our group is working on several questions posed in this area which still do not have satisfying solutions. We present our efforts which are mostly aimed at improving performance, lifting up limitations on an input and nding new elds of application for graph parsing.