Re: context sensitive parsing

In article <564@ima.UUCP>, dowding@bigburd.PRC.Unisys.COM (John Dowding) writes:
> I think that the use of term context-free and context-sensitive
> are misleading here. Most programming languages have context-sensitive
> restrictions, but they are handled in the semantics, not the syntax.
> As the semantic actions are generally arbitrarily powerful, they can
> certainly do context-sensitive checking.
> An example of this is the constraint in some languages that a function
> be defined before it is called. This can not be checked for by
> a context-free grammar.


Syntax is to do with structure and can be checked by static
analysis of the program. We can then distinguish context free syntax
which is to do with raw structure from context sensitive syntax which
is to do with consistency within raw structure. We can also distinguish
concrete syntax which is to do with representation from abstract syntax
which is to do with meaningful structure. Semantics is to do with meaning
alone. In Chomsky terms: lexicon = type 3 grammar
                                                  context free syntax = type 2 grammar
                                                  context sensitive syntax = type 1 grammar
                                                  semantics = type 0 grammar


                                                  concrete syntax = surface structure
                                                  abstract syntax = deep structure


This confusion originates from the early days of syntax directed translation.
The term 'static semantics' used to be applied to context sensitive syntax
because it couldn't be handled by a context free approach and people thought
that all that was needed for parsing was a context free grammar. Thus,
anything else must be semantics! Furthermore, in denotational semantics,
details like context sensitivity are deemed irrelevant and so get pushed
into the semantic equations. That doesn't make them semantics though!


Nowadays, attribute grammars are used to specify context sensitivity and
to enable context sensitive checking in compilers. See articles by Knuth,
& Watt. See McGettrick's & Pagan's books on language definition.
[It's always been my impression that the distinction between syntax and
semantics degenerates into religion pretty quickly. Practically any aspect
of a language could be argued to be either. In useful compilers, though, it
seems that you're better off having your parser recognize an overgeneral
version of your language, and then throwing out invalid cases later; it makes
it a lot easier to produce useful error messages, e.g. "this should have been
a pointer but it's not" rather than "invalid token after `*'". -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.