We introduce the formal underpinnings of our theory of non-classical feature structures. The resuiting expanded universe of feature structures has direct implications for robust parsing for linguistic theories founded upon feature theory. We present an implementation of a robust chart parser for Head-driven Phrase Structure Grammar (HPSG). The problem of relaxed unification is in limiting it so that arbitrarily nongrammatical inputs needn’t be accepted. In the worst case, excessively “relaxed” parsers cannot provide meaningful interpretations to process. However, parsers which can guarantee minimally nongrammatical (inconsistent) interpretations provide an important tool for grammar development and online robust processing of natural language. Our parser prefers maximally consistent interpretations, and accommodates inconsistencies by discovering the minimal set of constraints that need to be relaxed for a parse to go through, without employing backtracking or post processing. The system is different from other related relaxational techniques for unification grammars which require advanced naming of features whose constraints are allowed to be relaxed. Yet it is compatible with those approaches in that there is a well defined location for preferences on sources of inconsistency to be named, as well as for resolution of inconsistent information. We use a simple approach to the problem of unknown words and suggest generalization of that for coping with missing and extra elements in an input.