Take the 2-minute tour ×
English Language & Usage Stack Exchange is a question and answer site for linguists, etymologists, and serious English language enthusiasts. It's 100% free, no registration required.

This almost feels like a SO question.

Is there an EBNF that covers all of English, and if so, what is it?

share|improve this question
4  
We should be so lucky! If anything like that existed all those programmers working on writing a natural language parser would probably be out of work! –  FumbleFingers Jul 1 '11 at 21:30
1  
Um. What is an EBNF? Do you eat it or drink it? (I checked the Wiki link. I still don't know.) –  JPmiaou Jul 1 '11 at 21:32
2  
@FumbleFingers: None of those programmers would be out of work, in fact, they probably already have this construction, but in a highly non-canonical form (I played with an online sentence parser). Their problem is that the parsing you get from a typical EBNF is ambiguous, and in many more ways than it is supposed to be ambiguous. You get too many parsings for each sentence. I will give tricks for reducing the number of parsings to the correct number. I am not sure which tricks are the best right now. –  Ron Maimon Mar 10 '12 at 4:03
1  
@FumbleFingers: These approaches are due to the fundamental matching problem: "The man ate the chicken on the bed with a fork" has an ambiguity of whether the chicken is on the bed or the man, and whether the chicken has the fork or the man does. These things are ubiquitous, so Google is trying to avoid the problem by using non-context-free regular grammars. This is not likely to work great, but its better than semantic-less context-free grammars, because "chicken with a fork" does not return many hits, while "eating with a fork" does. The only way to do it right is context-free + semantics. –  Ron Maimon Mar 10 '12 at 20:44
2  
"doing it right" would really mean addressing a specific problem, not trying to generalize the "English Language" (whatever is meant by that). A generalized solution seems silly, considering the amount of AI required to process a natural language. You must apply lots of assumptions and restrictions, led by a specific problem definition you're trying to solve. –  tenfour Mar 12 '12 at 0:42

3 Answers 3

up vote 19 down vote accepted

No.

It's been well demonstrated in the linguistic literature that natural human languages, including English, cannot be captured in a context-free grammar.

Here's a link for you (PDF): Evidence against the context-freeness of natural language

share|improve this answer
2  
This answer is 180 degrees opposite of the truth, and links to an irrelevant paper that uses a Swiss German construction which does not parallel any English construction. The answer for English is yes, and it does not put any parsing people out of work. The EBNF is only the start of the parsing project. They have pretty good ones today, but their problem is not that they don't capture all English sentences, but that they are too nonunique, they give too many interpretations to a given sentence. This answer is lousy, and it should not be accepted or upvoted. –  Ron Maimon Mar 10 '12 at 4:05
2  
+1, because this is a good answer. –  Mahnax Mar 12 '12 at 2:29
    
just curious, why does it use Swiss German as opposed to English? (the paper is written in English, Swiss German is probably obscure to most English reader) –  Louis Rhys Apr 28 '12 at 8:32
    
Geoffrey Pullum disagrees: dl.acm.org/citation.cfm?id=970173 –  Wes Nov 22 '13 at 15:42
    
There is a machine-readable dialect of English called Attempto Controlled English: en.wikipedia.org/wiki/Attempto_Controlled_English –  Anderson Green Jul 15 at 6:41

If by "English" you mean "any utterance that might be written or uttered by a native English speaker", then English — and indeed any language for that matter — is far too complex probably for such a thing to exist. (And as JSBangs points out, there are reasons for believing that such a thing couldn't even exist in principle.)

If by "English" you're prepared to accept a highly constrained subset of English, then you might consider the rewrite rules that exist, for example, in early Chomskyan models of syntax. In symbolic form, these express things like "PP → P NP" ("a prepositional phrase is rewritten as/comprises a preposition plus noun phrase").

In reality, applications that need to do syntax parsing usually end up employing an algorithm that allows multiple candidate analyses to be assessed in parallel. There are several variants of this approach that essentially fall under the umbrella of "dynamic programming" — look in particular at something called the Viterbi Algorithm.

share|improve this answer
    
This is complete nonsense. You can give an EBNF for your entire answer, and the question, and all the stuff on this stackexchange, minus some unusual constructions that hardly ever occur. –  Ron Maimon Mar 10 '12 at 4:06
7  
Well, do publish... –  Neil Coffey Mar 10 '12 at 5:35
    
It would not be accepted in any journal, because it is too trivial. It is also probably well known to all those folks who do the NYT parsing challenge every year. Instead I will post it here. There might be bugs, I haven't programmed it into a computer to test all the productions, but if people check it by hand, these but bugs will be easily fixable, because the general idea is correct. –  Ron Maimon Mar 10 '12 at 5:56
2  
OK, excellent. Until proven wrong, I think I stick by the essence of my argument, though: an EBNF grammar would only cover a fairly constrained subset of English and it isn't usually the technique used in most parsing applications. –  Neil Coffey Mar 10 '12 at 15:30
1  
I wonder if we're arguing about a problem of nomenclature here? I think you could argue that some form of context-free rules form a very basic-level component of many parsing systems. But as far as I'm aware, in most systems these are really a very low-level component then sit underneath other components (as you say, to resolve ambiguities among other things), including in many cases some kind of statistical model -- which in my mind constitutes "context". Maybe the post you promised might help clear this up? –  Neil Coffey Mar 11 '12 at 6:05

The answer is best approximated as "yes", although there are some strictly non-context free components of English. The approximation of saying "English grammar is context free" is more true than false, in that the vast majority of the sentences you will encounter will be parsable by a simple EBNF, and all of them will be parseable by a mild extension of EBNF that I will describe below, and which does not require anything more than a stack plus some list-variables to keep track of permutable objects.

The permutable list variables you have to keep track of in the parsing algorithm are (probably) not strictly context free constructions, but they are not deep modifications of the context-free grammar idea, and there will be a preferred ordering of the list which is the one most commonly occurring in the New York Times, which is strictly context free.

I did not thoroughly bug-check the grammar, but it is mostly okeh.

The Generating problem and the Parsing Problem

There are two different problems in a formal grammar, the problem of generating all outputs and the problem of parsing a given output. To illustrate, consider the following BNF:

SENTENCE: ALIST | BLIST
ALIST: "a" ALIST | "a" BLIST | ""
BLIST: "b" BLIST | "b" ALIST | "ba" ALIST | ""

The very simple rules for generating the productions of the grammar are given above. The vertical line is read "or", and it separates options for expanding the objects in capitals. The stuff in quotes are actual letters, and the empty string "" means that you produce nothing. To start, you have one symbol

SENTENCE

Then you replace SENTENCE with one of the options to the right of the colon. For illustration, take ALIST

ALIST

Now you replace ALIST with one of its options (removing the quote marks),

a BLIST

Now replace BLIST with one of its options, and so on, until you run out of capital letter things. The capital letter things are called "nonterminals", and the lowercase things are called "terminals" or "leaves". The result in this case is a string of alternating a's and b's:

ababbabbab

Each finished product is a sentence of the language. Since I have given the rules explicitly, all productions are generatable by a simple algorithm.

The problem of parsing is going backwards--- given a sentence, figure out which rules were used to construct it. The problem of parsing is harder than the problem of generation, because it is usually ambiguous. The sentence

abaa

could have come from a-ba-a using the second BLIST option, or from a-b-a-b. This is the main difficulty in parsing, and different presentations of the same language sometimes have different amount of ambiguity. For special grammars, there is no ambiguity, and these are the kind that are most often used in computer languages. The C programming language is presented in an LALR (left-to-right) BNF that can be automatically parsed by the UNIX classics lex and yacc (or their free software versions, flex and bison).

The main type of grammars that people study are the context-free grammars, where the stuff on the left is just one symbol in capital letters, one nonterminal. General grammars are defined as the output of any conceivable computer program, and so are too general to be useful. There are also other classes, which I will completely ignore, because the context free class is the closest one to linguistics.

The prototypical example of a nontrivial context free grammar is parentheses matching of two different kinds of parentheses:

SENTENCE: S
S: "(" S ")" | "[" S "]"

This grammar generates all sentences which are properly balanced nested parentheses of two kinds, square or round. A more interesting example is

SENTENCE: EXPR
EXPR : EXPR "+" EXPR
| EXPR "*" EXPR
| "(" EXPR ")"
| NUMBER
NUMBER : "0" | NONZERODIGIT DIGITLIST
NONZERODIGIT: "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
DIGIT: "0" | NONZERODIGIT
DIGITLIST: DIGIT DIGITLIST | ""

You read this left to right as follows: "a SENTENCE is an EXPR", "An EXPR is an EXPR plus an EXPR or an EXPR times an EXPR, or an EXPR in parentheses, or a NUMBER", etc. This grammar generates every arithmetic expression you use in grammar school. The C programming language is generated by a simple context free grammar, as are nearly all programming languages in use today.

The context free grammars are distinguished from the regular grammars, which have at most one nonterminal on the left and on the right. The regular grammar describes a finite state language, which can be "lexed" by a "lexer" rather than "parsed" by a "parser". An example of a lexed regular language is the NUMBER grammar in the example above. You only need to remember a finite number of things in the past to determine if a number is well formed, and you never need to look at a far away place, as you do when you are trying to check if parentheses are properly balanced.

This stuff is standard, and is discussed in detail on Wikipedia and elsewhere. I only give a quick review to establish some examples, and for completeness sake. It is related to a fascinating theory of finite state machines and stack machines, which is good to understand.

The EBNF

A BNF is a set of rules for rewriting a nonterminal in terms of other nonterminals. I will give a trivial linguistic example.

SENTENCE: STATEMENT | QUESTION | COMMAND
STATEMENT: SUBJECT VERB ADVERBLIST OBJECT "."
QUESTION: "Hey," DO SUBJECT VERB ADVERBLIST OBJECT "?"
| DO SUBJECT VERB ADVERBLIST OBJECT "?"
| "Hey, dood, " DO SUBJECT VERB ADVERBLIST OBJECT "?"
COMMAND: VERB ADVERBLIST | VERB ADVERBLIST OBJECT
ADVERBLIST: ADVERB ADVERBLIST | ""
ADVERB: "quickly" "slowly"
DO: "do"
VERB: "run" "walk" "hop"
OBJECT: "here" "there" "everywhere"
SUBJECT "we" "they" "the bunnies"

This grammar is kind-of stupid (it is also regular, although the presentation above does not make it obvious at first glance). It generates a ridiculously tiny subset of English consisting of sentences, questions, and commands about bunnies and plural people who go places by various means of locomotion:

"hey, dood, do the bunnies run quickly quickly slowly here?"
"we hop slowly quickly here?"

The sentences are dumb. The only recursive part of the grammar is the part that generates the adjective list. This pattern, making a list, occurs very often:

ADVERBLIST : ADVERB ADVERBLIST | ""

I will abbreviate this nonterminal "ADVERBLIST" by calling it "ADVERB[]", with the brackets meaning a list of zero or more adverbs, and omitting the rule which forms it. This means I am using an extension of BNF, so it is EBNF (extended BNF).

Further, there are lots of cut-and-paste operations in the BNF for QUESTION above, corresponding to a certain thing being either present in one form or another. I will abreviate options using a nested parentheses language inside the BNF itself:

QUESTION : ("hey" | "hey, dood," | "") DO SUBJECT ADVERB[] VERB "?"

Hopefully this is self explanatory. This means that one BNF line can actually stand for very many replacement rules, since

QUESTION: ("hey" | "hey, dood," | "") DO ("" | "tell if" | "tell me if") SUBJECT ADVERB[] VERB, ("yo?" | "huh?" | "huh, yo?" | "?")

generates 36 different sentences.

Further, I will use the standard EBNF abbreviation of square brackets for an optional construction, [X] is the same as (X | ""). These types of EBNF are no good for lex and yacc, but you can manually expand them out to a real BNF, so they are still context free constructions.

QUESTION: ["hey" [",dood]] DO [ "tell" ["me"] "if" ] SUBJECT ADVERB[] VERB ["huh"]["yo"]"?"

The above is equivalent to the previous, but more compact.

Commutative extended BNF

The main problem with a BNF description is that it generates a completely different structure for the sentences

"to the store I went"

and

"I went to the store"

when their semantics are identical. The first is just a poetic rearrangement of the second, and a speaker will understand it just fine. But the BNF will glob together the "to the store" to a structure, which I will call an "ADVERB" (I really don't care what other people call it) because it attaches to "the store". The problem is that

ADVERB I went

and

I went ADVERB

attach in different ways in the formal grammar, because you need to go through the "I" in the first case. Further, the following production

I to the store went

is also marginally poetically acceptable. If you think this sounds forced, consider

"Without a fork, I, by a stream and on a chair, ate the chicken"

This is perfectly fine, and equivalent to

"I ate the chicken by a stream and on a chair without a fork."

In a normal BNF or EBNF description, the different ADVERBs in the sentence attach to the VERB in different ways depending on their relation to the verb, whether to the left or to the right, and even worse, in different ways depending on their relation to the subject, whether they are to the left or the right of the subject.

To fix this, I will leave the class of context free languages (maybe, perhaps this doesn't leave the class, I didn't prove it yet one way or the other, and it really doesn't matter for the practical purposes of linguistics). I will introduce another extension to the BNF, namely a "+" sign. A nonterminal with a plus sign attached can freely commute with all nonterminals not enclosed in parentheses by moving to the right. So during productions, it can slide around parentheses to the right as many times as it likes:

STATEMENT: ADVERB+[] SUBJECT (VERB OBJECT)

means that there is a list or ADVERB+ objects, which can slide past subject, or past the unit (VERB OBJECT). This construction is a pain in the neck to code generally, it isn't covered by lex and yacc. There might be a simple way to replace it with different rules, for example

STATEMENT: ADVERB[] SUBJECT ADVERB[] (VERB OBJECT) ADVERB[]

But this sort of thing leads to a prolifiration of different kinds of nodes (since each different kind of merge operation of two things into one in a basic description produces a different kind of node) and the prolification of node types (when their semantics is obviously the same) is the bugaboo of natural language generation. I will not put things in standard EBNF form, and I will use the "+" construction above.

While you can't feed this into yacc, it is still not to hard to code a parser by hand for commutative EBNF's (at least the ones that come up in English). Perhaps somebody will write an automated parser for commutative BNF's, but if the grammar is simple enough, a hand coding might be sufficient.

Nonobvious context-freeness of English

When you have a complex sentence, there are adjective-like and adverb-like phrases that can occur as embedded phrases:

"With a sword, tall and gallant, on a rock, breathless and encumbered, by a stream, over the field, armored in chains, without mercy, John slew the Jabberwock!" or

"Tall and gallant, by a stream, John, on a rock, breathless and encumbered, over the field, slew the Jabberwock, (John was) armored in chains, without mercy!"

I placed (John was) to indicate that the adjective like phrase should not attach to Jabberwock, which is the preferred parsing of native speakers. The attachement to John is also an ok parsing, but less salient.

The adjective-like phrases "tall and gallant" and "armored in chains" occur with no particular order preference in the list of adjective and adverb phrases. This means that as you parse the sentence, you keep track of the adjective list (each of which might recurse down several times) and the adverb list (each of these might recurse), and when you are done, you attach the adjectives to the subject, and the adverbs to the verb. The verb object is the exception--- it is tightly attached to the verb. You can't move this guy around, or stuff things between it and the verb.

I should point out that in terms of style, you are generally supposed to do it like this:

ADVERB, ADVERB ... ADVERB, ADJECTIVE, ADJECTIVE ..., ADJECTIVE SUBJECT ADJECTIVE ADJECTIVE VERB ADVERB, ADVERB...

So that it will appear:

"on the stream, by the river, without mercy, tall and gallant John, breathless and beaming, armored in chains, slew the Jabberwock over the field."

In this order, you can make it context free for sure, because you can glob up the initial adverbs and the final adverbs first, then the middle adjectives to the subject, then the adverbs, subject, and verb into a sentence. I don't like this, because to a speaker all permutations are semantically equivalent, since they attach the same things to the same things.

A subtle point appears here: while you are allowed to say

The man with a limp shot the deer.

If you say,

with a limp, the man shot the deer

the semantics changes--- the phrase becomes an adverb for sure. In the second position, it is more likely that you would bind "with a limp" as an adjective to "the man" rather than to the "shot the deer" as an adverb.

Recursive Skeleton English

The main commutative EBNF rules are:

SENTENCE: STATEMENT | QUESTION | COMMAND
STATEMENT: ADJ+[] ADVERB+[] (SUBJECT) ADJECTIVE+[] (VERB)
QUESTION: ADJ+[] ADVERB+[] (DO SUBJECT) ADJECTIVE+[] (VERB)
COMMAND: ADJ+[] ADVERB+[] (VERB)

ADVERB: ADV
| WHEN (STATEMENT)
| IF (STATEMENT)
| GERUND
| PREPLY NP
ADJECTIVE: GERUND | PREPISH NP | ADJ
WHEN: "when" | "whereby" | "until" | "unless"
IF: ["not"] ("if" | "only if" | "because")
AND: "and" | "but" | "or"
PREPLY: [not] ("to"|"onto"|"into"|"of"|"out of"|"in"|"within"|"by"|"with"|"without")
PREPISH: [not] ("to"|"of"|"in"|"by"|"with"|"without")
ADJ: ADJ ("and"|",") ADJ | GERUND
NP: (("a"|"the") (ADJ+[] SNP))} WHICH CLAUSE
CLAUSE: ADJECTIVE+[] ADVERB+[] SUBJECT VERB
| ADJECTIVE+[] ADVERB+[] SUBJECT VERB PREP
SUBJECT: NP
OBJECT: NP
WHICH: "that" | ""
GERUND: FOGHORN GER
FOGHORN: (PREPLY "-" NP)[] "-" OBJECT
ADJ: ADJ AND ADJ|
"purple"| "smelly"| "happy"| "windy" | "unbelievable" etc.
ADV: ADV AND ADV |
"quicky" | "slowly" | "happily"
NOUN: "cat" | "dog" | "man" | etc.
VERB: ("berate" [OBJECT]) | ("stop" [OBJECT]) | ("flee" [OBJECT]) | ("put" OBJECT) LOCATION+ ...
GER: "berating" | "stopping" | "fleeing" | "putting" etc.

Plurals, tenses, passive constructions, subject-verb matching, and a bunch of other things English incorporates are not incorporated in this BNF, and neither are the required argument rules, just the recursive structure of the phrases. The remaining stuff is complicated annoyance that doesn't touch the embedding structure. This embedding structure is what is more-or-less universal across all old world modern languages.

Disclaimer: This is a draft skeleton, and I have not debugged it. I am sure it is full of nonsense, since it is late at night.

Unambiguous English

The main ambiguity problem with parsing English is that sometimes the "with a fork" attaches to nouns and sometimes to verbs. For example:

I ate the Chicken with one leg with a fork

might be parsed as

ate(subject=me, object= Chicken(the:with one leg, with a fork)) ate(subject=me, object=Chicken(the: with one leg), with a fork) ate(subject=me, object=Chicken(the: with one leg, with a fork)) ate(subject=me(:with one leg), object=Chicken(the,singular),with a fork))

etc. depending on whether the eating was done with one leg, or with a fork, or whether these are attributes of myself, or of the chicken. This ambiguity makes it difficult to decide how to attach the ADVERB and ADJECTIVE arguments properly to what thing.

In order to eliminate this ambiguity, and make an unambiguously binding English-like language with the exact same word order, you can introduce the prepositions

with-ish of-ish on-ish to-ish

etc, to indicate that these attach to a nounphrase, not to a verb. I will write all ADJECTIVEs which modify the subject to the far left, and all adjectives which modify the various objects next to those objects. Further, there is the ambiguity of nesting level--- which depth of stack you are supposed to be on for each ADVERB and ADJECTIVE. I will indicate this using parentheses level. Then English becomes unambiguous. Further, these rules generally match the preferred style of the New York Times.

With-ish one leg, I ate (the Chicken) with a fork.

i.e. one-legged me ate the chicken using a fork.

I ate (the Chicken with-ish one leg) with a fork

i.e., I ate the one legged chicken using a fork

I ate (the Chicken with-ish one leg with-ish a fork)

i.e. I ate the one legged chicken which possesses a fork, which perhaps it uses as a prosthesis to replace its missing limb.

Unambiguous English might be a good target for starting semantics. It shouldn't require much to tell a computer that chickens can often have one leg, but more rarely have a fork. The semantic web construction from the nouns and the verbs and their attachments is not a hopeless project, but it is a difficult one, which requires ingenuity. The grammar problem is much easier, and a variation on the stuff above should solve it completely.

share|improve this answer
9  
This is like coming to a medical research center and saying "I wrote a guide that can be used to diagnose 100% of medical ailments." To a doctor this will seem like a naive pursuit (which just implies that it should be more modestly described), and without even looking, an incomplete result at very best. Just saying... –  tenfour Mar 11 '12 at 20:28
1  
@tenfour: It is not like coming to a medical center, because you and everyone else already have an algorithm in their heads which decides if a sentence is grammatical. It's not very complicated, I just described the major recursive constructions explicitly. I left out "the apples picked in 2003" and other that-omitting past-tense constructions (but the present tense analog is included). If you refuse to read the content of this post, which describes how to do natural language generation, you won't understand English grammar. –  Ron Maimon Mar 12 '12 at 2:54
2  
"I just described the major recursive constructions"... of course you can parse a subset of English with EBNF. The question is about "all" of English. And don't forget that "English" is more than just grammar, which many have already told you in other posts. –  tenfour Mar 12 '12 at 9:18
1  
@tenfour: English is not much more than the grammar and binding rules. Once you have this, you can start discussing semantics, because you know what can bind to what. I am annoyed that nobody is actually dealing with the content of the post, which is a construction of the complete recursive structure of a major natural language. –  Ron Maimon Mar 12 '12 at 16:27
1  
As it has been demonstrated already by others, you need real world semantic understanding even to parse grammar properly. –  tenfour Mar 13 '12 at 14:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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