There is a plethora of prior art on this problem, coming from the areas of formal syntax in linguistics, computational linguistics and also natural language processing. While there has been plenty of progress made on this problem there are also many open problems that researchers are working on, so it would definitely be worth your while reading up on some of the various introductory material on this topic so that you have a sense of what you can already easily accomplish using existing tools, and which things might see you biting off a bit more than you can chew.
The general problem of analyzing the structure of a sentence is referred to as
parsing and as has already been pointed out, there are (very roughly) two broad approaches towards tackling it. The one that is currently in vogue at the moment is to develop statistical models of the language you want to be able to parse by looking at the probabilities associated with sequences of words occurring next to each other and then automatically deriving a set of rules from the model. The advantage of this sort of approach is that you can throw more and more language data at your model - and we have lots of it these days - yielding significant improvements. They also tend to be more robust, which comes about because they are probabilistic. You can just ask the system to give you the most likely analysis, no matter how bad it actually is, and it will happily oblige. So the flip side to the robustness is that they tend to overgenerate - they provide analyses that are ungrammatical.
Since it sounds like you're after a test for grammaticality I think you're probably more interested the other broad approach which is often referred to as symbolic or rule-based approaches. These are usually grounded in a formal theory of linguistic syntax and there are many of these to choose from. Most of these center around the notion of a
grammar, an abstract device which is a set of rules encoding the constraints of a particular language. In fact, one way of thinking about these grammars is that they provide a model for grammaticality - if a sentence can be produced by your grammar then it is a valid sentence in the language; if the grammar does not license it, then it is ungrammatical.
In order automate the process of detecting grammaticality, just having a grammar on its own is not enough. You firstly need the grammar to be in a machine-readable form (ie code of some description) and you also need a parser, a bit of software which can apply the rules of the grammar to given input strings of your language. Luckily there are tools around to help you with this, so you don't have to reinvent the wheel. A great way to learn about implementing your own grammars would be with the Python Natural Language Toolkit. Chapter 8 of the accompanying book (which is available for free online) provides a hands-on introduction to writing grammars and exploring parsing algorithms. If you don't know Python or are new to programming the book also doubles as an introduction to programming.
The problem with 'toy' grammars of the type in the NLTK book is that they only describe a woefully small fragment of a language. Unfortunately this is also going to be true even of a grammar that you invest a fair bit of time developing. Many of the rules that govern our languages are readily apparent to us and can be encoded relatively straight forwardly but there are also a great many that occur so infrequently we hardly notice them or that are just so complicated it's tricky to describe a set of rules to capture them without negatively impacting other parts of the language. This is an inherent problem associated with hand built grammars that try to model grammaticality: the large amount of time it takes to extend the grammar to handle different linguistic rules and words from diverse topic areas. The lack of coverage over input text is a big reason why statistical approaches to parsing are popular - you almost literally just throw more data at the model and your coverage of the language increases.
Luckily for you there are a few linguistically-motivated grammars around that have quite a bit of development time under their belt so if all you actually want is the answer to the question "is this sentence grammatical?" then you could check out the English Resource Grammar which has a nice online interface and also the Link Grammar in the AbiWord program. Just remember that even though these systems are theoretical oracles regarding grammaticality, the practicalities of creating such a system means that unless you're throwing only basic sentences at them, don't automatically assume them to be infallible. If you're unsure, have a look at the analysis it's given you (if any) and see if it makes sense. If it doesn't perhaps you've found a bug in the grammar, a place for improvement.
So where you could go from here...
- A great text book to read would be Speech and Language Processing by Jurafsky and Martin (specifically section III on Syntax)
- Play around with the NLTK and build your own grammars. You won't end up with a wide-coverage grammar but it'll be fun and you'll learn a lot.
- Read up on some the history of the interplay between linguistics and computational linguistic/natural language technology in the open access journal Linguistic Issues in Language Technology (it's fascinating stuff)
- Read up on the art of grammar engineering, the practice of developing large-scale linguistically motivated machine readable grammars: a good paper is Grammar Engineering for Linguistic Hypothesis Testing by Emily Bender and another is the second chapter in Language from a Cognitive Perspective: Grammar, Usage, and Processing Edited by Emily M. Bender & Jennifer E. Arnold, but it doesn't seem to be available online.
- Or just play around with an existing end-to-end parser that has reasonably good coverage. The English Resource Grammar would be a particularly good one to look at.