A heuristic driven chart-parser for attributed node labeled graph grammars and its application to feature recognition in CIM

Abstract

To integrate CA*-systems with other applications in the CIM world, one principal approach currently under development is the feature recognition process based on graph grammars. It enables any CIM component to recognize the higher-level entities - the so-called features - used in this component out of a lower-data exchange format, which might be the internal representation of a CAD system as well as some standard data exchange format. In this paper we present a 'made-to-measure' parsing algorithm for feature recognition. The heuristic driven chart based bottom up parser analyzes attributed node labeled graphs (representing workpieces) with a (feature-)specific attributed node labeled graph grammar (representing the feature definitions) yielding a high level (qualitative) description of the workpiece in terms of features.