Talk:Context-free grammar

Contents

1 Decidability 2 Syntax or semantics 3 Phrase structure grammars 4 Natural languages

Decidability

It is not possible to construct a general algorithm which takes as input two context-free grammars and decides whether the two grammars generate the same language; nor is it decidable whether their languages have a single string in common. It is however possible to decide whether a given context-free grammar generates a non-empty language or not, and it is also possible to decide algorithmically whether a given context-free grammar generates an infinite language or not.

Is it possible to decide whether given context-free grammar is equivalent to given regular grammar ? In particular is it possible to decide whethere there is single string that doesn't belong to context-free language (that is, whether or not is it equivalent to .*) ? Taw 14:41 Apr 6, 2003 (UTC)

The answer for your first question is Pumping lemma. -- Sundar 05:08, Feb 15, 2005 (UTC)

Syntax or semantics

Context-free grammars are important because they are powerful enough to describe the syntax of programming languages

(Well...context-free grammars can describe most of the syntax of programming languages. For example, any programming language that requires that variables be declared before use is not fully describable via a context-free grammar, essentially because there can be arbitrary amounts of source code between declaration and use--see the reference to the "pumping lemma" below. Such constraints are typically swept over into the corner, labelled "semantics," and dealt with outside of the parser mechanism proper. In the example, "semantic action" code is attached to the grammar rule that recognizes identifiers to check against a symbol table.) --24.36.158.101

Right, the requirement to declare before use is called "semantics" rather than "syntax", so the sentence in the article is correct: the syntax of programming languages is describable by context-free grammars. --LC

Not exactly - it's debatable whether "declare-before-use" is really "syntax" or "semantics". In C and C++, for example, it's impossible to check whether a source file is syntactically correct without building a symbol table while parsing that can at least distinguish between typedef'd and "regular" identifiers. The syntax of C and C++ critically depends on the distinction betwen those two forms of identifiers, which depends on what you're calling semantic information. In addition, there's plenty of other such stuff in various languages that's usually "swept into the corner" but is unquestionably syntax. For example: the ad hoc precedence rules built into parser generators to resolve dangling else and similar conflicts; the whole "longest match" convention that is built into lexical analyzers; the layout mechanisms of many more recent languages such as ML, Haskell, and Python. Then there's the fact that the C++ grammar has ambiguities that cannot be resolved by any finite amount of lookahead, and so the C++ standard simply states ad hoc disambiguation rules which implementors have to follow by making the parser capable of looking ahead an arbitrary distance in certain situations. As far as I can tell, practical languages that really follow a "pure" context-free syntactic paradigm are rather few and far between. Brynosaurus 15:00, 13 Aug 2004 (UTC)

It's my understanding that because of these facts C, C++, and the other languages do not have context-free grammars. A context-free grammar is an ideal for a computer programming language which is seldom achieved - basically because many things which are very useful for programming languages are not possible in a context-free grammar.

This is the strict sense of "context-free" grammar. When programmers think about "grammar", "syntax", and "semantics" they usually have much looser usage of these terms. — Hippietrail 02:13, 14 Aug 2004 (UTC)

Quite so. It is certainly almost universal practice to use BNF notation informally as a method of concisely describing or suggesting the general, overall structure of a language's syntax. But it is almost never the case that these BNF notations actually formally specify the syntax of the language by themselves. Brynosaurus 06:18, 14 Aug 2004 (UTC)

Phrase structure grammars

PSG isn't a precise term. CFGs are definitely PSGs, but there are also CSGs (context-sensitive grammars), for example, which could also be described as PSGs. The redirect seems sensible enough to me for the moment, since it's hard to imagine that an article on PSGs could be written which didn't just duplicate material in Context-free grammar and Chomsky hierarchy. I agree though, that the redirect is misleading. Perhaps it would be better to have a stub with links to Context-free grammar and Chomsky hierarchy? Cadr 23:11, 14 Feb 2005 (UTC)

It ought to be a stub if they are not equivalent.Otherwise it is misleading. -- Sundar 05:08, Feb 15, 2005 (UTC)

Natural languages

It would be nice to include some statement about whether natural languages are context-free in this article. On this topic, the article Bambara language has the following note:

In mathematical linguistics Bambara is regarded with interest, since for only very few languages it was possible to show that they were not context-free. For Zurich German and Dutch the proof is based on sentence construction, whereas the proof for Bambara is based on word construction.

I wonder what is statement is really supposed to say, because I find it a bit difficult to believe. Can it really be so hard to find an example showing that English is not context-free? --Saforrest 12:37, Apr 19, 2005 (UTC)