Re: Can syntax be enough? No need of semantics.

Srinu <sinu.nayak2001@gmail.com> writes:


> Can we have a language/grammar, which doesn't need any semantics
> checking for it to be able to correctly interpreted by its compiler?


It depends on the language in question. A sufficiently simple language
can have the legal-program property expressed entirely in a CF grammar.
The language of regular expressions is an example, as is the language of
SKI combinators.


> [I've never seen a grammar that could handle in a reasonable checks
> that variables are declared before use, and that types of subexpressions
> match. -John]


If you have dynamic binding and dynamic typing, you can not statically
check programs anyway, so the property of being a legal program is
basically just a parsing problem. Variables being used before
definition and mismatched types are "just" run-time errors. Classic
LISP and Prolog are examples of languages where CF parsing is the only
static verification.


If we want to statically eliminate all possibility of run-time errors,
the problem is much harder, though, unless we simplify the language so
no run-time errors are possible. A "pure" Prolog (with no arithmetic)
can be said to be of this category: Variables are created as they are
used (standard Prolog behaviour) and undefined predicates just always
fail (which is not a run-time error -- failure is a valid response).


As for static type checking, this can be specified as logical rules
using environments for variables, like the rules below for simply typed
lambda calculus:


        T(x) = t
      ----------
      T |- x : t


      T |- m : s->t, T |- n : s
      --------------------------
                t |- m n : t


      T[x:s] |- n : t
      ----------------
      T |- \x.n : s->t




The rules describe both syntax (though ambiguously) and types. You can
call the rules a grammar (though not context free). Here, there is only
one (unnamed) "nonterminal", but you can annotate the turnstile (|-)
symbol with nonterminals to describe more complex langauges.


The notation is widely used to specify both static and dynamic semantics
of langauges.


Torben

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