Determining the last statement exercise

On Thu, 5 Nov 2009 at 10:15:56, in comp.lang.javascript, VK wrote:

Csaba Gabor wrote:
Let's consider this same question in the PHP world,
where it is easier to handle. In PHP land, all statements
except the last one must end with ; or }.

It doesn't matter because Rice's Theorem doesn't depend on a formal
language syntax. The only thing that matters is if it's a general
purpose higher level programming language (skipping for now on exact
formal definitions of these terms).
snip

It doesn't have to be a high-level language. It can be a Turing machine,
and you can't get any lower-level than that.

Rice's theorem is about testing a function to see if it meets its
specification. That's not what's wanted here.

For a general case finding the right place for the return statement
means to algorithmically decide for an arbitrary program with an
arbitrary input if it has a return point and then to find that
intended return point of it, so, unlike Harris claimed, it is
necessary to prove that the halting problem is decidable

Read the question. The OP wants to find the last part of the submitted
code and make it a return statement if it's an expression. It doesn't
matter in the least if execution never reaches that last part : he isn't
interested.

and
consecutively to resolve the Entscheidungsproblem.

That's the problem of proving that a well formed formula is/isn't a
theorem, given a logic language and a set of axioms. It can be solved
for some, relatively simple, languages but not in general.

Another option is
to write a program that successfully passes the Turing test so having
all qualities of a free-will human identity.
I guess that either of these three tasks from above is way beyond the
humble frames of clj. The future Nobel laureate should post such
solution in a serious scientific preprint journals right away

They don't award Nobel Prizes for mathematics.

John
--
John Harris

On Nov 3, 4:21*pm, Csaba Gabor <dans... (AT) gmail (DOT) com> wrote:

Suppose you have some javascript statements in a string.
Can you determine whether the entire string is syntactically
valid, and if so, the starting position of the last statement?
In other words,

function lastStatementPos(code) {
* // returns the starting position within code of the last
* // javascript statement, and -1 if code is not syntactiaclly
* // valid.

This came up in a different context today, and I thought
it would make an interesting exercise.

*Csaba Gabor from Vienna

My solution for determining the (position of) the
last javascript statement runs along the lines outlined
in my Nov. 5 response to Lasse's first post at
http://groups.google.com/group/comp.lang.javascript/browse_frm/thread/91262ad01ca356bc/
and also in my response to VK within this thread:
http://groups.google.com/group/comp.lang.javascript/browse_frm/thread/2aa9a60623eb5883/

In the below, the term inject will mean to insert
code at a given point within a larger block of code
and to have it be syntactically valid.

Unless I'm forgetting some cases, javascript statements
end with either ; or } or a newline. The idea will
be to go backwards (KSB = keep searching backwards)
through each viable one of these characters (call the
current character being checked cP). See the
description of KSB below for determining the next
previous viable terminating character) and make 9
checks to decide whether or not we have a last
statement:

1. First, we determine that the character after cP
is not part of a comment (or in other "inert" code
such as a string or regular expression) by injection
of non compiling code. If it's an inert position,
then KSB

2. Find the next non whitespace character, call it
chNext. If chNext is a semicolon or any closing
delimiter such as ], ), or } then we don't actually
have a statement (or it's empty) so KSB

3. If we can not inject an empty loop at this point
(and have the result be syntactically correct), then
then cP does not represent an end of statement, so KSB

4. Starting with cP, find the first non whitespace
character going backwards, call it chPrev, If chPrev
is a semicolon or closing curly brace then we are done,
since those will mark the end of a statement. But
see the description of KSB below for why we don't have
to worry about embeddings.

5. If we can inject a "break; " at this point,
we're in a loop, so KSB.

6. If we can inject an " else; if (x) " at this point,
then we're in an if, so KSB.

7. If the final part of the code through chPrev is
an else, then we're in an if statement, so KSB.

8. If chNext is the first character of an autoincrement
or an autodecrement (++ or --) then it is independent
of the previous statement (since we passed point 3),
so we are done.

9. If chNext is not one of the five
characters +, -, (, [, or / then we are likewise done.
Otherwise, KSB. The other characters are not ambiguous
in their desire to connect to a previous item (such
as .), but those five are. However, if we have gotten
here, and one of those characters appears, then the
prior portion of code is an expression and chNext will
be connected to it. KSB

KSB. To finish off the algorithm description, some
words on determining the prior newline, semicolon,
or right curly brace: If a right curly brace is
encountered, then anything within it cannot be a
last statement. Therefore, in that situation, find
the corresponding opening brace, and continue the
search backwards from there. Finding the matching
(opening) brace is straightforward because one just
searches backwards replacing the text starting from
each candidate opening brace till the closing one
with {x} or {x:y}, and then apply checkSyntax. The
first opening brace to pass such a syntax check is
the matching one. While this does not guarantee
that we will be at the top level (eg. if / nested
loops), at least be can be sure that we are not
embedded within {...}


I have implemented the above description into
working code, though there are some parts still
unexercised. Since this is already a long post, I
won't make it longer by posting the actual code.
However, one can piggyback off this to break up a
piece of code into all its component statements,
even within loops, conditionals, and blocks. That,
however, is a bit trickier since one can't simply
recurse with lastStatementPos at the lower levels,
because the code within a block won't necessarily
pass a syntax check (eg. if you try to work with:
{ var foo=7;
break; }
without including the relevant loop, checkSyntax
will be displeased (ie. it won't pass a syntax
check). try/catch also require a bit of care.


In any case, direct syntax parsing is more
efficient, but the method outlined here and in
removeTrailingComments, that of using javascript's
own syntax checking upon injection of a judicious
code snippet is sometimes far simpler than having
to write a parser from scratch. For example,
the method is easily adapted to removing all
comments from a given block of code. In addition,
it also solves the problem of injecting a return,
when possible, before the last statement under
either of the two possible definitions mentioned
(since if the final statement is a block, one can
just recurse into it).

Csaba Gabor from Vienna

Csaba Gabor wrote:

On Nov 3, 4:21 pm, Csaba Gabor <dans... (AT) gmail (DOT) com> wrote:
Suppose you have some javascript statements in a string.
Can you determine whether the entire string is syntactically
valid, and if so, the starting position of the last statement?
In other words,

function lastStatementPos(code) {
// returns the starting position within code of the last
// javascript statement, and -1 if code is not syntactiaclly
// valid.

This came up in a different context today, and I thought
it would make an interesting exercise.

Csaba Gabor from Vienna

My solution for determining the (position of) the
last javascript statement runs along the lines outlined
in my Nov. 5 response to Lasse's first post at
http://groups.google.com/group/comp.lang.javascript/browse_frm/thread/91262ad01ca356bc/
and also in my response to VK within this thread:
http://groups.google.com/group/comp.lang.javascript/browse_frm/thread/2aa9a60623eb5883/

In the below, the term inject will mean to insert
code at a given point within a larger block of code
and to have it be syntactically valid.

Unless I'm forgetting some cases, javascript statements
end with either ; or } or a newline. The idea will

Don't forget that it's LineTerminator production (see 7.3), not just
newline.

[...]

--
kangax