Sufficiently Small

Since BBC BASIC does not use C-like nested scopes marked by braces to delineate loops and other blocks, the structure of such blocks is not captured in the Abstract Syntax Tree (AST); that is to say that the statements within a loop will not be child nodes of the opening loop statement such as FOR or WHILE. Furthermore, there is not necessarily a one-to-one correspondence between loop entry points such as FOR, and loop ends such as NEXT – a FOR loop may contain more than one NEXT statement, and what is more, in convoluted cases involving GOTOs, a single NEXT statement may be re-used by several FOR loops. Next please! Compiling Iteration Structures in BBC BASIC for more information.

It is therefore required to pair each closing loop statement (e.g. NEXT or ENDWHILE) with its corresponding opening loop statement(s), and this is turn requires that the possible paths of execution through the program can be determined statically (i.e. at compile time) so that for each closing statement we can trace backwards through the program execution to the previous opening statement. This also makes it possible to identify illegal constructs, such as ending a WHILE loop with a NEXT statement.

To achieve this, we must build a data structure called the Control Flow Graph (CFG). For each statement in the AST we determine all possible following statement. Ordinarily this is simply the next statement in the program, but we must also resolve line number references in GOTO, GOSUB, etc. and at each IF statement control flow may go in either of two directions. We do not resolve function or procedure calls when building the CFG, so each function or procedure becomes a separate connected-component in the resulting graph.

I’ve been working with the code to Acornsoft’s Sphinx Adventure from 1982 as a real-world BBC BASIC test program for the BBC Micro.

I don’t know who the author is, but I’m willing to bet they never imagined their by now long-forgotten code would undergo the sort of analysis its about to receive! Maybe the code in Sphinx Adventure is intentionally obfuscated, or maybe its just badly written, but some of the non-structured programming techniques such as jumping out of the middle of procedures never to return, are ‘interesting’ to say the least.

Each node in this image is a single statement in the program, and the arrows between the nodes indicate the program flow. Each connected group of nodes is a separate procedure, and the largest group of nodes to the top-left of the chart is the main program starting from the first line through a long trail of DATA statements.

The Sphinx.graphml is browsable with yEd, which was also used to produce these diagrams.

Zooming in, we can see the CFG for a single procedure – in this case PROCF,

462 DEF PROCF(W): IFW=28 THEN PROCR(21): GOTO465
463 IFO?W <> L  ANDO?W <> 1 THEN PROCR(7): PRINTA2$;" here.": GOTO465 ELSE IFO?W2 <> 1 THEN PROCR(8): PRINTA2$;".": GOTO465
464 IFW=27 ANDL=O?28 ANDWA=0 THEN PRINT"Your bottle is now full of water.":WA=1 ELSE IFW=27 ANDL=O?28 THEN PRINT"your bottle is already full." ELSE PROCR(21)
465 ENDPROC

The label in each node indicates its logical line number in the original code and the type of statement the node represents at the abstract syntax level.

Now we have the basic CFGs we can analyse them to match up corresponding loop statements, and optionally perform optimizations such as moving invariant code out of loops and eliminating dead (unreachable) code fragments.