10

Is there a way to test to see if a string of words forms a complete sentence?

For example: 

The dog jumped over the fence == Good 
The cat square seven the triangle == BAD

I was thinking the type of words (verb, noun, etc.) and order of the words would help in creating a rule set to test the sentence against. But before I run off and code up all the sentence rules I know I am looking for any prior art on the subject.

Improve this question
6
  • What do you mean here by tagging it as "constructed-language"? I can imagine a language where the phrase The cat square seven the triangle could be perfectly correct and mean something like The dog jumped over the fence. Besides, your definition of correctness is too broad...
    – Alexander Galkin
    Commented Nov 29, 2011 at 20:03
  • 4
    This is called "parsing," and it is an open question in computational linguistics. (Though it is most usually approached not as a task of giving a grammaticality judgment, but rather assuming a sentence is grammatical and finding the "best" way to assign structure to it.) The approach you suggest -- using grammatical rules -- has been basically replaced by complicated statistical algorithms.
    – Aaron
    Commented Nov 29, 2011 at 20:30
  • @Aaron: This not called parsing, it's called "generating", and as far as I know, generating is not an open problem. It is not so difficult to write a program to generate English grammar, and then a sentence is grammatical if it is produced by the program. The "parsing" problem requires you to go backwards, and then you get a plethora of "I ate the chicken with a fork" ambiguities: did I eat with a fork, or did the chicken have a fork? These ambiguities generally require semantics to resolve, and this is the difficulty in parsing. But there is no difficulty in generating.
    – Ron Maimon
    Commented Mar 5, 2012 at 13:27
  • @Alexander Galkin: "The cat square seven the triangle" would never be grammatical in any language is square cat triangle are all nouns and seven is an adjective, because it has no verb. It is grossly misleading to say this, it isn't true. Generating English is not an open problem.
    – Ron Maimon
    Commented Mar 5, 2012 at 13:31
  • @RonMaimon: 1) There are thousands of languages in the world which don't require a sentence to have a verb -- take any slavic language, for example Russian or Polish. 2) How do you know there is no verb here? POS determining is not a trivial task, the classical example is "cat mothers little tigers" -- do you see a verb here?
    – Alexander Galkin
    Commented Mar 5, 2012 at 19:23

3 Answers 3

Reset to default
12

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.
Improve this answer
5
  • 1
    While this answer is Ok, I can't find sentences in English that don't follow the most simple straightforward BNF you can write down. This doesn't solve parsing, because of ambiguities that require semantics, but it does solve the problem of "is this sentence grammatical", which is easier. You don't have to parse the sentence in the way preferred by native speakers to decide grammaticalness, only show that you can parse in some way.
    – Ron Maimon
    Commented Mar 5, 2012 at 13:33
  • So yes, creating individual grammars in a post-hoc fashion for each sentence you can think of is not all that hard. But what we really want is one single grammar which accepts every grammatical sentence whilst rejecting those which are ungrammatical. Try to do this with BNF and your head will start to hurt very quickly.
    – nedned
    Commented Mar 6, 2012 at 6:19
  • I am not creating individual grammers post-hoc. I can write down to you a complete English grammar in a modified commutative BNF today which will accept every grammatical English sentence in the New York Times, and reject all clearly ungrammatical ones (with some borderline cases and too-complex-for-humans-to-parse ones too of course). I did a sketch as an exercize while learning BNF long ago. I checked it recently, and I found a few rare constructions which are missing, "Only if Jane cooks will I eat" (archaic reverse word order). The BNF includes everything else ...
    – Ron Maimon
    Commented Mar 6, 2012 at 6:28
  • But it is a commutative modified BNF, meaning that the language is strictly not context free. The addition is that you can permute adjective like and adverb like phrases at the same level. This is the only non-context freeness, and it occurs in "Briefly, holding a sword, fleetingly, tall, tan King William saw the Jabberwock!" (the adjective-like and adverb-like phrases are interspersed at random). This might not be grammatical to some, who would put the adverb-phrases (sometimes verb arguments) before the adjective-phrases. But I allow them to permute as units on the same level.
    – Ron Maimon
    Commented Mar 6, 2012 at 6:32
  • This commutativity wrecks context freeness, and makes writing a parser (a little) harder, but commutativity fixes 99% of the false ambiguity in formal parsings of English, leaving only the ambiguity which speakers apparently see in the sentence themselves. I will post the BNF as an answer to this question, and explain the commutativity idea--- it isn't hard to understand. It's why "1+3+4+7" has only one parsing, (1+3)+(4+7) has the same semantics as ((1+3)+4)+7 or any other of the many parenthesizations. I know modern formal grammars fail to take commutativity into account.
    – Ron Maimon
    Commented Mar 6, 2012 at 6:35
5

I'm going to give a silly answer that might be helpful, and I'll let someone else give the more serious answer. Here it is.

  1. Go to http://erg.delph-in.net/logon
  2. Enter your sentence.
  3. See whether it returns a parse.

The link I have given is for an online implementation of the LinGO English Resource Grammar, which is a rather heavy-duty implementation of English grammar in HPSG.

Improve this answer
2
  • +1: This answer is not silly--- I tried a bunch of examples, and the grammar seems good. It even handles strange gerund adjectives: for "the car on the table putting boy went home.", all the variations were grammatically possible readings. It works for "If if Jane cooks only if John helps, you're leaving then I'm not inviting you." What is it missing?
    – Ron Maimon
    Commented Mar 5, 2012 at 13:46
  • I now know what it is missing, and I will write about it: it is the non-context free part of English, which is only a minor commutativity issue which is trivial to fix up. I automatically did so in my "BNF", so it's technically not BNF, but something else, and the language it describes is not context free, but something else "same-level commutative context free", which is (maybe not strictly) between context free and context sensitive.
    – Ron Maimon
    Commented Mar 6, 2012 at 6:22
4

As for prior art, there is quite a lot. Formal grammars use a theory of language to encode the grammar of a language. You can go through the links I gave when answering a related question. ERG that jlovegren mentioned is one such example. Other examples would be XTAG and XLE, both of which have fairly comprehensive grammars for English, just like ERG, and OpenCCG, which, at the moment, does not have a comprehensive grammar for English, but has it for a few other languages.

Statistical algorithms, these days, far out-perform hand-written grammars when it comes to "understanding" a sentence. However, the designers of most statistical parsers have designed their systems to make the "best possible sense" of every sentence, and so, are poor at detecting grammaticality.

One system that is already used to detect grammaticality of sentences is Link-Grammar which happens to be integrated into AbiWord.

I could go on, but this should be enough to start with.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.