Re: Interpreted Basic control-flow analysis
- From: "Roger Willcocks" <roger@xxxxxxxx>
- Date: Mon, 3 Jul 2006 21:56:06 +0100
"Arthur J. O'Dwyer" <ajonospam@xxxxxxxxxxxxxx> wrote in message
news:Pine.LNX.4.60-041.0607031436160.2674@xxxxxxxxxxxxxxxxxxxxxxxx
[multi-posted to moderated comp.compilers, unmoderated comp.programming]
I have an apparently non-trivial problem in control-flow analysis.
I'm trying to make a static control-flow analyzer for programs written
in TI-83 Basic, an interpreted language. The input is a Basic program,
line by line; and the output is a mapping from lines to lists of their
successors. (See example below.)
The important control structures supported by TI-83 Basic are
If-Then-Else-End, While-End, and Goto-Label.
At runtime, the interpreter maintains a stack of all the currently
enclosing control structures. A new entry is pushed when encountering
If-Then or While, and popped when encountering End. Notice that Goto
does not affect the state of the control stack --- this is the crux
of the problem! The runtime nesting of control structures isn't
necessarily reflected by a lexical nesting.
The successors of If-Then, Else, While, and Goto are always
lexically determined[1] and thus easy to compute. The successors of
"End" are what I'm having trouble with.
Consider the following trivial example, in which the lexical nesting
does reflect the runtime semantics:
1. If X successors are 2
2. Then " 3, 8
3. While Y " 4, 6
4. A " 5
5. End " 4, 6
6. B " 7
7. End " 8
8. C " none
The successors for line 5 should be 3 and 6 since the While needs to be
reevaluated. I'll use this numbering below.
Now consider the following example, in which the lexical nesting
doesn't quite match the runtime behavior:
1. While X " 2, 4
2. Goto L " 6
3. End " unreached
4. While Y " 5, 7
5. Lbl L " 6
6. End " 2, 5
The "End" in line 6 corresponds to "While X" if it was reached
via line 2 ("Goto L"), but it corresponds to "While Y" if it was
reached via line 4 (which is where control ends up if X is false
the first time line 1 is reached).
I'm looking for an algorithm that can handle this kind of language.
It sounds like you need the fabled 'come from' instruction. The successors
for the End on line 6 will be line 4 plus the top of the return stack at
each Goto which could arrive at line 5.
But you also need to carry the whole call stack forward (and possibly
several in parallel if there are multiple come froms for line 5) since line
7 could be an End too.
Since you're only after successors, I don't think you need to add a line to
a call stack if it's already on the stack, which deals with recursion, but
that means that every End needs to have 'all the entries on all the call
stacks that could be active at that line' in its successor list since you
can't pair up stack entries and Ends.
To do otherwise would require running the program. And you cannot in general
know whether it will complete.
--
Roger
.
- References:
- Interpreted Basic control-flow analysis
- From: Arthur J. O'Dwyer
- Interpreted Basic control-flow analysis
- Prev by Date: Re: Deleting substrings
- Next by Date: Re: Deleting substrings
- Previous by thread: Re: Interpreted Basic control-flow analysis
- Next by thread: Re: Interpreted Basic control-flow analysis
- Index(es):
Relevant Pages
|
