Re: Interpreted Basic control-flow analysis

On Thu, 6 Jul 2006, Hans-Peter Diettrich wrote:
> "Arthur J. O'Dwyer" wrote:
>> 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.
[...]


      FWIW, my problem has been solved to my satisfaction after some
discussion on comp.programming; the best solution so far, and the
one I've adopted, is basically "run through the program in the
analyzer, stopping whenever you repeat a state," exploiting the
fact that a PC has way more memory than a TI-83 and runs way
faster. :) See comp.programming for details.


      But since Hans-Peter asked a few direct questions, for the record,
here are my answers:


>> 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!
>
> Please specify: do you describe the operation of your analyzer, or the
> operation of the original interpreter?


      I was describing the (original) interpreter. Of course, the analyzer
has to have the same "idea" of the language as the interpreter, or else
we'd end up with "misunderstood" programs, and that would be bad.


>> The runtime nesting of control structures isn't
>> necessarily reflected by a lexical nesting.
>
> How that?


      As John editorialized, yes, this Basic is totally interpreted.
So there might be a lexical nesting, or there might not. See the
examples I provided in my first message, or consider this real-world
case I should have mentioned but didn't:


          While 1
              (get some user input)
              (act on it)
              If (no more action required):End
              (do more action)
          End


The first "End" acts like a jump back to the top of the loop if
(no more action required). But if (more action required), then
that line is skipped, and we (do more action) before hitting the
"real" end of the While loop.




> IMO the trouble only arises from your misinterpretation of the
> successor of the END of a WHILE loop.


      Your O is mistaken, then. :) But I do think it's amusing that
practically everyone who responded in comp.programming also
commented on my wrong-headed labeling of the lines, and gave me
their relabelings... all different from one another!




> IMO chances for hitting really structured code are almost the same, for
> a BASIC language with unrestricted GOTOs, and for assembly language.


      I'm not sure I can parse that comment, but if you're saying that
this Basic language is about as unstructured as assembly language,
you're not being forceful enough. :) The "End" weirdness, and a couple
more quirks I haven't mentioned, make it even less comprehensible
than the knottiest assembly code!


      Gratuitous example:


              If A
              If B
              C


"C" is executed whenever (A is not true) or (B is true), because if
A is not true, then the line following "If A" is skipped. :)




> I'd suggest you study the documentation around the dcc (C decompiler) by
> Cristina Çifuentes, for techniques in handling and reduction of regular
> and irregular control flow graphs. (Universities of Tasmania and
> Queensland, ~1995)


      It certainly looks interesting, albeit much more complicated and
ambitious a program than the one I'm trying to make. I'll read about
it anyway.


-Arthur

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