Summary: 'C', is it's grammar context sensitive ?
Alexander Vrchoticky
alex at vmars.tuwien.ac.at
Sat Sep 1 00:29:58 AEST 1990
ramsey at NCoast.ORG (Cedric Ramsey) writes:
>If you guys agree that 'C' is context sensitive then what languages
>truely are context-free, if any.
Uh, almost none, or almost every. It depends on your view.
I won't go into the details of formal language theory here,
but clarify a few points:
- Efficient syntax analysis of programming languages dictates the use
of context free grammars for syntax specification.
- From a formal language point of view no practical programming language
is context-free. (It can't be context free if it allows for an
unlimited number of identifiers that can appear three or more
times in a program.)
The apparent contradiction is usually resolved as follows:
- Build a parser based on a context free grammar that generates a
`reasonably small' superset of the language and use other techniques
(symbol tables) to `filter out' the cases that are illegal in the
language but which slip through the parser based on the superset.
The phrase `reasonably small' is not really very well-defined.
However I think few people would call the following a reasonable grammar
for C, even though it generates a superset of C:
S --> A S | \epsilon
A --> 'a' | 'b' | ... | 'z' (and the uppercase letters, and the digits, and ...)
On the other hand most people are very happy with mapping all possible
identifiers into one token with the use of a lexical analyzer and
using table lookup to check for things like proper declarations.
This is done routinely in every compiler.
Fewer people are happy with the fact that two different tokens in the
C language (identifier and typedef-name) have the same lexical representation
and can therefore not be told apart without resorting to table lookup.
But that's the way C is defined.
And to answer the original question: Most (all?) newer languages have
avoided the problem by a somewhat more generous use of keywords.
--
Alexander Vrchoticky Technical University Vienna, Dept. for Real-Time Systems
Voice: +43/222/58801-8168 Fax: +43/222/569149
e-mail: alex at vmars.tuwien.ac.at or vmars!alex at relay.eu.net (Don't use 'r'!)
More information about the Comp.lang.c
mailing list