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

Main Page | Report this Page

Computers Forum Index » Computer Compilers » Can syntax be enough? No need of semantics....

Page 1 of 1

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

Author

Message

Srinu...

Posted: Mon Sep 14, 2009 5:01 am

Guest

Dear All,

Can we have a language/grammar, which doesn't need any semantics
checking for it to be able to correctly interpreted by its compiler? I
mean, if some statement of this language/grammar satisfies the syntax
of the grammar, then it is a perfect statement and a compiler can
perform right things according to what the statement specifies.
Compiler shall not need semantics checking. Idea is to remove
semantics checking phase from a compiler.

Can this be possible?

If not, where can we face problem?

Thanks and regards,
Srinivas.
[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]

Quinn Tyler Jackson...

Posted: Fri Sep 18, 2009 8:36 pm

Guest

Srinivas asked:

Quote:

Can we have a language/grammar, which doesn't need any semantics
checking for it to be able to correctly interpreted by its compiler? I
mean, if some statement of this language/grammar satisfies the syntax
of the grammar, then it is a perfect statement and a compiler can
perform right things according to what the statement specifies.
Compiler shall not need semantics checking. Idea is to remove
semantics checking phase from a compiler.

Can this be possible?

Our moderator noted:

Quote:

[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]

To which I reply:

It is entirely possible to put semantic checks into a grammar and
thereby avoid ad hockery.* I have a grammar that does what John is
talking about for a lab-language created for the purpose of
demonstrating variable declaration and type checking. I have also
demonstrated the grammar structures necessary for a more subtle case:
member variables in C++ classes can be declared *after* they are
referenced in inline member function blocks. In fact, doing as much as
possible in a grammar (rather than in attached semantic code) has been
one of my Holy Grails for some time. (The correct grammar-only
processing of C++, for instance.) Another example is the Perl grammar.

Language theorists will immediately recognize that this cannot be done
by Type 2 constructs. The kinds of semantic checking being discussed
*can* be handled by a Type 0 system, however, and the state of the art
in generally available parsing engines is a very small subset of Type
1, if even that.

Many of these things are discussed in my book (Adapting to Babel) ad
nauseam with the charts, examples, experimental results, et cetera.

Quinn Tyler Jackson

* Where here "ad hockery" is defined as "doing in code rather than in
the grammar."

Andy Walker...

Posted: Fri Sep 18, 2009 9:01 pm

Guest

Our moderator wrote:

Quote:

[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]

Never seen a reasonable two-level grammar? Fi!

Whether it's sensible to handle semantics that way is another
matter, just as we have to ask whether to recognise identifiers via
the formal grammar or via special code in a lexer.

