An abstract syntax tree (AST) such as the above can be generated by customizing the tree building process. The EBNF grammar looks as follows:
instructions = <start_instructions> {instruction <add_instruction>}
When the parser reaches the first annotation, it calls routine Build_start_instruction, which creates a node labeled `instructions' and pushes it onto the parse stack. Next an instruction is parsed and a corresponding AST ends up on the parse stack. The parser then reaches the <add_instruction> annotation which causes routine Build_add_instruction to be called. This pops the instruction AST off the stack and adds it as a child of the node created by Build_start_instructions. When the end of a sequence of instructions is reached, the parse stack contains an AST such as the one depicted above. Build_add_instruction can take further actions such as adding line number information to the AST.
When this tree is finally walked, the routine Walk_instructions is called with a list of ASTs corresponding to the sequence of instructions. This list can then be translated into a string representing the instruction sequence in the target language, or it can be directly interpreted, or it can be partially evaluated.
Walk_instructions becomes a bit more complicated when the language includes gotos. This is discussed in the sections on loop exits, function/procedure returns, and unbridled gotos.