12

The tools for working with BNF grammars are a little more discoverable (ANTLR, Gold, etc) and usable than for other types of grammars. What sort of sentences can't be represented with ordinary BNF grammar rules?

Improve this question

3 Answers 3

Reset to default
7

On this site, I would expect that this question is about linguistically meaningful examples of syntactic structures that cannot be represented by BNF.

A first minor point is that BNF is a programmer/compiler oriented syntax (introduced with the programming language Algol 60) for representing what should rather be called more abstractedly context-free grammar (CFG).

The adequacy of context-free grammars for representing the syntax of natural languages has been addressed by many people in different way.

It should be also noted that we are mostly talking of a syntactic infrastructure, based on formal language theory, since linguist often consider as part of syntax various attribute and features that can be associated with this syntactic infrastructure.

The most frequently given example of syntactic structure that cannot be represented by a CF grammar is apparently the cross-serial dependency represented in the following diagram.

cross-serial dependency diagram (source wikipedia)

Such a syntactic structure is found in some languages, including Dutch and Swiss-German. Here is a Swiss-German example from Stuart Shieber:

                             _____________________
             _______________|______________       |
            |               |              |      |
...mer  em Hans     es    huus          hälfed  aastriiche.
...we   Hans (dat)  the   house (acc)   helped  paint.

That is, "we helped Hans paint the house."

Now there are to ways in which context-freeness of a language may be analyzed:

  • strong context-freeness: can this language be generated by a CF grammar so that the parse-tree structure conforms the syntactic relations between the parts of speech?

  • weak context-freeness: can the language be analyzed by a CF grammar at all? However, if the language is not strongly context-free, the structure of the parse-trees will not reflect the proper syntactic organization of a parsed sentence. But then, it is usually possible to retrieve it by other means, once the parsing is done.

It has been observed since around 1982 that cross-serial dependency is not strongly context-free, which is rather obvious. But there was some debate regarding weak context-freeness of languages with cross-serial dependency. The usual example was cross-serial dependency in Dutch, but there were arguments to show that Dutch was still weakly context-free.

In 1985, Stuart Shieber used the case of Swiss-German cross-serial dependency as evidence of a weakly non-context-free natural language. He used explicit case marking of the language and case based ordering rules for subordinate clauses to show that (the cross-serial part of) the language is weakly context-free only if the language of strings of the form {w a^m b^n x c^m d^n y | n,m >0} where a, b, c and d are symbols, w,x,y are strings not including these symbols, and a^m means a repeated m times.

But this language is known to be weakly non-context-free, as can easily be shown with the pumping lemma.

However, cross-serial dependency can be handled, in the strong structural sense, by a slightly more complex formalism, the tree-adjoining grammars.

There is actually a detailed account of this topic (which I found after writing this answer) written by Johan Behrenfeldt as his MS thesis in 2009.

Additional note:

Other candidates for non-context-freeness are the free word order languages. It is not a type of syntax I know well, but I think it should be mentioned. This case is complicated by the fact that some languages have partially free word order.

Though there has been significant work to encode free word order into the context-free framework, one may wonder whether it is always really meaningful structurally. The point is that full free word order amounts to considering strings as unordered sets of words. This implies a much greater combinatorics for associating the words, potentially giving rise to exponential algorithms rather polynomial ones, as is the case for context-free parsing, which is cubic. This can be dealt with by using other information in the parts of speech (morphological marking), through different kinds of algorithms with tractable complexity, and some have been proposed (see 4th reference).

Of course, if there are no constraints on word order (or limited ones), the language may well be regular, hence weakly context-free. But, in this case, there is little hope to use information from the context-free parsing (there is none for a regular grammar) to recreate a syntactic structure for the sentence being analyzed. Weak context-freeness does not help.

References:

Improve this answer
2
5

BNF is a Type-2 language in the Chomsky Hierarchy. A context free grammar has rules of the type:

A -> B C

but not rules of the type:

x A y -> x B C y

i.e., what happens with A depends on what comes before or after A (A's context).

Wikipedia has a Type-1 example which I don't know how to write here. [Feel free to edit this post.]

Thue is a Type-0 language which also cannot be represented in BNF.

As a realistic example, many natural languages require that the formal grammar used to analyse them be Mildly context-sensitive.

Improve this answer
1

Remember that the intersection of the outputs of two context-free languages is not necessarily context free. So (a raised to power x) (b ... x) (c ... y) intersected with (a ... z) (b ... x) (c ... x) produces (a ... x) (b ... x) (c ... x) because of the identity relation of the two b expressions, a result that is context-sensitive. (Sorry I can't write it in standard mathematical notation.)

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.