I think that the problem mostly narrows down to the reference of NPs, since verbs, adjectives, adverbs and all kinds of function words, but also indefinite or quantified NPs like a car or all humans should be unproblematic1.
I can't give a complete algorithm, but some indicators (some of them already mentioned) would be:
- Demonstrative pronouns and determiners like this, that, such etc., both in pronominal (This is a serious issue) and in a determiner (this task) use are certain candidates for context dependence.
With a decent parser, you will be able to dereference (find the antecedent of) such items, but taking sentences in isolation, unless the reference relation is between several clauses of one sentences, such pronouns or determiners are highly context-dependent.
- The same applies for personal and possessive pronouns (he, his, it2 we, their, ...) - unless referring to an entity in the same sentence, they will not be understandable without context.
Depending on whether the reader knows the text's spaker and addressee, first and second person pronouns (I, you, we etc.) might be less problematic.
- Proper individual names like Mary or Ms. Smith, but also *insert some pseudonym* usually don't have context-independent references either.
You need to decide on your own whether Mary Smith can be understood without context or not; you probably would want to make exceptions for persons that are assumed to be known to everyone, like Mr. Obama or Mozart; for this kind of world knowledge, you'd need more advanced tools (first thought: look-up in an encyclopedia?) to find out to what degree the meaning of such names are assumed to be part of a regular speaker's knowledge or not.
Proper names of places (China, Los Angeles, Hudson River) or major events (World War II) can probably be assumed to behave similarly to known persons, i.e. rather context-independent - again, dependent on how much world knowledge you 1) assume in the speaker and 2) are able to feed your system.
- You should consider making exceptions for NPs involving genitive or adjective attributes, or in combination with a PP, gerund VP or relative clause3: the murderer is context-dependent, but the murderer of Caesar is not (PP), the requirements vs. the requirements for EU membership (PP), the fountain vs. the fountain in front of the Eiffel tower (PP), the engineers vs. the engineers designing NASA's Mars robot (gerund VP), the mother vs. Albert Einstein's mother (genitive attribute), the president vs. the French president (adjective attribute), the woman vs. the woman who discovered radium (relative clause), ...
You might need to elaborate more on this, e.g. it is also important that the references within the NP are clear (of Ceasar vs. of him), but in general I would say that adjuctions usually help disambiguating the referene of a definite NP.
You would need to test these heuristics out, might be that the restrictions are either to hard or too strong, but it would be a a first approach.
Your success will also depend on what other features your algorithm can make use of (pronoun resolution, world knowledge), what the reader might know about the text in advance (e.g. who wrote that text and thus who could be meant by context-dependent pronouns like we), what the reader might know in general (esp. the reference of names like well-known persons, geographic names or historical events) and of course what exactly you consider to be context-dependent or independent - this will always be a rather vague notion.
1 I admit that this is not always as simple, e.g. a participant is not clear without context (a participant in what?) despite it being indefinite, or all cookies (all cookies in the world or all cookies in the box on the table?) despite it being univerally quantified.
2 Note the difference between the semantically empty (and thus unproblematic) it in constructions like It isn't clear whether... vs. pronominal use (It has brown fur).
3 I think, however, that relative clauses work only to a very restricted extend; my example with The woman who discovered radium seems to work fine, but The woman who signed or The woman who washed clothes not so much. It seems to me that predicates without an object (no matter if the verb is by default intransitive, transitive or ditransitive; more objects always give more information) are always more context-dependent than ones with an object (The woman who signed vs. The woman who signed the contract between...), but even with that, it might not be clear who the referent is, as long as it is not a singleton set (there is only one woman who discovered radium, but many more who at some point washed clothes). Similarly, the president of the US is clear (there is only one), but the minister of the US is not (there is more than one minister and you need context to determine which one is meant), so even among very similar constructions, the degree of context-dependence might differ substantially.