--
Andy Walker
Nottingham
[Good point. So why don't we use them? -John]

Anton Ertl...

Posted: Fri Sep 18, 2009 10:17 pm

Guest

Srinu <sinu.nayak2001 at (no spam) gmail.com> writes:

Quote:

That's just a question of what you see as syntax and what as "static
semantics". The current mainstream is to consider things described by
a context-free grammar as syntax and anything beyond that that has to
be statically checked as static semantics. But you can just as well
say that anything checked at compile time is syntax.

Quote:

Compiler shall not need semantics checking.

For the regular scanner and the context-free parser it is quite
popular to use a generator, whereas the rest is typically written in a
general-purpose programming language. Even if the scanner and/or
parser are written by hand, they are still often conceptually using a
specific formalism (e.g., context-free grammar as specification) and
implementation methodology (e.g., recursive-descent) that sets it
apart from the rest. That also seems to be useful for organizing the
compiler (e.g., syntax-directed compilation).

You can use some formalism for something more powerful than
context-free grammars to define all of the statically checkable parts
of a programming language, e.g., a Van Wijngaarden grammar. However,
that particular formalism has not caught on for specifying programming
languages and even less for compilers.

- anton
--
M. Anton Ertl
anton at (no spam) mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

Andy Walker...

Posted: Sat Sep 19, 2009 4:36 am

Guest

I wrote:

Quote:

Never seen a reasonable two-level grammar? Fi!
[Good point. So why don't we use them? -John]

Good question. Some answers:

(a) We don't know how to parse them. So we have first to convert
them into simpler grammars, which somewhat defeats the point.

(b) It's hard work to write one. People who invent languages seem
to prefer to specify an EBNF grammar, or similar, and then add
the semantics by saying in natural language what the rules are.
The result is that no-one knows what C, for example, really is,
as there is no adequately formal specification. Not since the
days when the formal spec was DMR's compiler.

(c) Fear.

--
Andy Walker
Nottingham

Tony Finch...

Posted: Mon Sep 21, 2009 6:58 pm

Guest

anton at (no spam) mips.complang.tuwien.ac.at (Anton Ertl) wrote:

Quote:

You can use some formalism for something more powerful than
context-free grammars to define all of the statically checkable parts
of a programming language, e.g., a Van Wijngaarden grammar. However,
that particular formalism has not caught on for specifying programming
languages and even less for compilers.

Our moderator annotated another post in this thread with:

Quote:

[Good point. So why don't we use them? -John]

The particular problem with VW grammars is that they require quite a
lot of low-level machinery to express basic ideas. The grammar ends up
being an obscure implementation rather than a concise specification.

Tony.
--
f.anthony.n.finch <dot at (no spam) dotat.at> http://dotat.at/

Torben Ægidius Mogensen...

Posted: Wed Sep 23, 2009 1:39 pm

Guest

Srinu <sinu.nayak2001 at (no spam) gmail.com> writes:

Quote:

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.

Quote:

[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

gopi...

Posted: Fri Sep 25, 2009 4:15 am

Guest

Quote:

I would think the answer is yes (to some degree). If you see untyped
languages or dynamically typed languages, their grammars and parsers
are quite simple and need almost no semantic checking. Also, most
declarative languages (including XML to some extent) fall under this
category. Even functional languages like lisp can be parsed quite well
using a really simple grammar.

Of course many such languages shift the paradigm to do more checking
at run-time, which is more of an "existential" check than a "semantic"
one.

Having said that, the key point is -- is it possible to make mistakes
when creating a sentence / program ? Can those mistakes be identified
early on by the parser or compiler ? Compiler design with semantic
checking is addressing these issues. Eliminating the need for checking
semantics is not going to take away the mistakes.

Generally speaking a better solution is to try and automate the
generation of procedural / OO programs from higher level declarative
programs. This gives the twin benefits of reduced complexity while
reusing the capabilities of existing powerful languages for modeling
behavior / function. Meta-Model driven tools take this a step forward
eliminating the need for generating programs and directly work at
runtime with external model files.

Gopi Kumar Bulusu
Chief Executive Officer

Sankhya Technologies Private Limited
http://www.sankhya.com

India Mobile : +91 94408 78042
US (Voice-Mail) : (408) 556-9757
Skype : gopibulusu
India Office : +91 44 2822 7358

gopi...

Posted: Fri Sep 25, 2009 4:18 am

Guest

On Sep 23, 2:39 pm, torb... at (no spam) pc-003.diku.dk (Torben Fgidius Mogensen)
wrote:

Quote:

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.

And such grammars can be implemented using tools like STF using STML
(SANKHYA Translation Modeling Language) without the need for any
programming (other than describing the rules in STML).

Thanks,
gopi

Gopi Kumar Bulusu
Chief Executive Officer

Sankhya Technologies Private Limited
http://www.sankhya.com

India Mobile : +91 94408 78042
US (Voice-Mail) : (408) 556-9757
Skype : gopibulusu
India Office : +91 44 2822 7358

<a href="http://www.sankhya.com/info/products/teraptor/teraptor.html
"> SANKHYA
Teraptor - When Performance Matters </a>

Srinu...

Posted: Tue Sep 29, 2009 12:21 pm

Guest

On Sep 18, 11:17 pm, an... at (no spam) mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

Quote:

I agree to this.

So, basically the answer is, "it is possible".

Thanks a lot.

Srinu

Page 1 of 1

All times are GMT The time now is Thu Nov 26, 2009 6:30 pm Computers Forum Index