Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Syntax and Semantics
Context-free languages are a rich class of languages with important applications
in the theory of practice of programming languages. However, not all languages
are context-free. For example, although the language
{ w rev(w) | w a string of a's and b's }
is context-free, the language
{ ww | w a string of a's and b's }
is not. This lecture deals with the following question:
How do we show that a language is not
context-free?
The mere fact that we might be unable to construct a PDA that
recognizes a language L does not constitute a proof of the
non-context-freeness of that language. One way to argue that
L is not context-free is to isolate a characteristic property
enjoyed by all the context-free languages, but not by L. The
so-called pumping lemma for context-free languages gives one
such property. Using the property described in the statement of the
pumping lemma, we can now formally show that many languages are not
context-free.
In particular, not all of the syntax of many programming languages can
be described using context-free grammars. For example, using
context-free grammars it is impossible to describe that variables
should be declared before they are used in a program.