xbasic64 Language Reference

A BASIC-to-x86_64 Educational Compiler

Compiler Design Project

December 14, 2025

 Abstract
This comprehensive technical report documents the xbasic64 compiler, an educational BASIC-to-
x86_64 native code compiler designed for students studying compiler design. The compiler imple-
ments a streamlined three-phase architecture (Lexer → Parser → Code Generator) that transforms
1980s-era BASIC programs into native x86-64 executables.
The report covers all aspects of the compiler implementation including lexical analysis, syntax anal-
ysis with recursive descent parsing, semantic analysis with type coercion, direct AST-to-assembly
code generation, and the runtime library system. It includes detailed explanations of the compila-
tion pipeline, formal grammar specifications, implementation walkthroughs with annotated source
code, and side-by-side examples showing BASIC code transformations to assembly.
This documentation serves both as a learning resource for compiler design students and as a com-
plete technical specification for the xbasic64 BASIC dialect, demonstrating how theoretical compiler
concepts translate into practical implementation.
Contents

1 Overview 11
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.1 What is xbasic64? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.2 Target Audience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.3 Educational Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.1.4 What You’ll Learn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Required Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
[Link] 1. Assembly Language Basics . . . . . . . . . . . . . . . . . . . . . . 13
[Link] 2. Rust Programming Basics . . . . . . . . . . . . . . . . . . . . . . 13
[Link] 3. Compiler Theory (Helpful but Not Required) . . . . . . . . . . . 13
1.2.2 Development Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Architecture Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.1 The Three-Phase Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
[Link] Phase 1: Lexical Analysis (Lexer) . . . . . . . . . . . . . . . . . . . 14
[Link] Phase 2: Syntax Analysis (Parser) . . . . . . . . . . . . . . . . . . . 15
[Link] Phase 3: Code Generation . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.2 Why This Differs from Traditional Compilers . . . . . . . . . . . . . . . . . . 16
1.3.3 Runtime Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4 Relationship to Compiler Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.1 Dragon Book Chapter Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.2 Key Theoretical Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.3 What’s Simplified . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5 Documentation Structure and Reading Guide . . . . . . . . . . . . . . . . . . . . . . 18
1.5.1 Document Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5.2 Recommended Reading Order . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
[Link] Path 1: Complete Beginner . . . . . . . . . . . . . . . . . . . . . . . 18
[Link] Path 2: Theory Background . . . . . . . . . . . . . . . . . . . . . . 19
[Link] Path 3: Specific Interest . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.3 Document Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.4 Visual Aids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.5 Code Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.6 Cross-References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.7 Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6.1 1. Build the Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1
 1.6.2 2. Try an Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6.3 3. Explore the Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6.4 4. Read the Documentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6.5 5. Try the Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.8 Navigation: ← Back to README | Next: Compiler Pipeline → . . . . . . . . . . . 21

2 Compiler Pipeline 22
2.1 Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Three-Phase Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 Phase 1: Lexical Analysis (Lexer) . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 Phase 2: Syntax Analysis (Parser) . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.3 Phase 3: Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Data Flow Through the Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.1 Example: Simple BASIC Program . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.2 After Lexical Analysis (Tokens) . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.3 After Syntax Analysis (AST) . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.4 After Code Generation (Assembly) . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Design Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 Why No Intermediate Representation (IR)? . . . . . . . . . . . . . . . . . . . 25
2.4.2 Trade-offs of Direct Translation . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.3 Single-Pass Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Comparison with Traditional Compilers . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.1 Traditional Multi-Phase Compiler . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.2 xbasic64 Simplified Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5.3 What’s Simplified for Education . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Pipeline Flow Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.9 Navigation: ← Overview | Home | Next: Lexical Analysis → . . . . . . . . . . . . . 30

3 Lexical Analysis Phase 31

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Theory: What is Lexical Analysis? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.1 Purpose of Lexical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 Regular Expressions and Finite Automata . . . . . . . . . . . . . . . . . . . . 31
3.2.3 Lexical vs. Syntactic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Token Types in xbasic64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.1 1. Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
[Link] Integer Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
[Link] Floating-Point Literals . . . . . . . . . . . . . . . . . . . . . . . . . 32
[Link] String Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.2 2. Identifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.3 3. Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
[Link] I/O Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
[Link] Variable Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
[Link] Control Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
[Link] Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2
 [Link] Program Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
[Link] Data Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
[Link] Logical Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
[Link] Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.4 4. Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
[Link] Arithmetic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . 34
[Link] Comparison Operators . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.5 5. Punctuation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.6 6. Special Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 BASIC-Specific Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 Case-Insensitive Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2 Type Suffixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.3 Line Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.4 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5 Implementation Walkthrough: src/[Link] . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5.1 The Lexer Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5.2 Core Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
[Link] advance() and peek() . . . . . . . . . . . . . . . . . . . . . . . . . . 38
[Link] skip_whitespace() . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
[Link] read_string() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
[Link] read_number() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
[Link] read_hex() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
[Link] read_identifier() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
[Link] keyword_or_ident() . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5.3 The Main Tokenization Loop: next_token() . . . . . . . . . . . . . . . . . . . 41
3.5.4 The tokenize() Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6 Tokenization Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6.1 Example 1: Simple Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.6.2 Example 2: FOR Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.6.3 Example 3: String with Escaped Quotes . . . . . . . . . . . . . . . . . . . . . 44
3.6.4 Example 4: IF Statement with Comparison . . . . . . . . . . . . . . . . . . . 44
3.6.5 Example 5: Line Numbers and Comments . . . . . . . . . . . . . . . . . . . . 45
3.6.6 Example 6: Type Suffixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6.7 Example 7: Hexadecimal and Scientific Notation . . . . . . . . . . . . . . . . 45
3.6.8 Example 8: Multiple Statements on One Line . . . . . . . . . . . . . . . . . . 46
3.6.9 Example 9: Array Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6.10 Example 10: Function Call with Operators . . . . . . . . . . . . . . . . . . . 47
3.7 Common Pitfalls and Edge Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.7.1 1. Whitespace Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.7.2 2. Case Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.7.3 3. Type Suffix Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.7.4 4. Operator Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.7.5 5. Hexadecimal vs. Long Suffix . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.7.6 6. Comment Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.10 Previous: Compiler Pipeline - Overview of the compilation process . . . . . . . . . 49

3
4 Syntax Analysis 50
4.1 Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 Parsing Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.1 What is Syntax Analysis? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.2 Context-Free Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.3 Parse Trees vs. Abstract Syntax Trees . . . . . . . . . . . . . . . . . . . . . . 51
4.2.4 Parsing Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2.5 Recursive Descent Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Formal Grammar Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.1 Program Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.2 Statement Productions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.3 Expression Productions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.4 Operator Precedence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.5 Grammar Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4 Parsing Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4.1 Recursive Descent for Statements . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4.2 Precedence Climbing for Expressions . . . . . . . . . . . . . . . . . . . . . . . 57
4.4.3 Handling Right-Associativity . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4.4 Error Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5 Abstract Syntax Tree (AST) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5.1 AST Node Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
[Link] Statement Nodes (Stmt) . . . . . . . . . . . . . . . . . . . . . . . . 58
[Link] Expression Nodes (Expr) . . . . . . . . . . . . . . . . . . . . . . . . 61
[Link] Supporting Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.5.2 AST Design Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.5.3 Example AST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.6 Parser Implementation Walkthrough . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.6.1 Parser Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.6.2 Core Parsing Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.6.3 Statement Parsing Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.6.4 Expression Parsing with Precedence Climbing . . . . . . . . . . . . . . . . . . 67
4.6.5 Parsing Complex Constructs . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.6.6 Parse Tree to AST Transformation . . . . . . . . . . . . . . . . . . . . . . . . 70
4.6.7 Example: Parsing a Complete Program . . . . . . . . . . . . . . . . . . . . . 70
4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.9 Navigation: ← Lexical Analysis | Home | Next: Semantic Analysis → . . . . . . . . 72

5 Semantic Analysis 73
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2 Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.3 What is Semantic Analysis? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.3.1 Purpose of Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.3.2 Semantic Analysis in xbasic64 . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.3.3 What Semantic Analysis Checks . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.4 The Type System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.4.1 BASIC’s Five Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.4.2 Type Suffixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

4
 5.4.3 Type Representation in Memory . . . . . . . . . . . . . . . . . . . . . . . . . 75
[Link] Integer Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
[Link] Floating-Point Types . . . . . . . . . . . . . . . . . . . . . . . . . . 75
[Link] String Type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.4.4 Type Determination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5 Type Coercion Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5.1 The Type Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5.2 Type Promotion Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.5.3 Special Operator Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
[Link] Division Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
[Link] Exponentiation (^) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
[Link] Comparison Operators . . . . . . . . . . . . . . . . . . . . . . . . . 78
[Link] Logical/Bitwise Operators . . . . . . . . . . . . . . . . . . . . . . . 78
5.5.4 Coercion Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.5.5 Coercion in Binary Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.5.6 Implicit vs. Explicit Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.6 Symbol Table Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.6.1 What is a Symbol Table? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.6.2 Symbol Table Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.6.3 Variable Storage Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.6.4 Implicit Variable Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.6.5 Scope Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
[Link] Global Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
[Link] Local Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
[Link] Procedure Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.6.6 Symbol Resolution Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.6.7 Array Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.6.8 Variable Lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.6.9 Symbol Table Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.6.10 Case Insensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.7 Semantic Analysis Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.7.1 Example 1: Type Coercion in Mixed Expressions . . . . . . . . . . . . . . . . 86
5.7.2 Example 2: Integer Division and Modulo . . . . . . . . . . . . . . . . . . . . 88
5.7.3 Example 3: Boolean Expressions . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.7.4 Example 4: Symbol Table States . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.7.5 Example 5: Local vs. Global Scope . . . . . . . . . . . . . . . . . . . . . . . . 91
5.7.6 Example 6: Type Coercion in Assignment . . . . . . . . . . . . . . . . . . . . 92
5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.8.1 Type System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.8.2 Type Coercion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.8.3 Symbol Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.8.4 Integration with Code Generation . . . . . . . . . . . . . . . . . . . . . . . . 94
5.8.5 Design Philosophy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.10 Navigation: ← Syntax Analysis | Home | Next: Code Generation → . . . . . . . . 94

6 Code Generation Phase 95

6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5
 6.1.1 What is Code Generation? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.1.2 The Direct Translation Strategy . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.1.3 The Code Generation Process . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.1.4 Output Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.2 Target Architecture: x86-64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.2.1 Why x86-64? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.2.2 Key Architecture Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
[Link] Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
[Link] SSE Registers for Floating-Point . . . . . . . . . . . . . . . . . . . . 97
6.2.3 System V AMD64 ABI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
[Link] Function Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
[Link] Return Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
[Link] Register Preservation . . . . . . . . . . . . . . . . . . . . . . . . . . 98
[Link] Stack Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3 Register Allocation Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3.1 Primary Result Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3.2 Binary Operation Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.3.3 Why This Strategy? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.4 Stack Frame Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.4.1 Stack Frame Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.4.2 Function Prologue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.4.3 Function Epilogue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.4.4 Variable Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.4.5 Stack Alignment Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.4.6 Accessing Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.5 Implementation Walkthrough: src/[Link] . . . . . . . . . . . . . . . . . . . . . . 101
6.5.1 The CodeGen Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.5.2 Type System and Coercion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.5.3 Expression Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.5.4 Binary Expression Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.5.5 Statement Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
[Link] Variable Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
[Link] IF Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
[Link] FOR Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.5.6 Built-in Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.5.7 Array Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.6 Side-by-Side Examples: BASIC to Assembly . . . . . . . . . . . . . . . . . . . . . . . 111
6.6.1 Example 1: Simple Variable Assignment . . . . . . . . . . . . . . . . . . . . . 111
6.6.2 Example 2: Arithmetic Expression . . . . . . . . . . . . . . . . . . . . . . . . 111
6.6.3 Example 3: Type Coercion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.6.4 Example 4: IF Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.6.5 Example 5: FOR Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.6.6 Example 6: Function Call . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.6.7 Example 7: String Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.6.8 Example 8: Array Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.7 Common Patterns and Idioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.7.1 Pattern 1: Zero a Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.7.2 Pattern 2: Boolean to Integer . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

6
 6.7.3 Pattern 3: Load Floating-Point Constant . . . . . . . . . . . . . . . . . . . . 119
6.7.4 Pattern 4: Sign Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.7.5 Pattern 5: Function Prologue/Epilogue . . . . . . . . . . . . . . . . . . . . . 119
6.8 Optimization Opportunities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.8.1 1. Register Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.8.2 2. Constant Folding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.8.3 3. Common Subexpression Elimination . . . . . . . . . . . . . . . . . . . . . . 120
6.8.4 4. Dead Code Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.8.5 5. Strength Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.8.6 6. Loop Invariant Code Motion . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.10 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.12 Previous: ← Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

7 Runtime System 122

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.2 Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.3 Runtime Library Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.3.1 Purpose and Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.3.2 Runtime Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
7.3.3 How Compiled Programs Use the Runtime . . . . . . . . . . . . . . . . . . . 123
7.3.4 Calling Convention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7.3.5 Libc Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7.3.6 Runtime Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7.4 String Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.4.1 String Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.4.2 String Return Convention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.4.3 String Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
[Link] String Conversion Functions . . . . . . . . . . . . . . . . . . . . . . 126
[Link] Substring Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
[Link] String Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
[Link] String Concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.4.4 Static Buffers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.5 I/O Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.5.1 Console Output (PRINT Statement) . . . . . . . . . . . . . . . . . . . . . . . 132
[Link] Print Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
[Link] PRINT Statement Compilation . . . . . . . . . . . . . . . . . . . . . 135
7.5.2 Console Input (INPUT Statement) . . . . . . . . . . . . . . . . . . . . . . . . 135
7.5.3 File I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
[Link] File Handle Management . . . . . . . . . . . . . . . . . . . . . . . . 137
[Link] File Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.5.4 DATA/READ/RESTORE Support . . . . . . . . . . . . . . . . . . . . . . . . 141
[Link] Data Table Format . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
[Link] Runtime Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.6 Math Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.6.1 Implementation Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.6.2 Runtime Math Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

7
 7.6.3 Inline Math Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
7.6.4 Math Function Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.6.5 Why Inline vs. Runtime? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.7 Runtime Implementation Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7.7.1 Source File Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
[Link] src/runtime/data_defs.s - Data Section Definitions . . . . . . . . 148
[Link] src/runtime/print.s - Print Functions . . . . . . . . . . . . . . . 148
[Link] src/runtime/input.s - Input Functions . . . . . . . . . . . . . . . 148
[Link] src/runtime/string.s - String Functions . . . . . . . . . . . . . . 149
[Link] src/runtime/math.s - Math and Utility Functions . . . . . . . . . 149
[Link] src/runtime/data.s - DATA/READ/RESTORE Support . . . . . 149
[Link] src/runtime/file.s - File I/O Functions . . . . . . . . . . . . . . 149
7.7.2 Runtime Assembly Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
7.7.3 Linking Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.7.4 Runtime Function Naming Convention . . . . . . . . . . . . . . . . . . . . . . 151
7.7.5 Performance Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.7.6 Debugging Runtime Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.7.7 Extending the Runtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
7.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
7.9 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
7.9.1 Related Documentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
7.9.2 External Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
7.9.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

8 xbasic64 Language Reference 156

8.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.2 Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.3 1. Formal Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.3.1 1.1 Notation Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.3.2 1.2 Program Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.3.3 1.3 Assignment Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.3.4 1.4 Print Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.3.5 1.5 Input Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
8.3.6 1.6 Control Flow Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
8.3.7 1.7 Jump Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.3.8 1.8 Array Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.3.9 1.9 Procedure Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.3.10 1.10 Data Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.3.11 1.11 File I/O Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.3.12 1.12 Other Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.3.13 1.13 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
8.3.14 1.14 Literals and Identifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.4 2. Lexical Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.4.1 2.1 Character Set and Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.4.2 2.2 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.4.3 2.3 Line Numbers and Statement Separators . . . . . . . . . . . . . . . . . . . 162
8.4.4 2.4 Identifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
8.4.5 2.5 Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

8
 [Link] 2.5.1 Integer Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
[Link] 2.5.2 Floating-Point Literals . . . . . . . . . . . . . . . . . . . . . . 163
[Link] 2.5.3 String Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
8.4.6 2.6 Operators and Punctuation . . . . . . . . . . . . . . . . . . . . . . . . . . 164
8.4.7 2.7 Token Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
8.5 3. Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
8.5.1 3.1 Assignment Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
8.5.2 3.2 PRINT Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
8.5.3 3.3 INPUT Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
8.5.4 3.4 LINE INPUT Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
8.5.5 3.5 IF Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.5.6 3.6 FOR…NEXT Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.5.7 3.7 WHILE…WEND Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
8.5.8 3.8 DO…LOOP Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
8.5.9 3.9 SELECT CASE Statement . . . . . . . . . . . . . . . . . . . . . . . . . . 169
8.5.10 3.10 GOTO Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.5.11 3.11 GOSUB and RETURN Statements . . . . . . . . . . . . . . . . . . . . . 170
8.5.12 3.12 ON…GOTO Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.5.13 3.13 DIM Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.5.14 3.14 SUB Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
8.5.15 3.15 FUNCTION Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
8.5.16 3.16 Call Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
8.5.17 3.17 DATA, READ, and RESTORE Statements . . . . . . . . . . . . . . . . 173
8.5.18 3.18 File I/O Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
[Link] 3.18.1 OPEN Statement . . . . . . . . . . . . . . . . . . . . . . . . . 174
[Link] 3.18.2 CLOSE Statement . . . . . . . . . . . . . . . . . . . . . . . . 174
[Link] 3.18.3 File PRINT Statement . . . . . . . . . . . . . . . . . . . . . . 174
[Link] 3.18.4 File INPUT Statement . . . . . . . . . . . . . . . . . . . . . . 174
8.5.19 3.19 CLS Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
8.5.20 3.20 END Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
8.5.21 3.21 STOP Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
8.6 4. Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.6.1 4.1 Expression Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.6.2 4.2 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.6.3 4.3 Type Coercion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
8.6.4 4.4 Arithmetic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.6.5 4.5 Comparison Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.6.6 4.6 Logical Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
8.6.7 4.7 String Concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
8.6.8 4.8 Operator Precedence Table . . . . . . . . . . . . . . . . . . . . . . . . . . 179
8.6.9 4.9 Built-in Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
[Link] 4.9.1 Mathematical Functions . . . . . . . . . . . . . . . . . . . . . . 180
[Link] 4.9.2 String Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 180
[Link] 4.9.3 Type Conversion Functions . . . . . . . . . . . . . . . . . . . . 181
[Link] 4.9.4 Other Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 181
8.6.10 4.10 Expression Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
8.7 5. Language Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
8.7.1 5.1 Variables and Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

9
 8.7.2 5.2 Arithmetic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
8.7.3 5.3 Comparison and Logical Operations . . . . . . . . . . . . . . . . . . . . . 183
8.7.4 5.4 String Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
8.7.5 5.5 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
8.7.6 5.6 Control Flow - IF Statement . . . . . . . . . . . . . . . . . . . . . . . . . 185
8.7.7 5.7 Control Flow - Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
8.7.8 5.8 SELECT CASE Statement . . . . . . . . . . . . . . . . . . . . . . . . . . 188
8.7.9 5.9 Subroutines and Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 189
8.7.10 5.10 DATA, READ, and RESTORE . . . . . . . . . . . . . . . . . . . . . . . 190
8.7.11 5.11 File I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
8.7.12 5.12 GOTO and GOSUB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
8.7.13 5.13 Complete Program Example: Guessing Game . . . . . . . . . . . . . . . 192
8.7.14 5.14 Complete Program Example: Fibonacci Sequence . . . . . . . . . . . . . 193
8.7.15 5.15 Complete Program Example: Array Sorting . . . . . . . . . . . . . . . . 194
8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

10
Chapter 1

Overview

1.1 Introduction
Welcome to the xbasic64 compiler documentation! This guide will take you on a journey through the
design and implementation of a real, working compiler that transforms 1980s-era BASIC programs
into native x86-64 machine code.

1.1.1 What is xbasic64?

xbasic64 is a BASIC-to-x86_64 native code compiler that compiles classic BASIC dialects
(Tandy Color BASIC, GW-BASIC, QuickBASIC) directly to native executables. Unlike interpreters
or bytecode compilers, xbasic64 produces fast, standalone binaries that run directly on modern x86-
64 processors.
The compiler is written in Rust and generates x86-64 assembly code that is then assembled and
linked into executable programs. It supports the core features of 1980s BASIC including:
• Classic BASIC syntax with optional line numbers
• Five data types: Integer, Long, Single, Double, and String
• Control flow structures: IF/THEN/ELSE, FOR/NEXT, WHILE/WEND, DO/LOOP, SE-
LECT CASE
• Procedures with SUB and FUNCTION (including recursion)
• File I/O operations
• Built-in math and string functions
• DATA/READ/RESTORE for inline data

1.1.2 Target Audience

This documentation is designed for compiler design students who want to understand how
compilers work by studying a real implementation. Whether you’re:
• Taking a compiler design course and want to see theory in practice
• Reading the Dragon Book and looking for a concrete example
• Learning about code generation and assembly language
• Interested in language implementation and runtime systems
• Building your own programming language

11
…this documentation will help you understand the complete compilation pipeline from source code
to executable binary.

1.1.3 Educational Value

Why study xbasic64 instead of a more complex compiler like GCC or LLVM?
Simplicity: xbasic64 uses a straightforward three-phase architecture (Lexer → Parser → Code
Generator) without the complexity of intermediate representations, optimization passes, or ad-
vanced type systems. You can understand the entire compiler in a few hours.
Completeness: Despite its simplicity, xbasic64 is a complete, working compiler that handles
real programs. It demonstrates all the essential compiler phases: lexical analysis, syntax analysis,
semantic analysis, and code generation.
Readability: The Rust codebase is clean, well-structured, and easy to follow. Each phase is
implemented in a single file with clear separation of concerns.
Practical Focus: xbasic64 generates real x86-64 assembly code and produces actual executables.
You’ll learn how high-level language constructs map to machine instructions.
Extensibility: The simple architecture makes it easy to add new features, experiment with op-
timizations, or modify the language. The exercises in this documentation will guide you through
various extensions.

1.1.4 What You’ll Learn

By studying xbasic64, you will understand:
1. Lexical Analysis: How to tokenize source code using regular expressions and finite automata
2. Syntax Analysis: How to parse tokens into an Abstract Syntax Tree using recursive descent
parsing
3. Semantic Analysis: How to implement type checking, type coercion, and symbol table
management
4. Code Generation: How to translate high-level constructs to x86-64 assembly code
5. Runtime Systems: How compiled programs interact with runtime libraries for I/O and
string operations
6. Calling Conventions: How to follow the System V AMD64 ABI for function calls and stack
management
7. Practical Trade-offs: Why xbasic64 makes certain design decisions and how they differ
from production compilers

1.2 Prerequisites
To get the most out of this documentation, you should have some background knowledge in a few
key areas. Don’t worry if you’re not an expert—we’ll explain concepts as we go—but familiarity
with these topics will help you follow along more easily.

12
1.2.1 Required Background
[Link] 1. Assembly Language Basics
You should understand fundamental assembly language concepts:
• Registers: What they are and how they’re used to hold values
• Instructions: Basic operations like MOV, ADD, CALL, JMP
• Stack: How the stack works for function calls and local variables
• Memory addressing: How to access memory locations
You don’t need to be an x86-64 expert, but basic assembly knowledge will help you understand the
code generation phase. If you’ve taken a computer architecture or systems programming course,
you’re well-prepared.
Learning Resources: - x86-64 Assembly Language Programming - Quick reference - Intel 64 and
IA-32 Architectures Software Developer Manuals - Comprehensive reference - System V AMD64
ABI - Calling convention specification

[Link] 2. Rust Programming Basics

The xbasic64 compiler is written in Rust, so you should be comfortable with:
• Basic syntax: Variables, functions, control flow
• Ownership and borrowing: Rust’s memory management model
• Enums and pattern matching: Used extensively for tokens and AST nodes
• Traits: For implementing common behaviors
• Error handling: Result types and error propagation
You don’t need to be a Rust expert, but you should be able to read and understand Rust code. If
you’ve completed the Rust Book’s first 10 chapters, you’re ready.
Learning Resources: - The Rust Programming Language - Official book (free online) - Rust by
Example - Learn by doing - Rustlings - Interactive exercises

[Link] 3. Compiler Theory (Helpful but Not Required)

If you’ve taken a compiler design course or read a compiler textbook, you’ll recognize many concepts
in xbasic64. However, this documentation is designed to be accessible even if you haven’t studied
compiler theory formally.
We’ll explain concepts like: - Regular expressions and finite automata (for lexical analysis) - Context-
free grammars and parse trees (for syntax analysis) - Symbol tables and type systems (for semantic
analysis) - Code generation and optimization (for the backend)
If you have studied compiler theory, the Theory Comparison document maps xbasic64 concepts to
standard textbook material.
Learning Resources: - Compilers: Principles, Techniques, and Tools (Dragon Book) - Classic
textbook - Crafting Interpreters - Modern, practical approach (free online) - Engineering a Compiler
- Alternative textbook

13
1.2.2 Development Environment
To build and experiment with xbasic64, you’ll need:
• Rust toolchain: Install from [Link]
• System assembler: as (usually pre-installed on Linux/macOS)
• C compiler/linker: cc with libc (for linking the final executable)
• Text editor: Any editor with Rust support (VS Code, Vim, Emacs, etc.)
See the main README for detailed build instructions.

1.3 Architecture Overview

xbasic64 uses a three-phase pipeline architecture that transforms BASIC source code into
native x86-64 executables. This section provides a high-level overview of how the compiler works.

1.3.1 The Three-Phase Pipeline

��������������� ��������������� ��������������� ���������������
� Source � � Tokens � � AST � � Assembly �
� Code � ���> � Stream � ���> � Tree � ���> � Code �
� (BASIC) � � � � � � (x86-64) �
��������������� ��������������� ��������������� ���������������
� � � �
� � � �
v v v v
Lexer Parser Code Generator Assembler
([Link]) ([Link]) ([Link]) (external)

[Link] Phase 1: Lexical Analysis (Lexer)

The lexer reads the source code character by character and groups them into tokens—meaningful
units like keywords, identifiers, numbers, and operators.
Input: BASIC source code as a string
FOR I = 1 TO 10
PRINT I
NEXT I
Output: Stream of tokens
Token::For
Token::Ident("I")
Token::Eq
Token::Integer(1)
Token::To
Token::Integer(10)
Token::Newline
Token::Print
Token::Ident("I")

14
Token::Newline
Token::Next
Token::Ident("I")
The lexer handles BASIC-specific features like: - Case-insensitive keywords (FOR, for, For are all
the same) - Type suffixes (%, &, !, #, $) - Line numbers (optional) - String literals with escape
sequences
See Lexical Analysis for details.

[Link] Phase 2: Syntax Analysis (Parser)

The parser reads the token stream and builds an Abstract Syntax Tree (AST)—a hierar-
chical representation of the program’s structure that captures the relationships between language
constructs.
Input: Token stream (from lexer)
Output: Abstract Syntax Tree
ForLoop {
var: "I",
start: Literal(1),
end: Literal(10),
step: None,
body: [
Print {
args: [Variable("I")]
}
]
}
The parser uses recursive descent parsing with precedence climbing for expressions. It
validates that the program follows BASIC’s grammar rules and reports syntax errors.
See Syntax Analysis for details.

[Link] Phase 3: Code Generation

The code generator walks the AST and emits x86-64 assembly code. It handles: - Type checking
and type coercion - Symbol table management (tracking variables and their types) - Register
allocation - Stack frame management - Calling conventions (System V AMD64 ABI)
Input: Abstract Syntax Tree
Output: x86-64 assembly code
mov DWORD PTR [rbp-4], 1 # I = 1
.L_for_1:
mov eax, DWORD PTR [rbp-4] # Load I
cmp eax, 10 # Compare with 10
jg .L_for_end_1 # Exit if I > 10

15
 mov eax, DWORD PTR [rbp-4] # Load I for PRINT
call print_integer # Print it

add DWORD PTR [rbp-4], 1 # I = I + 1

jmp .L_for_1 # Loop back
.L_for_end_1:
The generated assembly is then passed to the system assembler (as) and linker (cc) to produce the
final executable.
See Code Generation for details.

1.3.2 Why This Differs from Traditional Compilers

Most production compilers use a more complex multi-phase architecture:
Traditional Compiler:
Source → Lexer → Parser → Semantic Analyzer → IR Generator →
Optimizer → Code Generator → Assembly → Executable
xbasic64 simplifies this by:
1. No Intermediate Representation (IR): xbasic64 generates assembly directly from the
AST. Traditional compilers use an IR (like LLVM IR) to enable optimization and retargeting
to multiple architectures.
2. Combined Semantic Analysis and Code Generation: Type checking and code genera-
tion happen together in a single pass. Traditional compilers separate these phases.
3. Minimal Optimization: xbasic64 performs no optimization. Traditional compilers have
multiple optimization passes (constant folding, dead code elimination, register allocation,
etc.).
4. Single Target Architecture: xbasic64 only targets x86-64. Traditional compilers support
multiple architectures through retargetable backends.
Why these simplifications?
• Educational clarity: Fewer phases means less complexity to understand
• Faster development: Simpler architecture is easier to implement and modify
• Sufficient for BASIC: BASIC programs are typically small and don’t benefit much from
optimization
• Focus on fundamentals: You learn the core concepts without getting lost in optimization
theory
These trade-offs make xbasic64 an excellent learning tool while still being a complete, working
compiler.

1.3.3 Runtime Library

In addition to the three compilation phases, xbasic64 includes a runtime library written in x86-64
assembly. The runtime provides:
• I/O operations: PRINT, INPUT, file operations

16
 • String operations: Concatenation, substring, search
• Math functions: SIN, COS, SQR, etc. (wrapping libc functions)
• Memory management: String allocation and deallocation
Compiled programs link against this runtime library to access these features. The runtime uses
libc for portability across Linux and macOS.
See Runtime System for details.

1.4 Relationship to Compiler Theory

If you’re studying compiler design from a textbook like the Dragon Book, you might wonder how
xbasic64 relates to the concepts you’re learning. This section provides a quick mapping.

1.4.1 Dragon Book Chapter Mapping

xbasic64 demonstrates concepts from these Dragon Book chapters:

Dragon Book Chapter xbasic64 Component Documentation

Chapter 1: Introduction Overall architecture This document
Chapter 2: A Simple Compiler Complete pipeline Pipeline
Chapter 3: Lexical Analysis Lexer (src/[Link]) Lexical Analysis
Chapter 4: Syntax Analysis Parser (src/[Link]) Syntax Analysis
Chapter 5: Syntax-Directed Code generator Code Generation
Translation
Chapter 6: Type Checking Type system in codegen Semantic Analysis
Chapter 7: Run-Time Stack frames, calling Code Generation
Environments conventions
Chapter 8: Code Generation Assembly emission Code Generation

Not covered in xbasic64: - Chapter 9: Machine-Independent Optimizations (no optimization

passes) - Chapter 10: Instruction-Level Parallelism (no instruction scheduling) - Chapter 11: Opti-
mizing for Parallelism (no parallel code generation) - Chapter 12: Interprocedural Analysis (single-
module only)

1.4.2 Key Theoretical Concepts

Here’s how xbasic64 implements standard compiler theory concepts:
Lexical Analysis: - Uses hand-written lexer (not generated from regex) - Implements finite au-
tomaton for tokenization - Handles case-insensitive keywords with normalization
Syntax Analysis: - Recursive descent parser (top-down parsing) - Precedence climbing for expres-
sion parsing - Direct AST construction (no separate parse tree)
Semantic Analysis: - Type checking during code generation - Automatic type coercion following
BASIC rules - Symbol table for variable tracking
Code Generation: - Direct AST-to-assembly translation - Stack-based allocation for local vari-
ables - Register allocation for expression evaluation - System V AMD64 ABI compliance

17
Runtime System: - Hand-written assembly for performance-critical operations - libc integration
for portability - Dynamic string memory management
For a detailed comparison of xbasic64 to compiler theory, see Theory Comparison.

1.4.3 What’s Simplified

To keep the compiler understandable, xbasic64 simplifies or omits several features found in produc-
tion compilers:
1. No Intermediate Representation: Direct AST-to-assembly translation
2. No Optimization: Code is generated naively without optimization passes
3. Simple Type System: Only five types with straightforward coercion rules
4. Single Module: No separate compilation or linking of multiple source files
5. Limited Error Recovery: Parser stops at first syntax error
6. No Debugging Info: Generated code doesn’t include DWARF debug information
7. Single Architecture: Only targets x86-64 (no ARM, RISC-V, etc.)
These simplifications make the compiler easier to understand while still demonstrating all the
essential compilation phases.

1.5 Documentation Structure and Reading Guide

This documentation is organized into 10 main documents, each focusing on a specific aspect of the
compiler. Here’s how to navigate them effectively.

1.5.1 Document Organization

docs/
��� [Link] # Entry point (you've already read this!)
��� [Link] # This document - big picture overview
��� [Link] # Detailed look at the compilation pipeline
��� [Link] # Deep dive into tokenization
��� [Link] # Deep dive into parsing
��� [Link] # Type checking and symbol tables
��� [Link] # Assembly code generation
��� [Link] # Runtime library and support functions
��� [Link] # Complete BASIC language specification
��� [Link] # Hands-on practice problems
��� [Link] # Relating xbasic64 to textbook concepts

1.5.2 Recommended Reading Order

[Link] Path 1: Complete Beginner
If you’re new to compilers, follow this linear path:
1. Overview (this document) - Understand the big picture
2. Pipeline - See how the phases connect
3. Lexical Analysis - Start with tokenization
4. Syntax Analysis - Move to parsing

18
 5. Semantic Analysis - Learn about type checking
6. Code Generation - Understand assembly generation
7. Runtime System - See how runtime support works
8. Exercises - Practice what you’ve learned
Use the Language Reference as needed when you encounter unfamiliar BASIC features.

[Link] Path 2: Theory Background

If you’ve studied compiler theory and want to see it in practice:
1. Overview (this document) - Quick orientation
2. Theory Comparison - Map concepts to textbook
3. Pipeline - Understand the architecture
4. Jump to phases that interest you:
• Lexical Analysis
• Syntax Analysis
• Code Generation
5. Exercises - Try advanced extensions

[Link] Path 3: Specific Interest

If you’re interested in a particular topic:
• Lexical analysis: Read Lexical Analysis
• Parsing techniques: Read Syntax Analysis
• Type systems: Read Semantic Analysis
• Assembly generation: Read Code Generation
• Runtime systems: Read Runtime System
• Language design: Read Language Reference
Each document is self-contained with cross-references to related topics.

1.5.3 Document Structure

Each technical document follows a consistent structure:
1. Theory Section: Explains the compiler theory concepts
2. xbasic64 Implementation: Shows how xbasic64 implements those concepts
3. Data Structures: Documents key data structures used
4. Code Walkthrough: Annotated tour of the source code
5. Examples: Input/output examples showing the phase in action
6. Common Pitfalls: Things to watch out for
7. Exercises: Practice problems for that phase

1.5.4 Visual Aids

The documentation includes several diagrams in the diagrams/ directory:
• Pipeline Flow: Shows data flow through compilation phases
• AST Structure: Illustrates AST node hierarchy
• Stack Frame: Shows x86-64 stack layout

19
 • Type Hierarchy: Visualizes type system and coercion

1.5.5 Code Examples

The examples/ directory contains annotated examples:
• lexer-examples/: Source code with token stream output
• parser-examples/: Token streams with resulting AST
• codegen-examples/: BASIC code with generated assembly

1.5.6 Cross-References
Documents include links to: - Related documentation sections - Source code files (src/[Link],
src/[Link], etc.) - Example programs (examples/[Link], etc.) - External resources (Dragon
Book chapters, x86-64 references)

1.5.7 Navigation
Each document includes: - Previous/Next links: Navigate sequentially through the documenta-
tion - Table of contents: Jump to specific sections - Back to README: Return to the main
documentation index

1.6 Getting Started

Ready to dive in? Here’s how to get started with xbasic64:

1.6.1 1. Build the Compiler

First, clone the repository and build the compiler:
git clone [Link]
cd xbasic64
cargo build --release
The compiled binary will be at target/release/xbasic64.

1.6.2 2. Try an Example

Compile and run a simple BASIC program:
# Compile the Fibonacci example
./target/release/xbasic64 examples/[Link]

# Run the generated executable

./fibonacci

1.6.3 3. Explore the Source Code

The compiler source code is organized in src/:
• src/[Link] - Command-line interface and driver
• src/[Link] - Lexical analyzer (tokenizer)

20
 • src/[Link] - Syntax analyzer (parser)
• src/[Link] - Code generator (assembly emitter)
• src/[Link] - Runtime library integration
• src/runtime/ - Hand-written assembly runtime functions

1.6.4 4. Read the Documentation

Start with the next document: Compiler Pipeline

1.6.5 5. Try the Exercises

Once you understand the basics, try the hands-on exercises in Exercises to practice extending the
compiler.

1.7 Summary
xbasic64 is an educational BASIC compiler that demonstrates all the essential phases of compilation:
lexical analysis, syntax analysis, semantic analysis, and code generation. Its simple three-phase ar-
chitecture makes it easy to understand while still being a complete, working compiler that generates
real x86-64 executables.
This documentation will guide you through each phase of the compiler, relating practical implemen-
tation to theoretical concepts. Whether you’re a student learning compiler design or an educator
looking for teaching materials, xbasic64 provides a clear, accessible example of how compilers work.
Next Steps: - Continue to Compiler Pipeline to understand how the phases fit together - Jump
to a specific phase if you have a particular interest - Try building and running the compiler with
the example programs
Happy compiling! �

1.8 Navigation: ← Back to README | Next: Compiler Pipeline

→
title: “Compiler Pipeline” chapter: 2 prev: “[Link]” next: “[Link]”
dragon_book_chapters: [1, 2] difficulty: beginner estimated_time: “20 minutes” —

21
Chapter 2

Compiler Pipeline

The xbasic64 compiler uses a streamlined three-phase architecture that transforms BASIC source
code into executable x86-64 machine code. This document explains how data flows through the
compilation process and why this design differs from traditional multi-phase compilers.

2.1 Table of Contents

• Three-Phase Architecture
• Data Flow Through the Pipeline
• Design Decisions
• Comparison with Traditional Compilers
• Pipeline Flow Diagram
• Summary
• Further Reading

2.2 Three-Phase Architecture

The xbasic64 compiler consists of three sequential phases that execute in order:

2.2.1 Phase 1: Lexical Analysis (Lexer)

Purpose: Transform raw source text into a stream of tokens
Input: BASIC source code as a string
Output: Vector of tokens (Vec<Token>)
The lexer (src/[Link]) scans the source code character by character, grouping characters into
meaningful units called tokens. It handles:
• Keywords: PRINT, IF, FOR, etc. (case-insensitive)
• Identifiers: Variable and function names with optional type suffixes (%, &, !, #, $)
• Literals: Numbers (integers and floats) and string constants
• Operators: +, -, *, /, ^, comparison operators, logical operators
• Punctuation: Parentheses, commas, semicolons, colons
The lexer also strips out whitespace and comments, producing a clean token stream for the parser.

22
2.2.2 Phase 2: Syntax Analysis (Parser)
Purpose: Build an Abstract Syntax Tree (AST) from the token stream
Input: Vector of tokens (Vec<Token>)
Output: Program AST (Program struct containing Vec<Stmt>)
The parser (src/[Link]) consumes tokens and constructs a hierarchical tree structure repre-
senting the program’s syntactic structure. It uses:
• Recursive descent parsing for statements
• Precedence climbing for expressions (handling operator precedence and associativity)
The AST captures the program’s structure without the syntactic noise of keywords and punctuation.
Each node represents a language construct (statement or expression) with its components.

2.2.3 Phase 3: Code Generation

Purpose: Translate the AST directly into x86-64 assembly code
Input: Program AST (Program)
Output: x86-64 assembly code as a string (Intel syntax)
The code generator (src/[Link]) walks the AST and emits assembly instructions for each
node. It handles:
• Variable storage: Allocating stack space for local variables
• Type coercion: Converting between Integer, Long, Single, Double, and String types
• Register allocation: Using simple conventions (integers in eax, floats in xmm0)
• Control flow: Translating IF, FOR, WHILE into conditional jumps and labels
• Function calls: Following System V AMD64 ABI for calling runtime functions
The generated assembly is then passed to the system assembler (as) and linker (cc) to produce the
final executable.

2.3 Data Flow Through the Pipeline

Here’s how a simple BASIC program transforms through each phase:

2.3.1 Example: Simple BASIC Program

10 LET x% = 42
20 PRINT "The answer is"; x%

2.3.2 After Lexical Analysis (Tokens)

[
Integer(10),
Let,
Ident("x%"),
Eq,
Integer(42),
Newline,

23
 Integer(20),
Print,
String("The answer is"),
Semicolon,
Ident("x%"),
Newline,
]
The lexer has identified line numbers, keywords, identifiers with type suffixes, operators, and literals.

2.3.3 After Syntax Analysis (AST)

Program {
statements: [
Label(10),
Let {
name: "x%",
indices: None,
value: IntLiteral(42),
},
Label(20),
Print {
items: [
PrintItem::Expr(StringLiteral("The answer is")),
PrintItem::Expr(Variable("x%")),
],
newline: true,
},
]
}
The parser has built a tree structure where each statement is represented as a typed node with its
components clearly identified.

2.3.4 After Code Generation (Assembly)

.section .text
.globl _start

_start:
# Prologue
push rbp
mov rbp, rsp
sub rsp, 16 # Allocate space for x% (8 bytes, rounded to 16)

L10:
# LET x% = 42
mov eax, 42
movsx rax, ax # Sign-extend to 64-bit

24
 mov [rbp-8], rax # Store x%

L20:
# PRINT "The answer is"; x%
lea rdi, [_str_0] # Load string pointer
mov rsi, 14 # String length
call _print_string

mov eax, [rbp-8] # Load x%

call _print_int
call _print_newline

# Exit
mov rax, 60 # sys_exit
xor rdi, rdi
syscall

.section .data
_str_0: .ascii "The answer is"
The code generator has produced x86-64 assembly that allocates variables on the stack, loads values
into registers, and calls runtime functions for I/O operations.

2.4 Design Decisions

2.4.1 Why No Intermediate Representation (IR)?
Traditional compilers often include one or more intermediate representations between the AST and
target code. Common IRs include:
• Three-address code (TAC)
• Static Single Assignment (SSA) form
• LLVM IR
• Java bytecode
xbasic64 deliberately omits an IR phase for several reasons:
1. Educational Clarity
The direct AST-to-assembly translation makes it easier to trace how high-level constructs map to
machine code. Students can see the connection without navigating through intermediate transfor-
mations.
2. Simplicity
Fewer phases mean less code to understand and maintain. The entire compiler is under 2000 lines
of Rust, making it approachable for students.
3. Sufficient for BASIC
BASIC’s simple semantics don’t require sophisticated analysis or optimization. Most BASIC state-
ments map naturally to short assembly sequences.

25
4. No Optimization Passes
Production compilers use IR to enable optimization passes (constant folding, dead code elimina-
tion, register allocation, etc.). Since xbasic64 prioritizes clarity over performance, we skip these
optimizations.

2.4.2 Trade-offs of Direct Translation

Advantages: - Simpler implementation - Easier to understand and debug - Faster compilation
(fewer passes) - Direct correspondence between source and assembly
Disadvantages: - No optimization opportunities - Harder to target multiple architectures (tightly
coupled to x86-64) - Less sophisticated register allocation - Repeated code patterns (no common
subexpression elimination)
For an educational compiler, these trade-offs favor simplicity and clarity over performance.

2.4.3 Single-Pass Code Generation

The code generator makes a single pass over the AST (after a preliminary scan for DATA state-
ments). This means:
• Variables are allocated on first use
• Forward references (like GOTO to later line numbers) are handled with label fixups
• No global analysis or optimization
This approach keeps the code generator straightforward while still supporting all BASIC language
features.

2.5 Comparison with Traditional Compilers

2.5.1 Traditional Multi-Phase Compiler
Source Code
↓
Lexer → Tokens
↓
Parser → AST
↓
Semantic Analyzer → Annotated AST
↓
IR Generator → Intermediate Representation
↓
Optimizer → Optimized IR
↓
Code Generator → Assembly
↓
Assembler → Object Code
↓
Linker → Executable

26
Traditional compilers separate concerns into many phases, each with a specific responsibility. This
enables:
• Multiple optimization passes on the IR
• Target independence (multiple backends can consume the same IR)
• Sophisticated analysis (data flow, control flow, alias analysis)
• Better code quality through optimization

2.5.2 xbasic64 Simplified Pipeline

Source Code
↓
Lexer → Tokens
↓
Parser → AST
↓
Code Generator → Assembly
↓
System Assembler (as) → Object Code
↓
System Linker (cc) → Executable
xbasic64 combines semantic analysis into the code generation phase and skips IR entirely. This
means:
• Type checking happens during code generation (implicit coercion)
• Symbol management is handled by the code generator’s variable map
• No optimization - code is generated as-is from the AST
The result is a compiler that’s easy to understand but produces unoptimized code.

2.5.3 What’s Simplified for Education

Compared to production compilers (like GCC, Clang, or rustc), xbasic64 omits:
1. Intermediate Representation - No IR means no optimization infrastructure
2. Separate Semantic Analysis - Type checking is implicit during code generation
3. Optimization Passes - No constant folding, dead code elimination, or register optimization
4. Advanced Register Allocation - Uses simple conventions instead of graph coloring
5. Multiple Backends - Tightly coupled to x86-64 (not portable to ARM, RISC-V, etc.)
6. Error Recovery - Stops at first error instead of collecting multiple errors
7. Incremental Compilation - Recompiles entire program every time
These simplifications make xbasic64 an excellent learning tool while keeping it practical enough to
compile real BASIC programs.

2.6 Pipeline Flow Diagram

The following diagram illustrates how data flows through the compilation pipeline:
�������������������������������������������������������������������

27
� BASIC Source Code �
� "10 PRINT \"Hello\"\n20 END" �
�������������������������������������������������������������������
�
�
��������������������������
� Lexical Analysis �
� (src/[Link]) �
� �
� • Character scanning �
� • Keyword recognition �
� • Token generation �
��������������������������
�
�
��������������������������
� Token Stream �
� [Integer(10), Print, �
� String("Hello"), ...]�
��������������������������
�
�
��������������������������
� Syntax Analysis �
� (src/[Link]) �
� �
� • Recursive descent �
� • Precedence climbing �
� • AST construction �
��������������������������
�
�
��������������������������
� Abstract Syntax Tree �
� Program { stmts: [ �
� Label(10), �
� Print {...}, ...]} �
��������������������������
�
�
��������������������������
� Code Generation �
� (src/[Link]) �
� �
� • AST traversal �
� • Type coercion �
� • Assembly emission �
��������������������������

28
 �
�
��������������������������
� x86-64 Assembly �
� .section .text �
� _start: �
� push rbp �
� ... �
��������������������������
�
�
��������������������������
� System Assembler (as) �
��������������������������
�
�
��������������������������
� System Linker (cc) �
��������������������������
�
�
��������������������������
� Executable Binary �
� (ELF on Linux) �
��������������������������
Each phase transforms the data into a form more suitable for the next phase, ultimately producing
executable machine code.

2.7 Summary
The xbasic64 compiler uses a three-phase pipeline: Lexer → Parser → Code Generator. This sim-
plified architecture omits intermediate representations and optimization passes found in production
compilers, making it easier to understand while still producing working executables.
Key takeaways:
• Three phases: Lexical analysis, syntax analysis, and code generation
• Direct translation: AST maps directly to assembly without an IR
• Educational focus: Simplicity and clarity over optimization and performance
• Single-pass generation: Code is emitted in one traversal of the AST
• System tools: Relies on as and cc for assembly and linking
This design makes xbasic64 an excellent vehicle for learning compiler fundamentals without the
complexity of production-grade compilers.

2.8 Further Reading

• Lexical Analysis - Deep dive into the tokenization phase

29
 • Syntax Analysis - How the parser builds the AST
• Code Generation - Assembly generation and x86-64 details
• Theory Comparison - How xbasic64 relates to compiler textbooks

2.9 Navigation: ← Overview | Home | Next: Lexical Analysis →

title: “Lexical Analysis Phase” chapter: 3 prev: “[Link]” next: “[Link]”
dragon_book_chapters: [3] difficulty: intermediate estimated_time: “60 minutes” —

30
Chapter 3

Lexical Analysis Phase

3.1 Introduction
Lexical analysis (also called scanning or tokenization) is the first phase of compilation. The lexer
reads the source code as a stream of characters and groups them into meaningful units called
tokens. This phase simplifies the parser’s job by converting raw text into a structured sequence of
categorized elements.
In xbasic64, the lexer is implemented in src/[Link] and transforms BASIC source code into a
vector of tokens that the parser can process.

3.2 Theory: What is Lexical Analysis?

3.2.1 Purpose of Lexical Analysis
The lexer serves several critical functions in the compilation pipeline:
1. Abstraction: Converts character streams into meaningful tokens, hiding low-level details
from the parser
2. Simplification: Removes whitespace, comments, and other non-essential characters
3. Classification: Categorizes input into token types (keywords, identifiers, literals, operators)
4. Error Detection: Identifies malformed tokens (e.g., unterminated strings, invalid charac-
ters)
5. Position Tracking: Maintains line and column information for error reporting

3.2.2 Regular Expressions and Finite Automata

In compiler theory, lexical analysis is typically described using regular expressions and imple-
mented using finite automata:
• Regular Expressions: Patterns that describe the structure of tokens
– Example: An identifier might be [a-zA-Z][a-zA-Z0-9_]* (letter followed by let-
ters/digits/underscores)
– Example: An integer might be [0-9]+ (one or more digits)
• Finite Automata: State machines that recognize patterns

31
 – DFA (Deterministic Finite Automaton): Each state has exactly one transition per
input symbol
– NFA (Non-deterministic Finite Automaton): States may have multiple transitions
per symbol
The xbasic64 lexer uses a hand-written approach rather than generated automata, but the underly-
ing principles are the same. Each token recognition function implements a small finite automaton.

3.2.3 Lexical vs. Syntactic Analysis

It’s important to understand the division of labor:
• Lexical Analysis (this phase): Recognizes individual tokens
– Example: FOR, I, =, 1, TO, 10
• Syntactic Analysis (next phase): Recognizes token patterns and structure
– Example: FOR I = 1 TO 10 forms a valid FOR loop statement
The lexer doesn’t understand program structure—it just identifies the building blocks.

3.3 Token Types in xbasic64

The xbasic64 lexer recognizes several categories of tokens, defined in the Token enum in
src/[Link]:

3.3.1 1. Literals
Literals represent constant values in the source code:

[Link] Integer Literals

• Decimal: 42, 0, 12345
• Hexadecimal: &HFF, &h10 (prefix with &H or &h)
• Stored as Token::Integer(i64)

[Link] Floating-Point Literals

• Decimal notation: 3.14, 0.5, 2.0
• Scientific notation: 1E5, 2e-3, 1.5E+10
• Double-precision notation: 1D5, 2d-3 (BASIC uses ‘D’ for double precision)
• Stored as Token::Float(f64)

[Link] String Literals

• Enclosed in double quotes: "Hello, World!"
• Escaped quotes using double-double quotes: "He said ""Hi"""
• Stored as Token::String(String)
Examples:
X = 42 ' Integer literal
Y = 3.14159 ' Float literal
Z = 1.5E-10 ' Scientific notation

32
HEX = &HFF ' Hexadecimal (255)
MSG$ = "Hello!" ' String literal

3.3.2 2. Identifiers
Identifiers are names for variables, functions, and labels:
• Must start with a letter (A-Z, case-insensitive)
• Can contain letters, digits, and underscores
• May end with a type suffix: %, &, !, #, $
• Stored as Token::Ident(String) with the name in uppercase
Type Suffixes: - % - Integer (16-bit) - & - Long (32-bit) - ! - Single-precision float - # - Double-
precision float - $ - String
Examples:
Counter ' Identifier (becomes "COUNTER")
X% ' Integer variable
Total& ' Long variable
Price! ' Single-precision float
Value# ' Double-precision float
Name$ ' String variable

3.3.3 3. Keywords
Keywords are reserved words with special meaning in BASIC. The xbasic64 lexer recognizes 47
keywords:

[Link] I/O Keywords

• PRINT - Output to console
• INPUT - Read from console
• LINE - Used with INPUT for line input
• OPEN, CLOSE - File operations
• CLS - Clear screen

[Link] Variable Declaration

• LET - Variable assignment (optional in most BASIC dialects)
• DIM - Array declaration

[Link] Control Flow

• IF, THEN, ELSE, ELSEIF, ENDIF - Conditional execution
• FOR, TO, STEP, NEXT - For loops
• WHILE, WEND - While loops
• DO, LOOP, UNTIL - Do-while loops
• SELECT, CASE, ENDSELECT - Select case statements
• GOTO, GOSUB, RETURN, ON - Jump statements

33
[Link] Procedures
• SUB, ENDSUB - Subroutine definition
• FUNCTION, ENDFUNCTION - Function definition

[Link] Program Control

• END - End program
• STOP - Stop execution

[Link] Data Statements

• DATA - Define data values
• READ - Read data values
• RESTORE - Reset data pointer

[Link] Logical Operators

• AND, OR, NOT, XOR - Boolean operations
• MOD - Modulo operator

[Link] Comments
• REM - Remark (comment)
Examples:
PRINT "Hello" ' PRINT keyword
FOR I = 1 TO 10 ' FOR, TO keywords
IF X > 5 THEN ' IF, THEN keywords

3.3.4 4. Operators
Operators perform operations on values:

[Link] Arithmetic Operators

• + - Addition (Token::Plus)
• - - Subtraction (Token::Minus)
• * - Multiplication (Token::Star)
• / - Division (Token::Slash)
• \ - Integer division (Token::Backslash)
• ^ - Exponentiation (Token::Caret)

[Link] Comparison Operators

• = - Equal (Token::Eq)
• <> - Not equal (Token::Ne)
• < - Less than (Token::Lt)
• > - Greater than (Token::Gt)
• <= - Less than or equal (Token::Le)
• >= - Greater than or equal (Token::Ge)

34
Examples:
X = Y + 5 ' Assignment and addition
IF A <> B THEN ' Not equal comparison
Z = 2 ^ 8 ' Exponentiation (256)

3.3.5 5. Punctuation
Punctuation tokens structure the code:
• ( - Left parenthesis (Token::LParen)
• ) - Right parenthesis (Token::RParen)
• , - Comma (Token::Comma)
• ; - Semicolon (Token::Semicolon)
• : - Colon (Token::Colon) - statement separator
• # - Hash (Token::Hash) - file number prefix
Examples:
DIM A(10) ' Parentheses for array dimensions
PRINT A; B, C ' Semicolon and comma separators
X = 1 : Y = 2 ' Colon separates statements
OPEN "[Link]" FOR OUTPUT AS #1 ' Hash for file number

3.3.6 6. Special Tokens

Special tokens mark structural elements:
• Token::Newline - End of line (also generated for comments)
• Token::LineNumber(u32) - Line number at start of line
• Token::Eof - End of file
Examples:
10 PRINT "Hello" ' LineNumber(10), Print, String, Newline
20 END ' LineNumber(20), End, Newline

3.4 BASIC-Specific Features

The xbasic64 lexer handles several features specific to BASIC dialects:

3.4.1 Case-Insensitive Keywords

BASIC is traditionally case-insensitive. The lexer converts all identifiers and keywords to uppercase
before checking against the keyword table:
print "Hello" ' Recognized as PRINT
Print "Hello" ' Also recognized as PRINT
PRINT "Hello" ' Also recognized as PRINT
PrInT "Hello" ' Also recognized as PRINT
Implementation Detail: The read_identifier() function converts each character to uppercase
using to_ascii_uppercase() as it reads:

35
fn read_identifier(&mut self, first: char) -> String {
let mut s = String::new();
[Link](first.to_ascii_uppercase());

while let Some(c) = [Link]() {

if c.is_ascii_alphanumeric() || c == '_' {
[Link]([Link]().unwrap().to_ascii_uppercase());
} else {
break;
}
}
// ... handle type suffix
}

3.4.2 Type Suffixes

BASIC uses type suffixes to indicate variable types without explicit declarations:

Suffix Type Size Example

% Integer 16-bit Count%
& Long 32-bit Total&
! Single 32-bit float Price!
# Double 64-bit float Value#
$ String Variable Name$

The lexer includes the type suffix as part of the identifier:

X% = 42 ' Token::Ident("X%")
Name$ = "Alice" ' Token::Ident("NAME$")
Implementation Detail: After reading the alphanumeric portion of an identifier, the lexer checks
for a type suffix:
// Check for type suffix
if let Some(c) = [Link]() {
if c == '%' || c == '&' || c == '!' || c == '#' || c == '$' {
[Link]([Link]().unwrap());
}
}

3.4.3 Line Numbers

Classic BASIC programs use line numbers at the beginning of each line:
10 PRINT "Hello"
20 FOR I = 1 TO 10
30 PRINT I
40 NEXT I
50 END

36
The lexer recognizes line numbers only at the start of a line (tracked by the at_line_start flag):
Implementation Detail:
// Check for line number at start of line
if self.at_line_start {
if let Some(c) = [Link]() {
if c.is_ascii_digit() {
let mut num = String::new();
while let Some(c) = [Link]() {
if c.is_ascii_digit() {
[Link]([Link]().unwrap());
} else {
break;
}
}
self.at_line_start = false;
self.skip_whitespace();
return Ok(Token::LineNumber([Link]().unwrap_or(0)));
}
}
}
Line numbers are optional in xbasic64—modern BASIC code typically omits them.

3.4.4 Comments
BASIC supports two comment styles:
1. REM statement: REM This is a comment
2. Apostrophe: ' This is a comment
Both comment styles cause the lexer to skip to the end of the line and return a Token::Newline:
X = 1 REM Set X to 1
Y = 2 ' Set Y to 2
Implementation Detail:
// Handle REM keyword
if ident == "REM" {
self.skip_comment();
return Ok(Token::Newline);
}

// Handle apostrophe
'\'' => {
self.skip_comment();
Ok(Token::Newline)
}

37
3.5 Implementation Walkthrough: src/[Link]
Let’s examine the key components of the xbasic64 lexer implementation:

3.5.1 The Lexer Structure

pub struct Lexer<'a> {
input: &'a str, // Source code string
chars: Peekable<Chars<'a>>, // Character iterator with lookahead
pos: usize, // Current byte position
line: u32, // Current line number
at_line_start: bool, // Are we at the start of a line?
}
The lexer maintains: - A reference to the input string - A peekable character iterator (allows looking
ahead one character) - Position tracking for error reporting - A flag to detect line numbers

3.5.2 Core Methods

[Link] advance() and peek()
These are the fundamental operations for consuming input:
fn advance(&mut self) -> Option<char> {
let c = [Link]();
if let Some(ch) = c {
[Link] += ch.len_utf8();
}
c
}

fn peek(&mut self) -> Option<char> {

[Link]().copied()
}
• advance() consumes and returns the next character
• peek() looks at the next character without consuming it

[Link] skip_whitespace()
Whitespace (spaces, tabs, carriage returns) is not significant in BASIC except as a token separator:
fn skip_whitespace(&mut self) {
while let Some(c) = [Link]() {
if c == ' ' || c == '\t' || c == '\r' {
[Link]();
} else {
break;
}
}
}

38
Note: Newlines (\n) are NOT skipped—they’re significant in BASIC as statement terminators.

[Link] read_string()
String literals are enclosed in double quotes, with "" as an escape sequence for a literal quote:
fn read_string(&mut self) -> Result<String, String> {
let mut s = String::new();
[Link](); // consume opening "
loop {
match [Link]() {
Some('"') => {
// Check for escaped quote ""
if [Link]() == Some('"') {
[Link]();
[Link]('"');
} else {
break; // End of string
}
}
Some('\n') | None => {
return Err("Unterminated string".to_string());
}
Some(c) => [Link](c),
}
}
Ok(s)
}
Example:
"Hello" → "Hello"
"Say ""Hi""" → "Say "Hi""
"Unterminated → Error: Unterminated string

[Link] read_number()
Numbers can be integers or floats, with optional scientific notation:
fn read_number(&mut self, first: char) -> Token {
let mut s = String::new();
[Link](first);

let mut is_float = false;

let mut has_exponent = false;

while let Some(c) = [Link]() {

if c.is_ascii_digit() {
[Link]([Link]().unwrap());
} else if c == '.' && !is_float && !has_exponent {

39
 is_float = true;
[Link]([Link]().unwrap());
} else if (c == 'e' || c == 'E' || c == 'd' || c == 'D') && !has_exponent {
has_exponent = true;
is_float = true;
[Link]([Link]().unwrap());
// Handle optional sign after exponent
if let Some(sign) = [Link]() {
if sign == '+' || sign == '-' {
[Link]([Link]().unwrap());
}
}
} else {
break;
}
}

// Replace D with E for parsing

let s = [Link](['d', 'D'], "e");

if is_float {
Token::Float([Link]().unwrap_or(0.0))
} else {
Token::Integer([Link]().unwrap_or(0))
}
}
This function handles: - Integer literals: 42 - Decimal literals: 3.14 - Scientific notation: 1E5, 2e-3
- BASIC double notation: 1D5 (converted to 1e5)

[Link] read_hex()
Hexadecimal literals use the &H prefix:
fn read_hex(&mut self) -> Token {
let mut s = String::new();
while let Some(c) = [Link]() {
if c.is_ascii_hexdigit() {
[Link]([Link]().unwrap());
} else {
break;
}
}
let val = i64::from_str_radix(&s, 16).unwrap_or(0);
Token::Integer(val)
}
Example:
&HFF → Token::Integer(255)

40
&h10 → Token::Integer(16)

[Link] read_identifier()
Identifiers are alphanumeric names with optional type suffixes:
fn read_identifier(&mut self, first: char) -> String {
let mut s = String::new();
[Link](first.to_ascii_uppercase());

while let Some(c) = [Link]() {

if c.is_ascii_alphanumeric() || c == '_' {
[Link]([Link]().unwrap().to_ascii_uppercase());
} else {
break;
}
}

// Check for type suffix

if let Some(c) = [Link]() {
if c == '%' || c == '&' || c == '!' || c == '#' || c == '$' {
[Link]([Link]().unwrap());
}
}

s
}

[Link] keyword_or_ident()
After reading an identifier, we check if it’s a keyword:
fn keyword_or_ident(&self, s: &str) -> Token {
let base = s.trim_end_matches(['%', '&', '!', '#', '$']);
KEYWORDS
.get(base)
.cloned()
.unwrap_or_else(|| Token::Ident(s.to_string()))
}
The keyword lookup strips type suffixes first, so PRINT% would be recognized as the PRINT keyword
(though this would be unusual).

3.5.3 The Main Tokenization Loop: next_token()

The next_token() method is the heart of the lexer. It returns the next token from the input:
pub fn next_token(&mut self) -> Result<Token, String> {
self.skip_whitespace();

// Check for line number at start of line

41
if self.at_line_start {
if let Some(c) = [Link]() {
if c.is_ascii_digit() {
// ... read line number
}
}
}
self.at_line_start = false;

let c = match [Link]() {

Some(c) => c,
None => return Ok(Token::Eof),
};

match c {
'\n' => {
[Link] += 1;
self.at_line_start = true;
Ok(Token::Newline)
}

'"' => {
// ... read string
}

'\'' => {
self.skip_comment();
Ok(Token::Newline)
}

'+' => Ok(Token::Plus),

'-' => Ok(Token::Minus),
// ... other single-character tokens

'<' => {
if [Link]() == Some('>') {
[Link]();
Ok(Token::Ne)
} else if [Link]() == Some('=') {
[Link]();
Ok(Token::Le)
} else {
Ok(Token::Lt)
}
}

'&' => {
if [Link]() == Some('H') || [Link]() == Some('h') {

42
 [Link]();
Ok(self.read_hex())
} else {
Ok(Token::Ident("&".to_string()))
}
}

_ if c.is_ascii_digit() => Ok(self.read_number(c)),

_ if c.is_ascii_alphabetic() => {
let ident = self.read_identifier(c);

if ident == "REM" {
self.skip_comment();
return Ok(Token::Newline);
}

Ok(self.keyword_or_ident(&ident))
}

_ => Err(format!("Unexpected character: {}", c)),

}
}
The method uses pattern matching to dispatch to the appropriate handler based on the first char-
acter.

3.5.4 The tokenize() Method

For convenience, the lexer provides a method to tokenize the entire input at once:
pub fn tokenize(&mut self) -> Result<Vec<Token>, String> {
let mut tokens = Vec::new();
loop {
let tok = self.next_token()?;
let is_eof = tok == Token::Eof;
[Link](tok);
if is_eof {
break;
}
}
Ok(tokens)
}
This is useful for testing and for compilers that prefer to tokenize everything upfront.

3.6 Tokenization Examples

Let’s see how various BASIC code snippets are tokenized:

43
3.6.1 Example 1: Simple Assignment
Input:
X = 42
Token Stream:
Token::Ident("X")
Token::Eq
Token::Integer(42)
Token::Eof

3.6.2 Example 2: FOR Loop

Input:
FOR I = 1 TO 10 STEP 2
Token Stream:
Token::For
Token::Ident("I")
Token::Eq
Token::Integer(1)
Token::To
Token::Integer(10)
Token::Step
Token::Integer(2)
Token::Eof

3.6.3 Example 3: String with Escaped Quotes

Input:
PRINT "He said ""Hello"""
Token Stream:
Token::Print
Token::String("He said \"Hello\"")
Token::Eof

3.6.4 Example 4: IF Statement with Comparison

Input:
IF X > 10 AND Y < 5 THEN PRINT X
Token Stream:
Token::If
Token::Ident("X")
Token::Gt
Token::Integer(10)

44
Token::And
Token::Ident("Y")
Token::Lt
Token::Integer(5)
Token::Then
Token::Print
Token::Ident("X")
Token::Eof

3.6.5 Example 5: Line Numbers and Comments

Input:
10 REM This is a comment
20 PRINT "Hello"
Token Stream:
Token::LineNumber(10)
Token::Newline (REM comment becomes newline)
Token::Newline (actual newline)
Token::LineNumber(20)
Token::Print
Token::String("Hello")
Token::Eof

3.6.6 Example 6: Type Suffixes

Input:
DIM Count%, Total&, Price!, Value#, Name$
Token Stream:
Token::Dim
Token::Ident("COUNT%")
Token::Comma
Token::Ident("TOTAL&")
Token::Comma
Token::Ident("PRICE!")
Token::Comma
Token::Ident("VALUE#")
Token::Comma
Token::Ident("NAME$")
Token::Eof

3.6.7 Example 7: Hexadecimal and Scientific Notation

Input:
X = &HFF
Y = 1.5E-10

45
Token Stream:
Token::Ident("X")
Token::Eq
Token::Integer(255)
Token::Newline
Token::Ident("Y")
Token::Eq
Token::Float(1.5e-10)
Token::Eof

3.6.8 Example 8: Multiple Statements on One Line

Input:
X = 1 : Y = 2 : PRINT X + Y
Token Stream:
Token::Ident("X")
Token::Eq
Token::Integer(1)
Token::Colon
Token::Ident("Y")
Token::Eq
Token::Integer(2)
Token::Colon
Token::Print
Token::Ident("X")
Token::Plus
Token::Ident("Y")
Token::Eof

3.6.9 Example 9: Array Declaration

Input:
DIM A(10), B$(100)
Token Stream:
Token::Dim
Token::Ident("A")
Token::LParen
Token::Integer(10)
Token::RParen
Token::Comma
Token::Ident("B$")
Token::LParen
Token::Integer(100)
Token::RParen
Token::Eof

46
3.6.10 Example 10: Function Call with Operators
Input:
Result = SIN(X) * 2 + COS(Y) ^ 2
Token Stream:
Token::Ident("RESULT")
Token::Eq
Token::Ident("SIN")
Token::LParen
Token::Ident("X")
Token::RParen
Token::Star
Token::Integer(2)
Token::Plus
Token::Ident("COS")
Token::LParen
Token::Ident("Y")
Token::RParen
Token::Caret
Token::Integer(2)
Token::Eof

3.7 Common Pitfalls and Edge Cases

3.7.1 1. Whitespace Handling
Whitespace is generally ignored, but newlines are significant:
PRINT "Hello" ' Spaces ignored
PRINT"Hello" ' Also valid
PRINT
"Hello" ' Error: newline breaks statement

3.7.2 2. Case Sensitivity

Keywords and identifiers are case-insensitive, but string contents are not:
print "HELLO" ' Keyword: case-insensitive
PRINT "hello" ' String: case-sensitive

3.7.3 3. Type Suffix Ambiguity

Type suffixes are part of the identifier, not separate tokens:
X% = 42 ' X% is one identifier
X % = 42 ' Error: X, %, = (% is not a valid token alone)

47
3.7.4 4. Operator Lookahead
Some operators require lookahead to distinguish:
X < Y ' Less than
X <> Y ' Not equal
X <= Y ' Less than or equal
The lexer must peek at the next character to decide.

3.7.5 5. Hexadecimal vs. Long Suffix

The & character has two meanings:
X = &HFF ' Hexadecimal prefix
Y& = 42 ' Long type suffix
The lexer checks if & is followed by H or h to distinguish.

3.7.6 6. Comment Handling

Comments consume the rest of the line:
X = 1 REM Set X
Y = 2 ' This is on a new line
Both REM and ' return Token::Newline, effectively ending the statement.

3.8 Summary
The lexical analysis phase transforms raw BASIC source code into a structured sequence of tokens.
Key takeaways:
1. Purpose: The lexer abstracts character-level details and provides meaningful tokens to the
parser
2. Token Categories: Literals, identifiers, keywords, operators, punctuation, and special to-
kens
3. BASIC Features: Case-insensitive keywords, type suffixes, line numbers, and two comment
styles
4. Implementation: Hand-written lexer using character-by-character scanning with one-
character lookahead
5. Error Handling: Detects malformed tokens like unterminated strings and unexpected char-
acters
The token stream produced by the lexer becomes the input to the parser, which we’ll explore in
the next chapter.

3.9 Further Reading

• Dragon Book Chapter 3: Lexical Analysis
• “Crafting Interpreters” by Robert Nystrom - Chapter 4: Scanning
• Regular expressions and finite automata theory

48
 • Unicode handling in lexers (xbasic64 uses ASCII for simplicity)

Next: Syntax Analysis Phase - Learn how tokens are parsed into an Abstract Syntax Tree

3.10 Previous: Compiler Pipeline - Overview of the compilation

process
title: “Syntax Analysis” chapter: 4 prev: “[Link]” next: “[Link]”
dragon_book_chapters: [4] difficulty: intermediate estimated_time: “60 minutes” —

49
Chapter 4

Syntax Analysis

Syntax analysis (parsing) is the second phase of compilation, where the flat stream of tokens
from the lexer is transformed into a hierarchical Abstract Syntax Tree (AST) that represents the
program’s structure. This document explains the theory behind parsing, the grammar of xbasic64’s
BASIC dialect, and how the parser implementation works.

4.1 Table of Contents

• Parsing Theory
• Formal Grammar Specification
• Parsing Strategy
• Abstract Syntax Tree (AST)
• Parser Implementation Walkthrough
• Summary
• Further Reading

4.2 Parsing Theory

4.2.1 What is Syntax Analysis?
Syntax analysis is the process of checking whether a sequence of tokens conforms to the grammatical
rules of a programming language and building a structured representation of the program. While
the lexer answers “what are the words?”, the parser answers “how do these words fit together?”
The parser: 1. Validates syntax: Ensures the token stream follows the language’s grammar rules
2. Builds structure: Creates a hierarchical tree (AST) representing the program 3. Reports
errors: Identifies and reports syntax errors with meaningful messages 4. Prepares for code
generation: Produces a structure that’s easy to traverse during code generation

4.2.2 Context-Free Grammars

Programming languages are typically defined using context-free grammars (CFGs), which
consist of:
• Terminals: Tokens from the lexer (keywords, operators, literals)

50
 • Non-terminals: Syntactic categories (statement, expression, etc.)
• Production rules: Rules that define how non-terminals expand into terminals and other
non-terminals
• Start symbol: The top-level non-terminal (usually “program”)
Example grammar fragment:
statement → IF expression THEN statement
statement → PRINT print_list
expression → term (('+' | '-') term)*
term → factor (('*' | '/') factor)*
factor → NUMBER | IDENT | '(' expression ')'
Each production rule shows how a non-terminal (left side) can be replaced by a sequence of terminals
and non-terminals (right side).

4.2.3 Parse Trees vs. Abstract Syntax Trees

Parse trees (also called concrete syntax trees) represent every detail of the grammar derivation,
including all terminals and non-terminals. They’re useful for understanding how the parser works
but contain unnecessary detail.
Abstract Syntax Trees (ASTs) strip away syntactic noise (keywords, punctuation) and focus
on the semantic structure. ASTs are what compilers actually use because they’re: - More compact
- Easier to traverse - Focused on meaning rather than syntax
Example: IF X > 0 THEN PRINT X
Parse tree (conceptual):
Statement
��� IF (keyword)
��� Expression
� ��� Variable(X)
� ��� > (operator)
� ��� Literal(0)
��� THEN (keyword)
��� Statement
��� PRINT (keyword)
��� Expression
��� Variable(X)
AST (what xbasic64 uses):
If {
condition: Binary { op: Gt, left: Variable("X"), right: Literal(0) }
then_branch: [Print { items: [Variable("X")] }]
else_branch: None
}
The AST omits IF, THEN, and PRINT keywords since they’re implicit in the node types.

51
4.2.4 Parsing Strategies
There are two main approaches to parsing:
Top-Down Parsing - Starts from the start symbol and tries to derive the input - Builds the parse
tree from root to leaves - Examples: Recursive descent, LL(k) parsers - xbasic64 uses this approach
Bottom-Up Parsing - Starts from the input and tries to reduce it to the start symbol - Builds
the parse tree from leaves to root - Examples: LR(k), LALR parsers (used by yacc/bison) - More
powerful but more complex

4.2.5 Recursive Descent Parsing

xbasic64 uses recursive descent parsing, a top-down technique where: - Each non-terminal has
a corresponding parsing function - Functions call each other recursively to match the grammar -
Simple to implement and understand - Works well for languages with predictable syntax
Advantages: - Easy to write and debug - Error messages can be very specific - No parser generator
needed - Full control over parsing logic
Limitations: - Can’t handle left-recursive grammars directly - May require lookahead for some
constructs - Not as powerful as LR parsers for ambiguous grammars

4.3 Formal Grammar Specification

Here is the complete grammar for xbasic64’s BASIC dialect in Extended Backus-Naur Form
(EBNF):

4.3.1 Program Structure

program ::= statement*

statement ::= line_number? stmt_body (NEWLINE | EOF)

line_number ::= INTEGER

stmt_body ::= label_stmt

| let_stmt
| print_stmt
| input_stmt
| line_input_stmt
| if_stmt
| for_stmt
| while_stmt
| do_loop_stmt
| select_case_stmt
| goto_stmt
| gosub_stmt
| return_stmt
| on_goto_stmt

52
 | dim_stmt
| sub_stmt
| function_stmt
| call_stmt
| data_stmt
| read_stmt
| restore_stmt
| open_stmt
| close_stmt
| cls_stmt
| end_stmt
| stop_stmt

4.3.2 Statement Productions

(* Assignment *)
let_stmt ::= LET? IDENT array_subscript? '=' expression

array_subscript ::= '(' expression_list ')'

(* Output *)
print_stmt ::= PRINT ('#' INTEGER ',')? print_list?

print_list ::= print_item (print_sep print_item)* print_sep?

print_item ::= expression

print_sep ::= ';' | ','

(* Input *)
input_stmt ::= INPUT ('#' INTEGER ',')? (STRING ',')? ident_list

line_input_stmt ::= LINE INPUT (STRING ',')? IDENT

ident_list ::= IDENT (',' IDENT)*

(* Control Flow *)
if_stmt ::= IF expression THEN (single_line_if | block_if)

single_line_if ::= statement (ELSE statement)?

block_if ::= NEWLINE statement* (ELSEIF expression THEN NEWLINE statement*)* (ELSE NEWLINE stat

for_stmt ::= FOR IDENT '=' expression TO expression (STEP expression)? NEWLINE
statement*
NEXT IDENT?

while_stmt ::= WHILE expression NEWLINE

53
 statement*
WEND

do_loop_stmt ::= DO (WHILE | UNTIL)? expression? NEWLINE

statement*
LOOP ((WHILE | UNTIL) expression)?

select_case_stmt ::= SELECT CASE expression NEWLINE

case_clause*
END SELECT

case_clause ::= CASE (ELSE | expression) NEWLINE statement*

goto_stmt ::= GOTO goto_target

gosub_stmt ::= GOSUB goto_target

return_stmt ::= RETURN

on_goto_stmt ::= ON expression GOTO goto_target (',' goto_target)*

goto_target ::= INTEGER | IDENT

(* Arrays *)
dim_stmt ::= DIM array_decl (',' array_decl)*

array_decl ::= IDENT '(' expression_list ')'

(* Procedures *)
sub_stmt ::= SUB IDENT ('(' param_list ')')? NEWLINE
statement*
END SUB

function_stmt ::= FUNCTION IDENT ('(' param_list ')')? NEWLINE

statement*
END FUNCTION

call_stmt ::= IDENT ('(' expression_list ')')? | IDENT expression_list

param_list ::= IDENT (',' IDENT)*

(* Data *)
data_stmt ::= DATA literal (',' literal)*

read_stmt ::= READ ident_list

restore_stmt ::= RESTORE goto_target?

54
(* File I/O *)
open_stmt ::= OPEN expression FOR (INPUT | OUTPUT | APPEND) AS '#' INTEGER

close_stmt ::= CLOSE '#' INTEGER

(* Miscellaneous *)
cls_stmt ::= CLS

end_stmt ::= END

stop_stmt ::= STOP

4.3.3 Expression Productions

expression ::= logical_or_expr

logical_or_expr ::= logical_xor_expr (OR logical_xor_expr)*

logical_xor_expr ::= logical_and_expr (XOR logical_and_expr)*

logical_and_expr ::= comparison_expr (AND comparison_expr)*

comparison_expr ::= additive_expr (('=' | '<>' | '<' | '>' | '<=' | '>=') additive_expr)?

additive_expr ::= multiplicative_expr (('+' | '-') multiplicative_expr)*

multiplicative_expr ::= power_expr (('*' | '/' | '\' | MOD) power_expr)*

power_expr ::= unary_expr ('^' power_expr)? (* right-associative *)

unary_expr ::= '-' unary_expr

| '+' unary_expr
| NOT unary_expr
| primary_expr

primary_expr ::= INTEGER

| FLOAT
| STRING
| IDENT ('(' expression_list ')')? (* variable or function call *)
| '(' expression ')'

expression_list ::= expression (',' expression)*

literal ::= INTEGER | FLOAT | STRING | '-' INTEGER | '-' FLOAT

4.3.4 Operator Precedence

From lowest to highest precedence:

55
Level Operators Associativity Description
1 OR Left Logical/bitwise OR
2 XOR Left Logical/bitwise XOR
3 AND Left Logical/bitwise AND
4 =, <>, <, >, <=, >= Left Comparison
5 +, - Left Addition, subtraction
6 *, /, \, MOD Left Multiplication, division,
integer division, modulo
7 ^ Right Exponentiation
8 -, +, NOT Right Unary negation, unary
plus, logical NOT

Note: Exponentiation (^) is right-associative, meaning 2 ^ 3 ^ 2 evaluates as 2 ^ (3 ^ 2) =

512, not (2 ^ 3) ^ 2 = 64.

4.3.5 Grammar Notes

1. Case Insensitivity: Keywords and identifiers are case-insensitive (PRINT = print = Print)
2. Optional Line Numbers: Line numbers are optional and serve as labels for GOTO/GOSUB
3. Statement Separators: Colons (:) can separate multiple statements on one line
4. Whitespace: Generally insignificant except in string literals
5. Comments: REM and ' introduce comments that extend to end of line

4.4 Parsing Strategy

xbasic64 uses two complementary parsing techniques:

4.4.1 Recursive Descent for Statements

For statements, the parser uses straightforward recursive descent:
fn parse_statement(&mut self) -> Result<Stmt, String> {
match [Link]() {
Token::Print => self.parse_print(),
Token::If => self.parse_if(),
Token::For => self.parse_for(),
// ... other statement types
Token::Ident(_) => self.parse_assignment_or_call(),
_ => Err("Unexpected token")
}
}
Each statement type has a dedicated parsing function that: 1. Consumes the leading keyword 2.
Parses the statement’s components recursively 3. Returns an AST node representing the statement
Example: Parsing FOR loops
fn parse_for(&mut self) -> Result<Stmt, String> {
[Link](); // consume FOR

56
 let var = self.expect_ident()?;
[Link](Token::Eq)?;
let start = self.parse_expression()?;
[Link](Token::To)?;
let end = self.parse_expression()?;

let step = if [Link]() == Token::Step {

[Link]();
Some(self.parse_expression()?)
} else {
None
};

// Parse body until NEXT

let body = self.parse_until(Token::Next)?;

Ok(Stmt::For { var, start, end, step, body })

}

4.4.2 Precedence Climbing for Expressions

For expressions, the parser uses precedence climbing (also called Pratt parsing), which elegantly
handles operator precedence and associativity:
fn parse_prec(&mut self, min_prec: u8) -> Result<Expr, String> {
let mut left = self.parse_unary()?;

while let Some((prec, op)) = binary_op_info([Link]()) {

if prec < min_prec {
break;
}
[Link]();

// Right-associative for power, left-associative otherwise

let next_min = if op == BinaryOp::Pow { prec } else { prec + 1 };
let right = self.parse_prec(next_min)?;

left = Expr::Binary { op, left: Box::new(left), right: Box::new(right) };

}
Ok(left)
}
How precedence climbing works:
1. Parse the left operand (a unary expression or primary)
2. Look at the next operator
3. If its precedence is too low, return the left operand
4. Otherwise, recursively parse the right operand with adjusted precedence
5. Combine left and right into a binary expression

57
 6. Repeat from step 2
Example: Parsing 2 + 3 * 4
parse_prec(min_prec=1):
left = 2
see '+' (prec=5 >= 1), consume it
right = parse_prec(min_prec=6):
left = 3
see '*' (prec=6 >= 6), consume it
right = parse_prec(min_prec=7):
left = 4
see EOF (no operator)
return 4
return Binary(Mul, 3, 4)
return Binary(Add, 2, Binary(Mul, 3, 4))
This automatically produces the correct tree: 2 + (3 * 4).

4.4.3 Handling Right-Associativity

For right-associative operators like exponentiation (^), the parser uses the same precedence level
for the recursive call instead of prec + 1:
let next_min = if op == BinaryOp::Pow { prec } else { prec + 1 };
This makes 2 ^ 3 ^ 4 parse as 2 ^ (3 ^ 4) instead of (2 ^ 3) ^ 4.

4.4.4 Error Recovery

The parser uses a simple error recovery strategy:
1. Immediate failure: Most errors cause immediate parsing failure
2. Error messages: Include the unexpected token and what was expected
3. No panic mode: The parser doesn’t attempt to skip tokens and continue
This approach is simple but effective for an educational compiler. Production compilers use more
sophisticated error recovery to report multiple errors in one pass.

4.5 Abstract Syntax Tree (AST)

The AST is the primary output of the parser and the input to the code generator. It’s a tree
structure where each node represents a language construct.

4.5.1 AST Node Types

xbasic64 defines two main categories of AST nodes:

[Link] Statement Nodes (Stmt)

Statements represent actions or declarations:

58
pub enum Stmt {
Label(u32), // Line number label

Let { // Variable assignment

name: String,
indices: Option<Vec<Expr>>, // For array assignment
value: Expr,
},

Print { // Output to console

items: Vec<PrintItem>,
newline: bool,
},

Input { // Read user input

prompt: Option<String>,
vars: Vec<String>,
},

LineInput { // Read entire line

prompt: Option<String>,
var: String,
},

If { // Conditional execution
condition: Expr,
then_branch: Vec<Stmt>,
else_branch: Option<Vec<Stmt>>,
},

For { // Counted loop

var: String,
start: Expr,
end: Expr,
step: Option<Expr>,
body: Vec<Stmt>,
},

While { // Pre-test loop

condition: Expr,
body: Vec<Stmt>,
},

DoLoop { // Flexible loop

condition: Option<Expr>,
cond_at_start: bool,
is_until: bool,
body: Vec<Stmt>,

59
},

SelectCase { // Multi-way branch

expr: Expr,
cases: Vec<(Option<Expr>, Vec<Stmt>)>,
},

Goto(GotoTarget), // Unconditional jump

Gosub(GotoTarget), // Subroutine call
Return, // Return from subroutine

OnGoto { // Computed jump

expr: Expr,
targets: Vec<GotoTarget>,
},

Dim { // Array declaration

arrays: Vec<ArrayDecl>,
},

Sub { // Subroutine definition

name: String,
params: Vec<String>,
body: Vec<Stmt>,
},

Function { // Function definition

name: String,
params: Vec<String>,
body: Vec<Stmt>,
},

Call { // Subroutine call

name: String,
args: Vec<Expr>,
},

Data(Vec<Literal>), // Inline data

Read(Vec<String>), // Read from DATA
Restore(Option<GotoTarget>), // Reset DATA pointer

Cls, // Clear screen

End, // Terminate program
Stop, // Stop execution

// File I/O
Open {
filename: Expr,

60
 mode: FileMode,
file_num: i32,
},
Close { file_num: i32 },
PrintFile {
file_num: i32,
items: Vec<PrintItem>,
newline: bool,
},
InputFile {
file_num: i32,
vars: Vec<String>,
},
}

[Link] Expression Nodes (Expr)

Expressions represent values and computations:
pub enum Expr {
Literal(Literal), // Constant value

Variable(String), // Variable reference

ArrayAccess { // Array element access

name: String,
indices: Vec<Expr>,
},

Unary { // Unary operation

op: UnaryOp,
operand: Box<Expr>,
},

Binary { // Binary operation

op: BinaryOp,
left: Box<Expr>,
right: Box<Expr>,
},

FnCall { // Function call

name: String,
args: Vec<Expr>,
},
}

61
[Link] Supporting Types
pub enum Literal {
Integer(i64),
Float(f64),
String(String),
}

pub enum UnaryOp {

Neg, // Negation (-)
Not, // Logical NOT
}

pub enum BinaryOp {

Add, Sub, Mul, Div, IntDiv, Mod, Pow, // Arithmetic
Eq, Ne, Lt, Gt, Le, Ge, // Comparison
And, Or, Xor, // Logical/bitwise
}

pub enum GotoTarget {

Line(u32), // Line number
Label(String), // Named label
}

pub enum FileMode {

Input,
Output,
Append,
}

pub struct ArrayDecl {

pub name: String,
pub dimensions: Vec<Expr>,
}

pub enum PrintItem {

Expr(Expr), // Expression to print
Tab, // Tab to next zone (comma)
Empty, // No separator (semicolon)
}

4.5.2 AST Design Principles

1. Semantic Focus: The AST represents meaning, not syntax. Keywords and punctuation are
implicit in node types.
2. Type Safety: Rust’s enum types ensure that each node has exactly the fields it needs.
3. Recursive Structure: Statements can contain expressions, expressions can contain other

62
 expressions, and some statements (like If) contain other statements.
4. Explicit Structure: Array subscripts, function arguments, and other lists are explicitly
represented as Vec<Expr>.
5. Optional Components: Optional parts (like STEP in FOR loops or ELSE in IF statements)
use Option<T>.

4.5.3 Example AST

BASIC Code:
10 FOR I = 1 TO 10
20 PRINT I; " squared is "; I * I
30 NEXT I
Resulting AST:
Program {
statements: [
Label(10),
For {
var: "I",
start: Literal(Integer(1)),
end: Literal(Integer(10)),
step: None,
body: [
Label(20),
Print {
items: [
Expr(Variable("I")),
Expr(Literal(String(" squared is "))),
Expr(Binary {
op: Mul,
left: Box::new(Variable("I")),
right: Box::new(Variable("I")),
}),
],
newline: true,
},
],
},
Label(30),
],
}
Notice how: - Line numbers become Label statements - The FOR loop structure is explicit with var,
start, end, and body - The PRINT statement’s semicolons become PrintItem::Empty (omitted
here for clarity) - The expression I * I becomes a Binary node with Mul operator

63
4.6 Parser Implementation Walkthrough
Let’s examine key parts of src/[Link] to see how the theory translates to code.

4.6.1 Parser Structure

pub struct Parser {
tokens: Vec<Token>, // Input token stream
pos: usize, // Current position
last_loop_condition: Option<Expr>, // For DO...LOOP WHILE/UNTIL
last_elseif_condition: Option<Expr>, // For ELSEIF handling
}
The parser maintains: - The token stream from the lexer - Current position in the stream - State
for handling complex constructs (DO loops, ELSEIF)

4.6.2 Core Parsing Functions

Peeking and advancing:
fn peek(&self) -> &Token {
[Link]([Link]).unwrap_or(&Token::Eof)
}

fn advance(&mut self) -> Token {

let tok = [Link]([Link]).cloned().unwrap_or(Token::Eof);
[Link] += 1;
tok
}

fn expect(&mut self, expected: Token) -> Result<(), String> {

let tok = [Link]();
if std::mem::discriminant(&tok) == std::mem::discriminant(&expected) {
Ok(())
} else {
Err(format!("Expected {:?}, got {:?}", expected, tok))
}
}
These utility functions provide: - peek(): Look at current token without consuming it - advance():
Consume and return current token - expect(): Verify the current token matches expected type
Skipping newlines:
fn skip_newlines(&mut self) {
while matches!([Link](), Token::Newline) {
[Link]();
}
}
BASIC allows flexible newline placement, so the parser skips them between statements.

64
4.6.3 Statement Parsing Examples
Parsing LET statements:
fn parse_let(&mut self) -> Result<Stmt, String> {
[Link](); // consume LET
self.parse_assignment()
}

fn parse_assignment(&mut self) -> Result<Stmt, String> {

let name = if let Token::Ident(n) = [Link]() {
n
} else {
return Err("Expected variable name".to_string());
};

// Check for array subscript

let indices = if matches!([Link](), Token::LParen) {
[Link]();
let idx = self.parse_expr_list()?;
[Link](Token::RParen)?;
Some(idx)
} else {
None
};

[Link](Token::Eq)?;
let value = self.parse_expression()?;

Ok(Stmt::Let { name, indices, value })

}
This handles both simple assignment (X = 42) and array assignment (A(5) = 100).
Parsing IF statements:
fn parse_if(&mut self) -> Result<Stmt, String> {
[Link](); // consume IF
let condition = self.parse_expression()?;
[Link](Token::Then)?;

// Check for single-line IF

if !matches!([Link](), Token::Newline | Token::Eof) {
let then_branch = vec![self.parse_statement()?];
let else_branch = if matches!([Link](), Token::Else) {
[Link]();
Some(vec![self.parse_statement()?])
} else {
None
};

65
 return Ok(Stmt::If { condition, then_branch, else_branch });
}

// Block IF - parse body

self.skip_newlines();
let (then_branch, else_branch) = self.parse_if_body()?;

Ok(Stmt::If { condition, then_branch, else_branch })

}
This handles both single-line (IF X > 0 THEN PRINT X) and block form (IF...THEN...END IF).
Parsing FOR loops:
fn parse_for(&mut self) -> Result<Stmt, String> {
[Link](); // consume FOR
let var = if let Token::Ident(n) = [Link]() {
n
} else {
return Err("Expected variable name after FOR".to_string());
};

[Link](Token::Eq)?;
let start = self.parse_expression()?;
[Link](Token::To)?;
let end = self.parse_expression()?;

let step = if matches!([Link](), Token::Step) {

[Link]();
Some(self.parse_expression()?)
} else {
None
};

self.skip_newlines();

// Parse body until NEXT

let mut body = Vec::new();
loop {
match self.parse_statement() {
Ok(stmt) => [Link](stmt),
Err(e) if e == "NEXT" => break,
Err(e) => return Err(e),
}
self.skip_newlines();
}

Ok(Stmt::For { var, start, end, step, body })

}

66
The parser collects statements until it encounters NEXT, using error returns as a signaling mechanism
for loop terminators.

4.6.4 Expression Parsing with Precedence Climbing

Main expression entry point:
fn parse_expression(&mut self) -> Result<Expr, String> {
self.parse_prec(1) // Start at lowest precedence
}
Precedence climbing algorithm:
fn parse_prec(&mut self, min_prec: u8) -> Result<Expr, String> {
// Handle NOT prefix operator
let mut left = if matches!([Link](), Token::Not) {
[Link]();
let operand = self.parse_prec(min_prec)?;
Expr::Unary { op: UnaryOp::Not, operand: Box::new(operand) }
} else {
self.parse_unary()?
};

// Parse binary operators with precedence climbing

while let Some((prec, op)) = binary_op_info([Link]()) {
if prec < min_prec {
break;
}
[Link]();

// Power is right-associative; others are left-associative

let next_min = if op == BinaryOp::Pow { prec } else { prec + 1 };
let right = self.parse_prec(next_min)?;

left = Expr::Binary {
op,
left: Box::new(left),
right: Box::new(right),
};
}
Ok(left)
}
Operator precedence table:
fn binary_op_info(token: &Token) -> Option<(u8, BinaryOp)> {
match token {
Token::Or => Some((1, BinaryOp::Or)),
Token::Xor => Some((3, BinaryOp::Xor)),
Token::And => Some((2, BinaryOp::And)),

67
 Token::Eq => Some((4, BinaryOp::Eq)),
Token::Ne => Some((4, BinaryOp::Ne)),
// ... other comparison operators at level 4
Token::Plus => Some((5, BinaryOp::Add)),
Token::Minus => Some((5, BinaryOp::Sub)),
Token::Star => Some((6, BinaryOp::Mul)),
Token::Slash => Some((6, BinaryOp::Div)),
// ... other multiplicative operators at level 6
Token::Caret => Some((7, BinaryOp::Pow)),
_ => None,
}
}
Parsing unary expressions:
fn parse_unary(&mut self) -> Result<Expr, String> {
match [Link]() {
Token::Minus => {
[Link]();
let operand = self.parse_unary()?;
Ok(Expr::Unary { op: UnaryOp::Neg, operand: Box::new(operand) })
}
Token::Plus => {
[Link]();
self.parse_unary() // Unary plus is a no-op
}
_ => self.parse_primary(),
}
}
Parsing primary expressions:
fn parse_primary(&mut self) -> Result<Expr, String> {
match [Link]().clone() {
Token::Integer(n) => {
[Link]();
Ok(Expr::Literal(Literal::Integer(n)))
}
Token::Float(f) => {
[Link]();
Ok(Expr::Literal(Literal::Float(f)))
}
Token::String(s) => {
[Link]();
Ok(Expr::Literal(Literal::String(s)))
}
Token::Ident(name) => {
[Link]();
if matches!([Link](), Token::LParen) {
[Link]();

68
 let args = self.parse_expr_list()?;
[Link](Token::RParen)?;
Ok(Expr::FnCall { name, args })
} else {
Ok(Expr::Variable(name))
}
}
Token::LParen => {
[Link]();
let expr = self.parse_expression()?;
[Link](Token::RParen)?;
Ok(expr)
}
tok => Err(format!("Unexpected token in expression: {:?}", tok)),
}
}
Primary expressions are the “atoms” of expressions: literals, variables, function calls, and paren-
thesized expressions.

4.6.5 Parsing Complex Constructs

SELECT CASE statements:
fn parse_select_case(&mut self) -> Result<Stmt, String> {
[Link](); // consume SELECT
[Link](Token::Case)?;
let expr = self.parse_expression()?;
self.skip_newlines();

let mut cases: Vec<(Option<Expr>, Vec<Stmt>)> = Vec::new();

loop {
// Check for END SELECT
if matches!([Link](), Token::End | Token::EndSelect) {
if matches!([Link](), Token::End) {
[Link]();
[Link](Token::Select)?;
} else {
[Link]();
}
break;
}

[Link](Token::Case)?;

// Check for CASE ELSE

let case_value = if matches!([Link](), Token::Else) {
[Link]();

69
 None
} else {
Some(self.parse_expression()?)
};

self.skip_newlines();

// Parse case body until next CASE or END SELECT

let mut body = Vec::new();
loop {
match [Link]() {
Token::Case | Token::End | Token::EndSelect | Token::Eof => break,
_ => {}
}
match self.parse_statement() {
Ok(stmt) => [Link](stmt),
Err(e) => return Err(e),
}
self.skip_newlines();
}

[Link]((case_value, body));
}

Ok(Stmt::SelectCase { expr, cases })

}
This demonstrates how the parser handles multi-part constructs by: 1. Parsing the discriminant
expression 2. Looping to collect case clauses 3. Distinguishing between valued cases and CASE ELSE
4. Collecting statements for each case body

4.6.6 Parse Tree to AST Transformation

The parser directly builds AST nodes rather than first building a parse tree. This is more efficient
and simpler. For example, when parsing:
IF X > 0 THEN PRINT X
The parser: 1. Recognizes IF token → calls parse_if() 2. Calls parse_expression() →
builds Binary { op: Gt, left: Variable("X"), right: Literal(0) } 3. Expects THEN token
4. Calls parse_statement() → builds Print { items: [Variable("X")] } 5. Returns If {
condition: ..., then_branch: [...], else_branch: None }
No intermediate parse tree is created; the AST is built directly during parsing.

4.6.7 Example: Parsing a Complete Program

Input:
10 INPUT "Enter N: ", N
20 FOR I = 1 TO N

70
30 PRINT I * I
40 NEXT I
Parsing steps:
1. parse() starts, calls parse_statement() repeatedly
2. First statement: 10 INPUT...
• Sees Token::LineNumber(10) → creates Label(10)
• Sees Token::Input → calls parse_input()
• Parses prompt string and variable list
• Returns Input { prompt: Some("Enter N: "), vars: ["N"] }
3. Second statement: 20 FOR...
• Sees Token::LineNumber(20) → creates Label(20)
• Sees Token::For → calls parse_for()
• Parses loop variable, bounds, and body
• Body contains labels 30 and 40, and PRINT statement
• Returns For { var: "I", start: Literal(1), end: Variable("N"), step:
None, body: [...] }
4. parse() returns Program { statements: [Label(10), Input{...}, Label(20),
For{...}] }
Resulting AST:
Program {
statements: [
Label(10),
Input {
prompt: Some("Enter N: "),
vars: vec!["N".to_string()],
},
Label(20),
For {
var: "I".to_string(),
start: Literal(Integer(1)),
end: Variable("N".to_string()),
step: None,
body: vec![
Label(30),
Print {
items: vec![
PrintItem::Expr(Binary {
op: Mul,
left: Box::new(Variable("I".to_string())),
right: Box::new(Variable("I".to_string())),
}),
],
newline: true,
},
Label(40),
],

71
 },
],
}

4.7 Summary
Syntax analysis transforms a flat token stream into a hierarchical AST that represents the program’s
structure. Key takeaways:
• Context-free grammars define the syntax of programming languages
• Recursive descent parsing is simple and effective for predictable grammars
• Precedence climbing elegantly handles operator precedence and associativity
• ASTs focus on semantic structure, omitting syntactic noise
• Direct AST construction is more efficient than building parse trees first
The xbasic64 parser demonstrates these concepts in a clean, understandable implementation that’s
perfect for learning compiler design.

4.8 Further Reading

• Lexical Analysis - How tokens are produced
• Semantic Analysis - Type checking and symbol management
• Code Generation - Translating AST to assembly
• Language Reference - Complete BASIC grammar reference
• Theory Comparison - How this relates to compiler textbooks
External Resources: - Dragon Book Chapter 4: Syntax Analysis - “Crafting Interpreters” by
Robert Nystrom - Excellent explanation of Pratt parsing - “Engineering a Compiler” by Cooper &
Torczon - Comprehensive parsing coverage

4.9 Navigation: ← Lexical Analysis | Home | Next: Semantic

Analysis →
title: “Semantic Analysis” chapter: 5 prev: “[Link]” next: “[Link]”
dragon_book_chapters: [5, 6] difficulty: intermediate estimated_time: “50 minutes” —

72
Chapter 5

Semantic Analysis

5.1 Introduction
Semantic analysis is the phase of compilation that checks whether a syntactically correct program
makes sense according to the language’s rules. While the parser ensures the program follows gram-
matical structure, semantic analysis ensures it follows meaning-based rules like type compatibility,
variable declarations, and scope resolution.
In xbasic64, semantic analysis is integrated into the code generation phase rather than being a
separate pass. This document explains the semantic rules enforced by the compiler, focusing on
the type system, type coercion, and symbol management.

5.2 Table of Contents

• What is Semantic Analysis?
• The Type System
• Type Coercion Rules
• Symbol Table Management
• Semantic Analysis Examples
• Summary
• Further Reading

5.3 What is Semantic Analysis?

5.3.1 Purpose of Semantic Analysis
Semantic analysis bridges the gap between syntax and code generation. It answers questions like:
• Type checking: Are operations applied to compatible types?
• Type coercion: When types don’t match exactly, can they be converted automatically?
• Variable resolution: Does a variable exist? What is its type?
• Scope checking: Is a variable accessible in the current context?
• Declaration checking: Are arrays properly declared before use?

73
In traditional compilers, semantic analysis is a separate phase that: 1. Walks the AST 2. Builds
symbol tables 3. Annotates the AST with type information 4. Reports semantic errors

5.3.2 Semantic Analysis in xbasic64

xbasic64 takes a simpler approach: semantic analysis happens during code generation. As
the code generator walks the AST:
• Type inference: Expression types are computed on-the-fly using expr_type()
• Type coercion: Automatic conversions are inserted using gen_coercion()
• Symbol management: Variables are allocated in the symbol table on first use
• Scope tracking: Local vs. global variables are distinguished by procedure context
This integrated approach works well for BASIC because: - BASIC has implicit variable declaration
(variables spring into existence on first use) - The type system is simple with straightforward
coercion rules - There’s no need for complex type inference or constraint solving
Trade-offs: - Simpler implementation: Fewer passes over the AST - Less error reporting:
Semantic errors are caught during code generation, not before - Tighter coupling: Semantic rules
are embedded in code generation logic
For an educational compiler, this approach provides clarity by showing how semantic concepts
directly influence code generation.

5.3.3 What Semantic Analysis Checks

In xbasic64, semantic analysis enforces:
1. Type compatibility: Binary operations require compatible operand types
2. Automatic coercion: Numeric types are promoted following BASIC’s hierarchy
3. Variable types: Each variable has a type determined by its suffix
4. Array bounds: Array subscripts must be numeric (checked at runtime)
5. Function signatures: Built-in functions expect specific argument types
6. Scope rules: Local variables in procedures don’t conflict with globals
What it doesn’t check (due to BASIC’s permissive nature): - Variable declaration before use (im-
plicit declaration) - Array dimension declaration (runtime allocation) - Type mismatches between
strings and numbers (runtime error) - Unreachable code or unused variables

5.4 The Type System

5.4.1 BASIC’s Five Data Types
xbasic64 supports five data types, following GW-BASIC and QuickBASIC conventions:

Type Suffix Size Description Range/Precision

Integer % 16-bit Signed integer -32,768 to 32,767
Long & 32-bit Signed long integer -2,147,483,648 to
2,147,483,647
Single ! 32-bit Single-precision float ~7 digits precision
Double # 64-bit Double-precision float ~15 digits precision

74
Type Suffix Size Description Range/Precision
String $ Variable Character string Heap-allocated, (pointer,
length) pair

5.4.2 Type Suffixes

Variable types are determined by their suffix character:
Count% = 42 ' Integer (16-bit)
Total& = 1000000 ' Long (32-bit)
Price! = 19.99 ' Single (32-bit float)
Value# = 3.14159 ' Double (64-bit float)
Name$ = "Alice" ' String
Default type: Unsuffixed numeric variables are Double (#):
X = 3.14159 ' X is Double
Y = 100 ' Y is Double (not Integer!)
This differs from some BASIC dialects where unsuffixed variables default to Single.

5.4.3 Type Representation in Memory

[Link] Integer Types
• Integer (%): Stored as 16-bit signed value, but computed as 32-bit
– Stack storage: 8 bytes (for alignment)
– Register: eax (low 16 bits used)
– Sign-extended when loaded
• Long (&): Stored and computed as 32-bit signed value
– Stack storage: 8 bytes (for alignment)
– Register: eax

[Link] Floating-Point Types

• Single (!): 32-bit IEEE 754 float
– Stack storage: 8 bytes (for alignment)
– Register: xmm0 (SSE)
– Instructions: movss, addss, cvtsi2ss, etc.
• Double (#): 64-bit IEEE 754 float
– Stack storage: 8 bytes
– Register: xmm0 (SSE)
– Instructions: movsd, addsd, cvtsi2sd, etc.

[Link] String Type

Strings are represented as (pointer, length) pairs, not null-terminated:
• Pointer: 8-byte address to character data (heap-allocated)
• Length: 8-byte integer count of characters
• Storage: Two consecutive 8-byte slots on the stack

75
 – [rbp + offset]: pointer
– [rbp + offset - 8]: length
Example memory layout:
High addresses
�������������������
� String pointer � [rbp - 8] (rax)
�������������������
� String length � [rbp - 16] (rdx)
�������������������
� Integer var � [rbp - 24] (eax)
�������������������
Low addresses
This representation allows: - Efficient substring operations (no copying) - O(1) length queries -
Embedded null characters

5.4.4 Type Determination

The compiler determines expression types using the expr_type() function:
fn expr_type(&self, expr: &Expr) -> DataType {
match expr {
Expr::Literal(lit) => match lit {
Literal::Integer(_) => DataType::Long, // Literals are Long
Literal::Float(_) => DataType::Double,
Literal::String(_) => DataType::String,
},
Expr::Variable(name) => DataType::from_suffix(name),
Expr::Binary { left, right, op } => {
let lt = self.expr_type(left);
let rt = self.expr_type(right);
self.promote_types(lt, rt, *op)
},
// ... other cases
}
}
Key points: - Integer literals are treated as Long (not Integer) - Variable types come from their
suffix - Binary expression types are determined by type promotion rules

5.5 Type Coercion Rules

5.5.1 The Type Hierarchy
BASIC performs automatic type promotion following this hierarchy:
Integer (%) → Long (&) → Single (!) → Double (#)
When operands of different types are combined, both are promoted to the wider type. This ensures
no precision is lost during computation.

76
Example:
X% = 10 ' Integer
Y& = 20 ' Long
Z = X% + Y& ' Result is Long (both promoted to Long)

5.5.2 Type Promotion Rules

The promote_types() function determines the result type of binary operations:
fn promote_types(&self, left: DataType, right: DataType, op: BinaryOp) -> DataType {
// Special cases first

// Comparison operators always return Long (boolean as -1 or 0)

if matches!(op, BinaryOp::Eq | BinaryOp::Ne | ...) {
return DataType::Long;
}

// Division (/) always produces Double

if op == BinaryOp::Div {
return DataType::Double;
}

// Integer division (\) always produces Long

if op == BinaryOp::IntDiv {
return DataType::Long;
}

// MOD produces Long

if op == BinaryOp::Mod {
return DataType::Long;
}

// Power (^) always produces Double (uses libm pow())

if op == BinaryOp::Pow {
return DataType::Double;
}

// String concatenation
if left == DataType::String && right == DataType::String {
return DataType::String;
}

// Numeric promotion: widest type wins

match (left, right) {
(DataType::Double, _) | (_, DataType::Double) => DataType::Double,
(DataType::Single, _) | (_, DataType::Single) => DataType::Single,
(DataType::Long, _) | (_, DataType::Long) => DataType::Long,
_ => DataType::Integer,

77
 }
}

5.5.3 Special Operator Rules

[Link] Division Operators
BASIC has two division operators with different semantics:
Regular division (/): Always produces Double
PRINT 7 / 2 ' Prints 3.5 (Double)
PRINT 10% / 3% ' Prints 3.333... (Double, even with Integer operands)
Integer division (\): Always produces Long
PRINT 7 \ 2 ' Prints 3 (Long)
PRINT 10.5 \ 3.2 ' Prints 3 (operands truncated to integers first)

[Link] Exponentiation (^)

Power operations always produce Double and use the C library pow() function:
PRINT 2 ^ 3 ' Prints 8.0 (Double)
PRINT 2% ^ 3% ' Prints 8.0 (Double, even with Integer operands)

[Link] Comparison Operators

Comparisons return Long with boolean semantics: - True: -1 (all bits set) - False: 0
X = (5 > 3) ' X = -1 (true)
Y = (2 > 4) ' Y = 0 (false)
This allows bitwise operations on boolean results:
IF (A > 0) AND (B > 0) THEN ' Bitwise AND of -1 and -1 = -1 (true)

[Link] Logical/Bitwise Operators

AND, OR, XOR, NOT operate on integer types:
Flags% = &H01 OR &H04 ' Bitwise OR: 0x01 | 0x04 = 0x05
IF (X > 0) AND (Y > 0) THEN ' Logical AND (operands are -1 or 0)
For logical operations, operands are converted to integers if necessary.

5.5.4 Coercion Implementation

The gen_coercion() function generates assembly code to convert between types:
fn gen_coercion(&mut self, from: DataType, to: DataType) {
match (from, to) {
// Integer to Long (sign extension)
(DataType::Integer, DataType::Long) => {
[Link](" movsx eax, ax"); // Sign-extend 16-bit to 32-bit

78
 }

// Integer/Long to Single
(DataType::Integer | DataType::Long, DataType::Single) => {
[Link](" cvtsi2ss xmm0, eax");
}

// Integer/Long to Double
(DataType::Integer | DataType::Long, DataType::Double) => {
[Link](" cvtsi2sd xmm0, eax");
}

// Single to Double
(DataType::Single, DataType::Double) => {
[Link](" cvtss2sd xmm0, xmm0");
}

// Double to Single
(DataType::Double, DataType::Single) => {
[Link](" cvtsd2ss xmm0, xmm0");
}

// Single/Double to Integer/Long (truncate)

(DataType::Single, DataType::Integer | DataType::Long) => {
[Link](" cvttss2si eax, xmm0"); // Truncate toward zero
}
(DataType::Double, DataType::Integer | DataType::Long) => {
[Link](" cvttsd2si eax, xmm0"); // Truncate toward zero
}

// Same type - no conversion

_ => {}
}
}
Key instructions: - cvtsi2ss / cvtsi2sd: Convert signed integer to float - cvtss2sd / cvtsd2ss:
Convert between Single and Double - cvttss2si / cvttsd2si: Convert float to integer (truncate)
- movsx: Sign-extend integer

5.5.5 Coercion in Binary Expressions

When evaluating binary expressions, both operands are coerced to a common “working type”:
fn gen_binary_expr(&mut self, op: BinaryOp, left: &Expr, right: &Expr) -> DataType {
// Determine result type
let result_type = self.promote_types(
self.expr_type(left),
self.expr_type(right),
op

79
 );

// Determine working type (may differ for special operators)

let work_type = if matches!(op, BinaryOp::IntDiv | BinaryOp::Mod) {
// Integer operations: promote to common type, then convert to int
self.promote_types(self.expr_type(left), self.expr_type(right), BinaryOp::Add)
} else {
result_type
};

// Evaluate left operand and coerce to work type

let left_type = self.gen_expr(left);
self.gen_coercion(left_type, work_type);

// Save left result (16-byte aligned for ABI compliance)

[Link](" sub rsp, 16");
if work_type.is_integer() {
[Link](" mov [rsp], eax");
} else {
[Link](" movsd [rsp], xmm0");
}

// Evaluate right operand and coerce to work type

let right_type = self.gen_expr(right);
self.gen_coercion(right_type, work_type);

// Move right to secondary register and restore left

if work_type.is_integer() {
[Link](" mov ecx, eax"); // Right operand
[Link](" mov eax, [rsp]"); // Left operand
} else {
[Link](" movsd xmm1, xmm0"); // Right operand
[Link](" movsd xmm0, [rsp]"); // Left operand
}
[Link](" add rsp, 16");

// Perform operation (add, mul, etc.)

// ...

result_type
}
Example: X% + Y#
1. Determine types: X% is Integer, Y# is Double
2. Promote: Result type is Double
3. Evaluate X% → Integer in eax
4. Coerce to Double: cvtsi2sd xmm0, eax
5. Save: movsd [rsp], xmm0

80
 6. Evaluate Y# → Double in xmm0
7. Coerce to Double: (already Double, no-op)
8. Restore: movsd xmm1, xmm0 (right), movsd xmm0, [rsp] (left)
9. Add: addsd xmm0, xmm1
10. Result: Double in xmm0

5.5.6 Implicit vs. Explicit Conversion

Implicit conversion (automatic):
X% = 10
Y# = X% + 3.14 ' X% implicitly converted to Double
Explicit conversion (using functions):
X# = 3.14159
Y% = CINT(X#) ' Explicitly convert to Integer (rounds)
Z& = CLNG(X#) ' Explicitly convert to Long (rounds)
Conversion functions: - CINT(x): Convert to Integer (rounds to nearest) - CLNG(x): Convert to
Long (rounds to nearest) - CSNG(x): Convert to Single - CDBL(x): Convert to Double
Truncation vs. Rounding: - Implicit coercion uses truncation (cvttsd2si) - Explicit
CINT/CLNG use rounding (cvtsd2si)
X# = 3.7
Y% = X# ' Y% = 3 (truncated)
Z% = CINT(X#) ' Z% = 4 (rounded)

5.6 Symbol Table Management

5.6.1 What is a Symbol Table?
A symbol table is a data structure that maps identifiers (variable names, function names) to their
attributes (type, storage location, scope). It’s the compiler’s “memory” of what variables exist and
where they’re stored.
In xbasic64, the symbol table tracks: - Variable name: The identifier (e.g., "COUNT%") - Data
type: Integer, Long, Single, Double, or String - Stack offset: Where the variable is stored relative
to rbp - Scope: Global (module-level) or local (procedure-level)

5.6.2 Symbol Table Structure

The code generator maintains two symbol tables:
struct VarInfo {
offset: i32, // Stack offset (negative from rbp)
data_type: DataType, // Variable type
}

struct CodeGen {
vars: HashMap<String, VarInfo>, // Global variables

81
 proc_vars: HashMap<String, VarInfo>, // Local variables (current procedure)
current_proc: Option<String>, // Current procedure name
stack_offset: i32, // Current stack allocation position
// ...
}
Key points: - vars: Global symbol table for module-level variables - proc_vars: Local symbol
table for the current procedure - current_proc: Tracks whether we’re inside a SUB/FUNCTION
- stack_offset: Grows downward (negative) as variables are allocated

5.6.3 Variable Storage Strategy

All variables are stored on the stack in the current function’s stack frame:
High addresses
�����������������������
� Return address � ← pushed by call
�����������������������
� Saved rbp � ← push rbp; mov rbp, rsp
����������������������� ← rbp points here
� Variable 1 � [rbp - 8]
� Variable 2 � [rbp - 16]
� Variable 3 � [rbp - 24]
� ... �
����������������������� ← rsp after prologue
Low addresses
Allocation rules: - Each variable gets 8 bytes regardless of type (for alignment) - Integer (16-bit)
uses only 2 bytes but occupies 8-byte slot - Long (32-bit) uses 4 bytes but occupies 8-byte slot -
Single (32-bit) uses 4 bytes but occupies 8-byte slot - Double (64-bit) uses full 8 bytes - String uses
16 bytes (two 8-byte slots for pointer and length)
Why 8 bytes? - Simplifies offset calculation (all offsets are multiples of 8) - Maintains 8-byte
alignment for all variables - Matches x86-64 natural word size

5.6.4 Implicit Variable Declaration

BASIC uses implicit declaration: variables spring into existence on first use. The compiler
allocates storage when a variable is first referenced:
X = 42 ' X is created here (type: Double, default)
Y% = 10 ' Y% is created here (type: Integer, from suffix)
PRINT Z# ' Z# is created here (type: Double, from suffix)
The get_var_info() function handles this:
fn get_var_info(&mut self, name: &str) -> VarInfo {
// Check local variables first (if in procedure)
if self.current_proc.is_some() {
if let Some(info) = self.proc_vars.get(name) {
return [Link]();
}

82
 }

// Check global variables

if let Some(info) = [Link](name) {
return [Link]();
}

// Variable doesn't exist - allocate it

let data_type = DataType::from_suffix(name);
self.stack_offset -= 8; // Allocate 8 bytes
let offset = self.stack_offset;

let info = VarInfo { offset, data_type };

// Store in appropriate symbol table

if self.current_proc.is_some() {
self.proc_vars.insert(name.to_string(), [Link]());
} else {
[Link](name.to_string(), [Link]());
}

info
}
Allocation process: 1. Check if variable exists in local scope (if in procedure) 2. Check if
variable exists in global scope 3. If not found, allocate new storage: - Determine type from suffix -
Decrement stack_offset by 8 - Create VarInfo entry - Insert into appropriate symbol table

5.6.5 Scope Rules

xbasic64 supports two scopes:

[Link] Global Scope

Variables declared at module level are global and accessible everywhere:
X = 10 ' Global variable

SUB PrintX
PRINT X ' Can access global X
END SUB

PrintX ' Prints 10

[Link] Local Scope

Variables declared inside SUB or FUNCTION are local to that procedure:
X = 10 ' Global X

83
SUB Test
X = 20 ' Local X (shadows global)
PRINT X ' Prints 20 (local)
END SUB

Test
PRINT X ' Prints 10 (global unchanged)
Shadowing: Local variables with the same name as globals hide the global variable within the
procedure.

[Link] Procedure Parameters

Parameters are local variables initialized from arguments:
SUB Add(A, B)
Result = A + B ' A, B are local parameters
PRINT Result ' Result is local variable
END SUB

Add 5, 10 ' Passes 5 and 10 to A and B

Parameters are stored at the beginning of the local variable area and initialized from registers
(System V AMD64 ABI).

5.6.6 Symbol Resolution Algorithm

When the compiler encounters a variable reference, it resolves it using this algorithm:
1. IF inside a procedure THEN
a. Check local symbol table (proc_vars)
b. If found, return local variable info
END IF

2. Check global symbol table (vars)

3. If found, return global variable info

4. Variable not found - allocate new variable:

a. Determine type from suffix
b. Allocate stack space
c. Add to appropriate symbol table (local if in procedure, else global)
d. Return new variable info
Example:
X = 100 ' Allocates global X (Double)

SUB Test
Y = 200 ' Allocates local Y (Double)
X = 300 ' Allocates local X (shadows global)
PRINT X, Y ' Uses local X and local Y

84
END SUB

Test
PRINT X ' Uses global X (still 100)
PRINT Y ' Allocates global Y (was not visible outside Test)

5.6.7 Array Storage

Arrays are more complex than simple variables. The symbol table stores array metadata:
struct ArrayInfo {
ptr_offset: i32, // Stack offset where array pointer is stored
dim_offsets: Vec<i32>, // Stack offsets for dimension bounds
}

struct CodeGen {
arrays: HashMap<String, ArrayInfo>, // Array metadata
// ...
}
Array allocation:
DIM A(10) ' Allocate array with 11 elements (0-10)
Generated code: 1. Allocate space for array pointer on stack 2. Allocate space for dimension
bounds on stack 3. Call runtime function to allocate heap memory 4. Store pointer and bounds in
stack slots
Array access:
A(5) = 42 ' Store to array element
X = A(5) ' Load from array element
Generated code: 1. Load array pointer from stack 2. Load dimension bounds from stack 3.
Evaluate subscript expression 4. Calculate element address: base + (index * element_size)
5. Load/store value at calculated address

5.6.8 Variable Lifetime

Global variables: Live for the entire program execution - Allocated in main function prologue -
Deallocated in main function epilogue (implicitly by stack unwinding)
Local variables: Live for the duration of the procedure call - Allocated in procedure prologue -
Deallocated in procedure epilogue (implicitly by leave instruction)
Heap-allocated data (strings, arrays): Managed by runtime library - Allocated by runtime func-
tions (_rt_alloc) - Deallocated by runtime functions (garbage collection or explicit free)

5.6.9 Symbol Table Example

Consider this program:
X = 10 ' Global X (Double)
Y% = 20 ' Global Y% (Integer)

85
SUB Test(A)
B = 30 ' Local B (Double)
X = 40 ' Local X (shadows global)
PRINT A, B, X, Y%
END SUB

Test 50
PRINT X, Y%
Symbol tables after compilation:
Global symbol table (vars):
"X" -> VarInfo { offset: -8, data_type: Double }
"Y%" -> VarInfo { offset: -16, data_type: Integer }
Local symbol table for Test (proc_vars when inside Test):
"A" -> VarInfo { offset: -8, data_type: Double } (parameter)
"B" -> VarInfo { offset: -16, data_type: Double }
"X" -> VarInfo { offset: -24, data_type: Double } (shadows global)
Variable resolution in PRINT A, B, X, Y%: - A: Found in proc_vars → local parameter - B:
Found in proc_vars → local variable - X: Found in proc_vars → local variable (shadows global) -
Y%: Not in proc_vars, found in vars → global variable

5.6.10 Case Insensitivity

BASIC is case-insensitive, so the lexer converts all identifiers to uppercase before they reach the
symbol table:
MyVar = 10
myvar = 20 ' Same variable as MyVar
MYVAR = 30 ' Same variable as MyVar
All three references resolve to "MYVAR" in the symbol table.

5.7 Semantic Analysis Examples

5.7.1 Example 1: Type Coercion in Mixed Expressions
BASIC Code:
A% = 10 ' Integer
B& = 20 ' Long
C! = 3.5 ' Single
D# = 2.5 ' Double

Result = A% + B& * C! / D#
Type Analysis:
Step-by-step evaluation of A% + B& * C! / D#:

86
 1. B& * C!:
• Left: Long, Right: Single
• Promote to: Single (Long → Single)
• Result: Single
2. (B& * C!) / D#:
• Left: Single, Right: Double
• Special rule: / always produces Double
• Promote to: Double (Single → Double)
• Result: Double
3. A% + ((B& * C!) / D#):
• Left: Integer, Right: Double
• Promote to: Double (Integer → Double)
• Result: Double
Generated Assembly (simplified):
; A% + B& * C! / D#

; Evaluate B& * C!
mov eax, DWORD PTR [rbp-16] ; Load B& (Long)
cvtsi2ss xmm0, eax ; Convert to Single
movss xmm1, DWORD PTR [rbp-24] ; Load C! (Single)
mulss xmm0, xmm1 ; Multiply (Single)

; Save intermediate result

sub rsp, 16
movss [rsp], xmm0

; Evaluate D#
movsd xmm0, QWORD PTR [rbp-32] ; Load D# (Double)

; Restore left operand and convert to Double

cvtss2sd xmm1, DWORD PTR [rsp] ; Convert Single to Double
add rsp, 16

; Divide (always produces Double)

divsd xmm1, xmm0 ; xmm1 / xmm0
movsd xmm0, xmm1 ; Result in xmm0

; Save intermediate result

sub rsp, 16
movsd [rsp], xmm0

; Evaluate A%
movsx eax, WORD PTR [rbp-8] ; Load A% (Integer, sign-extend)
cvtsi2sd xmm0, eax ; Convert to Double

; Restore and add

movsd xmm1, [rsp] ; Restore previous result

87
add rsp, 16
addsd xmm0, xmm1 ; Add (Double)

; Store result (Result is Double by default)

movsd QWORD PTR [rbp-40], xmm0
Key observations: - Each operation promotes operands to a common type - Division forces
conversion to Double - Intermediate results are saved on the stack - Final result is Double (widest
type in expression)

5.7.2 Example 2: Integer Division and Modulo

BASIC Code:
X# = 17.8
Y# = 5.2

IntDiv = X# \ Y# ' Integer division

Remainder = X# MOD Y#
Type Analysis:
For X# \ Y#: 1. Both operands are Double 2. Integer division (\) requires integer operands 3.
Convert both to Long (truncate): 17.8 → 17, 5.2 → 5 4. Perform integer division: 17 5 = 3 5.
Result type: Long
For X# MOD Y#: 1. Both operands are Double 2. MOD requires integer operands 3. Convert both
to Long (truncate): 17.8 → 17, 5.2 → 5 4. Perform modulo: 17 MOD 5 = 2 5. Result type: Long
Generated Assembly (simplified):
; X# \ Y# (integer division)

; Load X# and convert to integer

movsd xmm0, QWORD PTR [rbp-8] ; Load X# (17.8)
cvttsd2si eax, xmm0 ; Truncate to Long (17)

; Save left operand

sub rsp, 16
mov [rsp], eax

; Load Y# and convert to integer

movsd xmm0, QWORD PTR [rbp-16] ; Load Y# (5.2)
cvttsd2si ecx, xmm0 ; Truncate to Long (5)

; Restore left operand

mov eax, [rsp]
add rsp, 16

; Perform integer division

cdq ; Sign-extend eax to edx:eax

88
idiv ecx ; eax = eax / ecx (17 / 5 = 3)

; Store result
mov DWORD PTR [rbp-24], eax ; IntDiv = 3

; X# MOD Y# (modulo)

; Load X# and convert to integer

movsd xmm0, QWORD PTR [rbp-8] ; Load X# (17.8)
cvttsd2si eax, xmm0 ; Truncate to Long (17)

; Save left operand

sub rsp, 16
mov [rsp], eax

; Load Y# and convert to integer

movsd xmm0, QWORD PTR [rbp-16] ; Load Y# (5.2)
cvttsd2si ecx, xmm0 ; Truncate to Long (5)

; Restore left operand

mov eax, [rsp]
add rsp, 16

; Perform modulo
cdq ; Sign-extend eax to edx:eax
idiv ecx ; edx = eax % ecx (17 % 5 = 2)
mov eax, edx ; Move remainder to eax

; Store result
mov DWORD PTR [rbp-32], eax ; Remainder = 2
Key observations: - Float operands are truncated (not rounded) for integer operations -
cvttsd2si performs truncation toward zero - idiv produces both quotient (eax) and remainder
(edx)

5.7.3 Example 3: Boolean Expressions

BASIC Code:
A = 10
B = 20
C = 15

Result1 = (A < B) AND (C > A)

Result2 = (A > B) OR (C < B)
Result3 = NOT (A = B)
Type Analysis:
For (A < B) AND (C > A): 1. A < B: Comparison returns Long (-1 for true) 2. C > A: Comparison

89
returns Long (-1 for true) 3. (-1) AND (-1): Bitwise AND of Long values 4. Result: -1 (true)
For (A > B) OR (C < B): 1. A > B: Comparison returns Long (0 for false) 2. C < B: Comparison
returns Long (-1 for true) 3. 0 OR (-1): Bitwise OR of Long values 4. Result: -1 (true)
For NOT (A = B): 1. A = B: Comparison returns Long (0 for false) 2. NOT 0: Bitwise NOT of Long
value 3. Result: -1 (true)
Generated Assembly (simplified):
; (A < B) AND (C > A)

; Evaluate A < B
movsd xmm0, QWORD PTR [rbp-8] ; Load A
movsd xmm1, QWORD PTR [rbp-16] ; Load B
ucomisd xmm0, xmm1 ; Compare A with B
setb al ; Set al if A < B
movzx eax, al ; Zero-extend to eax
neg eax ; Convert 1 to -1 (true)

; Save result
sub rsp, 16
mov [rsp], eax

; Evaluate C > A
movsd xmm0, QWORD PTR [rbp-24] ; Load C
movsd xmm1, QWORD PTR [rbp-8] ; Load A
ucomisd xmm0, xmm1 ; Compare C with A
seta al ; Set al if C > A
movzx eax, al ; Zero-extend to eax
neg eax ; Convert 1 to -1 (true)

; Restore left operand and perform AND

mov ecx, eax ; Right operand
mov eax, [rsp] ; Left operand
add rsp, 16
and eax, ecx ; Bitwise AND

; Store result
mov DWORD PTR [rbp-32], eax ; Result1 = -1 (true)
Key observations: - Comparisons return -1 (true) or 0 (false) - Logical operators are bitwise
operations on Long values - -1 AND -1 = -1 (all bits set) - 0 OR -1 = -1 (any bit set) - NOT 0 =
-1 (flip all bits)

5.7.4 Example 4: Symbol Table States

BASIC Code:
10 X = 100
20 Y% = 200

90
30 GOSUB 100
40 PRINT X, Y%, Z
50 END

100 Z = 300
110 X = 400
120 RETURN
Symbol Table Evolution:
After line 10:
Global vars:
"X" -> { offset: -8, type: Double }
After line 20:
Global vars:
"X" -> { offset: -8, type: Double }
"Y%" -> { offset: -16, type: Integer }
After line 100 (in subroutine):
Global vars:
"X" -> { offset: -8, type: Double }
"Y%" -> { offset: -16, type: Integer }
"Z" -> { offset: -24, type: Double }
After line 110 (in subroutine):
Global vars:
"X" -> { offset: -8, type: Double } (modified to 400)
"Y%" -> { offset: -16, type: Integer }
"Z" -> { offset: -24, type: Double }
After line 40 (back in main): - All three variables are accessible - X has value 400 (modified by
subroutine) - Y% has value 200 (unchanged) - Z has value 300 (created by subroutine)
Key observations: - Variables are global by default - GOSUB doesn’t create a new scope (unlike
SUB/FUNCTION) - Variables created in subroutines are accessible after RETURN

5.7.5 Example 5: Local vs. Global Scope

BASIC Code:
X = 100 ' Global X
Y = 200 ' Global Y

SUB Test(A)
X = 300 ' Local X (shadows global)
Z = 400 ' Local Z
PRINT A, X, Y, Z
END SUB

91
Test 500
PRINT X, Y
Symbol Table States:
Global symbol table (after initial assignments):
"X" -> { offset: -8, type: Double }
"Y" -> { offset: -16, type: Double }
Local symbol table inside Test:
"A" -> { offset: -8, type: Double } (parameter)
"X" -> { offset: -16, type: Double } (shadows global)
"Z" -> { offset: -24, type: Double }
Variable resolution in PRINT A, X, Y, Z: - A: Found in local table → parameter (500) - X:
Found in local table → local variable (300) - Y: Not in local table, found in global table → global
variable (200) - Z: Found in local table → local variable (400)
Variable resolution in PRINT X, Y (after Test returns): - X: Found in global table → global
variable (100, unchanged) - Y: Found in global table → global variable (200)
Key observations: - Local variables shadow globals with the same name - Globals are accessible
from procedures unless shadowed - Local variables don’t persist after procedure returns - Parameters
are local variables initialized from arguments

5.7.6 Example 6: Type Coercion in Assignment

BASIC Code:
X% = 3.7 ' Assign Double to Integer
Y& = 10.9 ' Assign Double to Long
Z! = 42 ' Assign Long to Single
W# = 5 ' Assign Long to Double
Type Analysis and Generated Code:
X% = 3.7: 1. Expression type: Double (literal 3.7) 2. Target type: Integer (from % suffix) 3.
Coercion: Double → Integer (truncate) 4. Result: 3 (truncated, not rounded)
mov rax, 0x400D999999999999A ; 3.7 as Double
movq xmm0, rax
cvttsd2si eax, xmm0 ; Truncate to Integer (3)
mov WORD PTR [rbp-8], ax ; Store as 16-bit
Y& = 10.9: 1. Expression type: Double (literal 10.9) 2. Target type: Long (from & suffix) 3.
Coercion: Double → Long (truncate) 4. Result: 10 (truncated)
mov rax, 0x4025CCCCCCCCCCCD ; 10.9 as Double
movq xmm0, rax
cvttsd2si eax, xmm0 ; Truncate to Long (10)
mov DWORD PTR [rbp-16], eax ; Store as 32-bit

92
Z! = 42: 1. Expression type: Long (integer literal) 2. Target type: Single (from ! suffix) 3.
Coercion: Long → Single 4. Result: 42.0 (exact conversion)
mov eax, 42
cvtsi2ss xmm0, eax ; Convert to Single
movss DWORD PTR [rbp-24], xmm0
W# = 5: 1. Expression type: Long (integer literal) 2. Target type: Double (from # suffix) 3.
Coercion: Long → Double 4. Result: 5.0 (exact conversion)
mov eax, 5
cvtsi2sd xmm0, eax ; Convert to Double
movsd QWORD PTR [rbp-32], xmm0
Key observations: - Float-to-integer conversion truncates (doesn’t round) - Integer-to-float con-
version is exact (within precision limits) - Target variable type determines coercion, not expression
type

5.8 Summary
Semantic analysis in xbasic64 ensures that syntactically correct programs follow the language’s
type and scope rules. Key takeaways:

5.8.1 Type System

• Five data types: Integer (%), Long (&), Single (!), Double (#), String ($)
• Default type for unsuffixed variables is Double
• Type determined by variable suffix, not declaration
• Literals: integers are Long, floats are Double

5.8.2 Type Coercion

• Automatic promotion follows: Integer → Long → Single → Double
• Special rules for operators:
– / (division) always produces Double
– \ (integer division) always produces Long
– ^ (power) always produces Double
– Comparisons return Long (-1 for true, 0 for false)
• Coercion uses SSE instructions: cvtsi2sd, cvtss2sd, cvttsd2si, etc.
• Truncation (not rounding) for implicit float-to-integer conversion

5.8.3 Symbol Table

• Two symbol tables: global (vars) and local (proc_vars)
• Implicit variable declaration on first use
• Variables allocated on stack with 8-byte alignment
• Scope rules: local variables shadow globals
• Case-insensitive identifier resolution

93
5.8.4 Integration with Code Generation
• Semantic analysis happens during code generation (single pass)
• Type checking and coercion are interleaved with assembly emission
• Symbol table lookups occur during variable reference generation
• Errors are detected during code generation, not in a separate phase

5.8.5 Design Philosophy

xbasic64’s approach to semantic analysis prioritizes: - Simplicity: Integrated with code generation,
fewer passes - Clarity: Direct mapping from semantic rules to assembly code - BASIC semantics:
Implicit declaration, permissive type system - Educational value: Easy to understand how types
affect code generation
This integrated approach makes xbasic64 an excellent vehicle for learning how semantic analysis
influences code generation without the complexity of separate analysis passes found in production
compilers.

5.9 Further Reading

• Dragon Book Chapter 5: Syntax-Directed Translation
• Dragon Book Chapter 6: Type Checking
• Code Generation - See how semantic analysis informs assembly generation
• Language Reference - Complete type system specification
• Theory Comparison - How xbasic64 relates to compiler theory

5.10 Navigation: ← Syntax Analysis | Home | Next: Code Gen-

eration →
title: “Code Generation Phase” chapter: 6 prev: “[Link]” next: “[Link]”
dragon_book_chapters: [8] difficulty: advanced estimated_time: “90 minutes” —

94
Chapter 6

Code Generation Phase

6.1 Overview
The code generation phase is the final stage of the xbasic64 compiler, where the Abstract Syntax
Tree (AST) is translated directly into x86-64 assembly language. Unlike traditional compilers that
use intermediate representations (IR) and multiple optimization passes, xbasic64 takes a simplified
approach: direct AST-to-assembly translation in a single pass.

6.1.1 What is Code Generation?

Code generation is the process of transforming the high-level representation of a program (in our
case, the AST) into executable machine code. This involves:
1. Instruction Selection: Choosing appropriate machine instructions for each operation
2. Register Allocation: Deciding which values go in which registers
3. Memory Management: Organizing variables and temporaries on the stack
4. Control Flow: Translating high-level control structures (IF, FOR, WHILE) into jumps and
branches
5. Calling Conventions: Following the platform’s rules for function calls

6.1.2 The Direct Translation Strategy

xbasic64 uses a single-pass, direct translation approach:
AST Node → Assembly Instructions (immediately)
This means: - No intermediate representation (IR) - No separate optimization passes - Code is gen-
erated as we traverse the AST - Simple and easy to understand, but less optimized than production
compilers
Why this approach? - Educational clarity: The mapping from BASIC to assembly is direct
and visible - Simplicity: Fewer moving parts means easier to understand and modify - Sufficient
for BASIC: The language is simple enough that sophisticated optimization isn’t critical

6.1.3 The Code Generation Process

The code generator walks the AST recursively:

95
 1. Preprocessing Pass: Collect DATA statements and check for GOSUB usage
2. Procedure Generation: Generate code for SUB and FUNCTION definitions
3. Main Program: Generate the main program body
4. Data Section: Emit string literals, DATA tables, and global variables
For each AST node, the generator emits appropriate assembly instructions that: - Evaluate expres-
sions (leaving results in registers) - Execute statements (performing side effects) - Manage control
flow (jumps, branches, loops)

6.1.4 Output Format

The generator produces Intel syntax x86-64 assembly that is: - Assembled with the system
assembler (as) - Linked with the C standard library (cc) - Compatible with the System V AMD64
ABI (Linux/macOS calling convention)
Example output structure:
.intel_syntax noprefix
.text
.globl main

main:
push rbp
mov rbp, rsp
sub rsp, 64 # Allocate stack space

# Program code here

xor eax, eax

leave
ret

.data
_str_0: .ascii "Hello, World!"

6.2 Target Architecture: x86-64

6.2.1 Why x86-64?
The x86-64 architecture (also called AMD64 or x86_64) is the 64-bit extension of the x86 instruction
set. We target this architecture because:
• Ubiquity: Runs on most modern desktop and server computers
• Rich instruction set: Provides instructions for integer, floating-point, and string operations
• Good tooling: Excellent assemblers, debuggers, and documentation
• Educational value: Understanding x86-64 is valuable for systems programming

96
6.2.2 Key Architecture Features
[Link] Registers
x86-64 provides 16 general-purpose 64-bit registers:

Register Purpose in xbasic64 Preserved?

rax Integer results, string pointers No (caller-saved)
rbx (unused) Yes (callee-saved)
rcx Right operand for binary ops No (caller-saved)
rdx String lengths, division remainder No (caller-saved)
rsi Function argument 2 No (caller-saved)
rdi Function argument 1 No (caller-saved)
rbp Frame pointer (base of stack frame) Yes (callee-saved)
rsp Stack pointer (top of stack) Yes (special)
r8-r15 General purpose Mixed

Register naming conventions: - 64-bit: rax, rbx, rcx, etc. - 32-bit: eax, ebx, ecx, etc. (lower
32 bits) - 16-bit: ax, bx, cx, etc. (lower 16 bits) - 8-bit: al, bl, cl, etc. (lower 8 bits)

[Link] SSE Registers for Floating-Point

Modern x86-64 uses SSE (Streaming SIMD Extensions) for floating-point:

Register Purpose in xbasic64

xmm0 Float results, function returns
xmm1 Right operand for float binary ops
xmm2-xmm15 Temporaries, function arguments

SSE instructions operate on these 128-bit registers: - movss / movsd: Move single/double precision
floats - addss / addsd: Add single/double precision - mulss / mulsd: Multiply single/double
precision - cvtsi2sd: Convert integer to double - cvttsd2si: Convert double to integer (truncate)

6.2.3 System V AMD64 ABI

The Application Binary Interface (ABI) defines how functions are called. On Linux and
macOS, we follow the System V AMD64 ABI:

[Link] Function Arguments

Arguments are passed in registers (not on the stack for the first 6):

Argument Integer/Pointer Floating-Point

1st rdi xmm0
2nd rsi xmm1
3rd rdx xmm2

97
 Argument Integer/Pointer Floating-Point
4th rcx xmm3
5th r8 xmm4
6th r9 xmm5
7th+ Stack (right-to-left) Stack

[Link] Return Values

• Integers and pointers: rax
• Floating-point: xmm0

[Link] Register Preservation

Caller-saved (may be clobbered by function calls): - rax, rcx, rdx, rsi, rdi, r8-r11 - xmm0-xmm15
Callee-saved (must be preserved by called function): - rbx, rbp, r12-r15
This means: if we need a value to survive a function call, we must save it before the call.

[Link] Stack Alignment

Critical requirement: The stack must be 16-byte aligned before any call instruction.
• On function entry (after call pushes return address): rsp % 16 == 8
• After push rbp: rsp % 16 == 0
• Before any call: rsp % 16 == 0
xbasic64 maintains this by: - Rounding stack allocations to multiples of 16 - Using 16-byte incre-
ments for temporary storage (not 8-byte pushes)

6.3 Register Allocation Strategy

xbasic64 uses a simple, convention-based register allocation strategy rather than sophisti-
cated register allocation algorithms.

6.3.1 Primary Result Registers

Each data type has a designated “result register” where computed values live:

BASIC Type C Type Result Location Notes

INTEGER (%) i16 eax (low 16 bits) Sign-extended
when loaded
LONG (&) i32 eax 32-bit signed
integer
SINGLE (!) f32 xmm0 32-bit float
(SSE)
DOUBLE (#) f64 xmm0 64-bit float
(SSE)

98
BASIC Type C Type Result Location Notes
STRING ($) (ptr, len) rax + rdx Pointer in rax,
length in rdx

Convention: After evaluating any expression, the result is in the appropriate register(s).

6.3.2 Binary Operation Pattern

For binary operations (e.g., A + B), we need both operands in registers:
1. Evaluate left operand → result in eax/xmm0
2. Save left operand to stack (16-byte aligned temporary)
3. Evaluate right operand → result in eax/xmm0
4. Move right to secondary register (ecx/xmm1)
5. Restore left from stack to primary register
6. Perform operation: add eax, ecx or addsd xmm0, xmm1
Example assembly for X + Y:
; Evaluate X
movsd xmm0, QWORD PTR [rbp - 8] ; Load X

; Save X
sub rsp, 16 ; 16-byte aligned temp
movsd QWORD PTR [rsp], xmm0

; Evaluate Y
movsd xmm0, QWORD PTR [rbp - 16] ; Load Y

; Restore X, move Y to xmm1

movsd xmm1, xmm0 ; Y to xmm1
movsd xmm0, QWORD PTR [rsp] ; X to xmm0
add rsp, 16

; Perform addition
addsd xmm0, xmm1 ; X + Y

6.3.3 Why This Strategy?

Advantages: - Simple: Easy to understand and implement - Predictable: Always know where
values are - Sufficient: Works well for BASIC’s expression complexity
Disadvantages: - Not optimal: Generates more memory traffic than necessary - No register
reuse: Doesn’t track which registers are free - Spills frequently: Uses stack for all temporaries
Production compilers use sophisticated algorithms (graph coloring, linear scan) to minimize register
spills, but for educational purposes, simplicity wins.

99
6.4 Stack Frame Layout
The stack frame is the region of the stack dedicated to a single function invocation. It holds local
variables, saved registers, and temporary values.

6.4.1 Stack Frame Structure

High addresses (towards 0x7FFFFFFFFFFF)
�����������������������������������
� Function arguments (7+) � ← Caller's frame
�����������������������������������
� Return address � ← Pushed by CALL instruction
�����������������������������������
� Saved rbp (old frame pointer) � ← push rbp
����������������������������������� ← rbp points here (frame base)
� Local variable 1 � [rbp - 8]
� Local variable 2 � [rbp - 16]
� Local variable 3 � [rbp - 24]
� ... �
� Local variable N � [rbp - N*8]
����������������������������������� ← rsp after prologue
� Temporary space � ← Used during expression evaluation
� (grows/shrinks dynamically) �
����������������������������������� ← rsp (current stack top)
Low addresses (towards 0x0)

6.4.2 Function Prologue

Every function starts with a prologue that sets up the stack frame:
main:
push rbp ; Save old frame pointer
mov rbp, rsp ; Set new frame pointer
sub rsp, 64 ; Allocate space for locals (rounded to 16)
After the prologue: - rbp points to the base of the frame (unchanging reference point) - rsp points
to the top of the stack (changes as we push/pop) - Local variables are accessed via [rbp - offset]

6.4.3 Function Epilogue

Every function ends with an epilogue that tears down the frame:
xor eax, eax ; Return value (0 for success)
leave ; Equivalent to: mov rsp, rbp; pop rbp
ret ; Pop return address and jump
The leave instruction is a shorthand for restoring the stack and frame pointers.

6.4.4 Variable Storage

All local variables are allocated 8 bytes regardless of actual type:

100
 BASIC Type Actual Size Allocated Size Reason
INTEGER (%) 2 bytes 8 bytes Alignment
LONG (&) 4 bytes 8 bytes Alignment
SINGLE (!) 4 bytes 8 bytes Alignment
DOUBLE (#) 8 bytes 8 bytes Natural size
STRING ($) 16 bytes 16 bytes Pointer + length

Why 8 bytes for everything? - Simplifies offset calculation - Maintains 8-byte alignment (re-
quired for efficient memory access) - Wastes some space but makes code generation simpler

6.4.5 Stack Alignment Requirements

The System V ABI requires 16-byte stack alignment before call instructions. This is critical
for: - SSE instructions (some require 16-byte aligned operands) - Varargs functions like printf -
Compatibility with C libraries
xbasic64 maintains alignment by: 1. Rounding total local variable space to multiple of 16 2. Using
16-byte increments for temporary storage (not 8-byte pushes)
Example:
; Need 24 bytes for 3 variables
; Round up: (24 + 15) & ~15 = 32
sub rsp, 32 ; Allocate 32 bytes (16-byte aligned)

6.4.6 Accessing Variables

Variables are accessed relative to rbp:
; Store integer variable at [rbp - 8]
mov DWORD PTR [rbp - 8], eax

; Load double variable from [rbp - 16]

movsd xmm0, QWORD PTR [rbp - 16]

; Store string (pointer + length) at [rbp - 24]

mov QWORD PTR [rbp - 24], rax ; Pointer
mov QWORD PTR [rbp - 32], rdx ; Length
Negative offsets from rbp access local variables. Positive offsets would access function parameters
(in traditional stack-based parameter passing).

6.5 Implementation Walkthrough: src/[Link]

Let’s walk through the key components of the code generator implementation.

6.5.1 The CodeGen Structure

pub struct CodeGen {
output: String, // Accumulated assembly output

101
 vars: HashMap<String, VarInfo>, // Global variables
arrays: HashMap<String, ArrayInfo>, // Array metadata
stack_offset: i32, // Current stack offset
label_counter: u32, // For generating unique labels
string_literals: Vec<String>, // String constants
data_items: Vec<Literal>, // DATA statement values
current_proc: Option<String>, // Current SUB/FUNCTION name
proc_vars: HashMap<String, VarInfo>,// Local variables
gosub_used: bool, // Whether GOSUB is used
}
The CodeGen struct maintains all state needed during code generation: - output: The assembly
code being built up - vars: Maps variable names to their stack offsets and types - stack_offset:
Tracks the current position in the stack frame (grows negative) - label_counter: Ensures unique
labels for branches and loops - string_literals: Collects all string constants for the data section

6.5.2 Type System and Coercion

BASIC’s type system requires automatic type promotion:
fn promote_types(&self, left: DataType, right: DataType, op: BinaryOp) -> DataType {
// Division (/) always produces Double
if op == BinaryOp::Div {
return DataType::Double;
}

// Integer division (\) always produces Long

if op == BinaryOp::IntDiv {
return DataType::Long;
}

// Numeric promotion: Integer < Long < Single < Double

match (left, right) {
(DataType::Double, _) | (_, DataType::Double) => DataType::Double,
(DataType::Single, _) | (_, DataType::Single) => DataType::Single,
(DataType::Long, _) | (_, DataType::Long) => DataType::Long,
_ => DataType::Integer,
}
}
Type coercion generates conversion instructions:
fn gen_coercion(&mut self, from: DataType, to: DataType) {
match (from, to) {
// Integer to Double
(DataType::Integer | DataType::Long, DataType::Double) => {
[Link](" cvtsi2sd xmm0, eax");
}
// Double to Integer (truncate)
(DataType::Double, DataType::Integer | DataType::Long) => {

102
 [Link](" cvttsd2si eax, xmm0");
}
// Single to Double
(DataType::Single, DataType::Double) => {
[Link](" cvtss2sd xmm0, xmm0");
}
// ... more conversions
}
}

6.5.3 Expression Evaluation

The gen_expr method evaluates expressions and returns their type:
fn gen_expr(&mut self, expr: &Expr) -> DataType {
match expr {
Expr::Literal(lit) => {
match lit {
Literal::Integer(n) => {
[Link](&format!(" mov eax, {}", *n as i32));
DataType::Long
}
Literal::Float(f) => {
let bits = f.to_bits();
[Link](&format!(" mov rax, 0x{:X}", bits));
[Link](" movq xmm0, rax");
DataType::Double
}
Literal::String(s) => {
let idx = self.add_string_literal(s);
[Link](&format!(" lea rax, [rip + _str_{}]", idx));
[Link](&format!(" mov rdx, {}", [Link]()));
DataType::String
}
}
}

Expr::Variable(name) => {
let info = self.get_var_info(name);
match info.data_type {
DataType::Long => {
[Link](&format!(" mov eax, DWORD PTR [rbp + {}]",
[Link]));
}
DataType::Double => {
[Link](&format!(" movsd xmm0, QWORD PTR [rbp + {}]",
[Link]));
}

103
 // ... other types
}
info.data_type
}

Expr::Binary { op, left, right } => {

self.gen_binary_expr(*op, left, right)
}

// ... other expression types

}
}

6.5.4 Binary Expression Pattern

Binary expressions follow a careful pattern to handle nested subexpressions:
fn gen_binary_expr(&mut self, op: BinaryOp, left: &Expr, right: &Expr) -> DataType {
let result_type = self.promote_types(
self.expr_type(left),
self.expr_type(right),
op
);

// Evaluate left operand and coerce to result type

let left_type = self.gen_expr(left);
self.gen_coercion(left_type, result_type);

// Save left result (16-byte aligned for ABI compliance)

[Link](" sub rsp, 16");
if result_type.is_integer() {
[Link](" mov QWORD PTR [rsp], rax");
} else {
[Link](" movsd QWORD PTR [rsp], xmm0");
}

// Evaluate right operand and coerce

let right_type = self.gen_expr(right);
self.gen_coercion(right_type, result_type);

// Move right to secondary register, restore left

if result_type.is_integer() {
[Link](" mov ecx, eax"); // right → ecx
[Link](" mov rax, QWORD PTR [rsp]"); // left → rax
} else {
[Link](" movsd xmm1, xmm0"); // right → xmm1
[Link](" movsd xmm0, QWORD PTR [rsp]"); // left → xmm0
}

104
 [Link](" add rsp, 16");

// Perform operation
match op {
BinaryOp::Add => {
if result_type.is_integer() {
[Link](" add eax, ecx");
} else {
[Link](" addsd xmm0, xmm1");
}
}
// ... other operations
}

result_type
}
Why 16-byte temporaries? If evaluating the right operand involves a function call, the stack
must be 16-byte aligned. Using 16-byte increments maintains this invariant.

6.5.5 Statement Generation

The gen_stmt method generates code for each statement type:

[Link] Variable Assignment

Stmt::Let { name, indices: None, value } => {
// Evaluate expression
let expr_type = self.gen_expr(value);
let var_info = self.get_var_info(name);

// Coerce to target type

self.gen_coercion(expr_type, var_info.data_type);

// Store based on target type

match var_info.data_type {
DataType::Long => {
[Link](&format!(" mov DWORD PTR [rbp + {}], eax",
var_info.offset));
}
DataType::Double => {
[Link](&format!(" movsd QWORD PTR [rbp + {}], xmm0",
var_info.offset));
}
// ... other types
}
}

105
[Link] IF Statement
Stmt::If { condition, then_branch, else_branch } => {
let else_label = self.new_label("else");
let end_label = self.new_label("endif");

// Evaluate condition
let cond_type = self.gen_expr(condition);

// Compare with 0 and branch

if cond_type.is_integer() {
[Link](" test eax, eax");
[Link](&format!(" je {}", else_label));
} else {
[Link](" xorpd xmm1, xmm1");
[Link](" ucomisd xmm0, xmm1");
[Link](&format!(" je {}", else_label));
}

// Generate THEN branch

for s in then_branch {
self.gen_stmt(s);
}
[Link](&format!(" jmp {}", end_label));

// Generate ELSE branch

self.emit_label(&else_label);
if let Some(eb) = else_branch {
for s in eb {
self.gen_stmt(s);
}
}

self.emit_label(&end_label);
}

[Link] FOR Loop

FOR loops are more complex due to step direction checking:
Stmt::For { var, start, end, step, body } => {
let start_label = self.new_label("for");
let end_label = self.new_label("endfor");
let var_offset = self.get_var_offset(var);

// Initialize loop variable (coerce to double)

let start_type = self.gen_expr(start);
self.gen_coercion(start_type, DataType::Double);
[Link](&format!(" movsd QWORD PTR [rbp + {}], xmm0", var_offset));

106
// Store end value
self.stack_offset -= 8;
let end_offset = self.stack_offset;
let end_type = self.gen_expr(end);
self.gen_coercion(end_type, DataType::Double);
[Link](&format!(" movsd QWORD PTR [rbp + {}], xmm0", end_offset));

// Store step value (default 1.0)

self.stack_offset -= 8;
let step_offset = self.stack_offset;
if let Some(s) = step {
let step_type = self.gen_expr(s);
self.gen_coercion(step_type, DataType::Double);
} else {
[Link](" mov rax, 0x3FF0000000000000 # 1.0");
[Link](" movq xmm0, rax");
}
[Link](&format!(" movsd QWORD PTR [rbp + {}], xmm0", step_offset));

// Loop start: check condition based on step sign

self.emit_label(&start_label);
[Link](&format!(" movsd xmm0, QWORD PTR [rbp + {}]", var_offset));
[Link](&format!(" movsd xmm1, QWORD PTR [rbp + {}]", end_offset));
[Link](&format!(" movsd xmm2, QWORD PTR [rbp + {}]", step_offset));

// Check if step is negative

[Link](" xorpd xmm3, xmm3");
[Link](" ucomisd xmm2, xmm3");
[Link](&format!(" jb .Lfor_neg_{}", self.label_counter));

// Positive step: exit if var > end

[Link](" ucomisd xmm0, xmm1");
[Link](&format!(" ja {}", end_label));
[Link](&format!(" jmp .Lfor_body_{}", self.label_counter));

// Negative step: exit if var < end

self.emit_label(&format!(".Lfor_neg_{}", self.label_counter));
[Link](" ucomisd xmm0, xmm1");
[Link](&format!(" jb {}", end_label));

self.emit_label(&format!(".Lfor_body_{}", self.label_counter));
self.label_counter += 1;

// Generate loop body

for s in body {
self.gen_stmt(s);
}

107
 // Increment loop variable
[Link](&format!(" movsd xmm0, QWORD PTR [rbp + {}]", var_offset));
[Link](&format!(" addsd xmm0, QWORD PTR [rbp + {}]", step_offset));
[Link](&format!(" movsd QWORD PTR [rbp + {}], xmm0", var_offset));
[Link](&format!(" jmp {}", start_label));

self.emit_label(&end_label);
}

6.5.6 Built-in Function Calls

Built-in functions are handled specially:
fn gen_fn_call(&mut self, name: &str, args: &[Expr]) {
let upper_name = name.to_uppercase();

// Math functions that call libc

if let Some(libc_fn) = LIBC_MATH_FNS.get(upper_name.as_str()) {
let arg_type = self.gen_expr(&args[0]);
self.gen_coercion(arg_type, DataType::Double);
[Link](&format!(" call {}", libc_fn));
return;
}

// Inline math functions

if let Some(instr) = INLINE_MATH_FNS.get(upper_name.as_str()) {
let arg_type = self.gen_expr(&args[0]);
self.gen_coercion(arg_type, DataType::Double);
[Link](&format!(" {}", instr));
return;
}

// String functions
match upper_name.as_str() {
"LEFT$" => {
self.gen_expr(&args[0]); // string: rax=ptr, rdx=len
[Link](" mov rdi, rax");
[Link](" mov rsi, rdx");
let count_type = self.gen_expr(&args[1]);
if count_type.is_integer() {
[Link](" movsxd rdx, eax");
} else {
[Link](" cvttsd2si rdx, xmm0");
}
[Link](" call _rt_left");
}
// ... more string functions

108
 }
}

6.5.7 Array Handling

Arrays require dynamic memory allocation and index calculation:
fn gen_dim_array(&mut self, arr: &ArrayDecl) {
let elem_size = if is_string_var(&[Link]) { 16 } else { 8 };

// Evaluate and store dimension bounds

let mut dim_offsets = Vec::new();
for dim in [Link]() {
let dim_type = self.gen_expr(dim);
if dim_type.is_integer() {
[Link](" movsxd rax, eax");
} else {
[Link](" cvttsd2si rax, xmm0");
}
[Link](" inc rax"); // DIM A(N) has N+1 elements (0 to N)
self.stack_offset -= 8;
dim_offsets.push(self.stack_offset);
[Link](&format!(" mov QWORD PTR [rbp + {}], rax",
self.stack_offset));
}

// Calculate total elements: dim0 * dim1 * dim2 * ...

[Link](&format!(" mov rax, QWORD PTR [rbp + {}]", dim_offsets[0]));
for offset in dim_offsets.iter().skip(1) {
[Link](&format!(" imul rax, QWORD PTR [rbp + {}]", offset));
}

// Allocate: total_elements * elem_size

[Link](&format!(" imul rdi, rax, {}", elem_size));
[Link](" call malloc");

// Store array pointer

self.stack_offset -= 8;
let ptr_offset = self.stack_offset;
[Link](&format!(" mov QWORD PTR [rbp + {}], rax", ptr_offset));

// Record array info

[Link]([Link](), ArrayInfo {
ptr_offset,
dim_offsets,
});
}
Array access uses row-major order indexing:

109
fn gen_array_load(&mut self, name: &str, indices: &[Expr]) {
let arr_info = [Link](name).expect("Array not declared");
let elem_size = if is_string_var(name) { 16 } else { 8 };

// Calculate linear index: ((i * dim1) + j) * dim2 + k

let idx_type = self.gen_expr(&indices[0]);
if idx_type.is_integer() {
[Link](" movsxd rax, eax");
} else {
[Link](" cvttsd2si rax, xmm0");
}

// For each subsequent index, multiply by dimension and add

for (i, idx_expr) in [Link]().enumerate().skip(1) {
[Link](" sub rsp, 16");
[Link](" mov QWORD PTR [rsp], rax");

let idx_type = self.gen_expr(idx_expr);

if idx_type.is_integer() {
[Link](" movsxd rcx, eax");
} else {
[Link](" cvttsd2si rcx, xmm0");
}

[Link](" mov rax, QWORD PTR [rsp]");

[Link](" add rsp, 16");
[Link](&format!(" imul rax, QWORD PTR [rbp + {}]",
arr_info.dim_offsets[i]));
[Link](" add rax, rcx");
}

// Multiply by element size and add to base pointer

[Link](&format!(" imul rax, {}", elem_size));
[Link](&format!(" add rax, QWORD PTR [rbp + {}]",
arr_info.ptr_offset));

// Load value
if is_string_var(name) {
[Link](" mov rcx, rax");
[Link](" mov rax, QWORD PTR [rcx]");
[Link](" mov rdx, QWORD PTR [rcx + 8]");
} else {
[Link](" movsd xmm0, QWORD PTR [rax]");
}
}

110
6.6 Side-by-Side Examples: BASIC to Assembly
Let’s see how various BASIC constructs translate to x86-64 assembly.

6.6.1 Example 1: Simple Variable Assignment

BASIC:
X# = 42.5
Y& = 100
Generated Assembly:
; X# = 42.5
mov rax, 0x4045400000000000 ; 42.5 as 64-bit float
movq xmm0, rax
movsd QWORD PTR [rbp - 8], xmm0

; Y& = 100
mov eax, 100
mov DWORD PTR [rbp - 16], eax
Explanation: - Floating-point literals are loaded as 64-bit hex values into rax, then moved to
xmm0 - Integer literals are loaded directly into eax - Variables are stored at negative offsets from
rbp

6.6.2 Example 2: Arithmetic Expression

BASIC:
Result# = (A# + B#) * C#
Generated Assembly:
; Evaluate A#
movsd xmm0, QWORD PTR [rbp - 8]

; Save A# (16-byte aligned)

sub rsp, 16
movsd QWORD PTR [rsp], xmm0

; Evaluate B#
movsd xmm0, QWORD PTR [rbp - 16]

; Restore A#, move B# to xmm1

movsd xmm1, xmm0
movsd xmm0, QWORD PTR [rsp]
add rsp, 16

; A# + B#
addsd xmm0, xmm1

111
 ; Save (A# + B#)
sub rsp, 16
movsd QWORD PTR [rsp], xmm0

; Evaluate C#
movsd xmm0, QWORD PTR [rbp - 24]

; Restore (A# + B#), move C# to xmm1

movsd xmm1, xmm0
movsd xmm0, QWORD PTR [rsp]
add rsp, 16

; (A# + B#) * C#
mulsd xmm0, xmm1

; Store Result#
movsd QWORD PTR [rbp - 32], xmm0
Explanation: - Each binary operation follows the save-evaluate-restore pattern - Temporary re-
sults are saved on the stack with 16-byte alignment - The final result is in xmm0 and stored to the
result variable

6.6.3 Example 3: Type Coercion

BASIC:
I% = 10
D# = I% + 3.14
Generated Assembly:
; I% = 10
mov eax, 10
mov WORD PTR [rbp - 8], ax

; Evaluate I% (load and sign-extend)

movsx eax, WORD PTR [rbp - 8]

; Coerce I% to Double
cvtsi2sd xmm0, eax

; Save I% as Double
sub rsp, 16
movsd QWORD PTR [rsp], xmm0

; Evaluate 3.14
mov rax, 0x40091EB851EB851F
movq xmm0, rax

; Restore I#, move 3.14 to xmm1

112
 movsd xmm1, xmm0
movsd xmm0, QWORD PTR [rsp]
add rsp, 16

; I# + 3.14
addsd xmm0, xmm1

; Store D#
movsd QWORD PTR [rbp - 16], xmm0
Explanation: - Integer is loaded with sign extension: movsx eax, WORD PTR - cvtsi2sd converts
signed integer in eax to double in xmm0 - Addition is performed in double precision

6.6.4 Example 4: IF Statement

BASIC:
IF X > 0 THEN
PRINT "Positive"
ELSE
PRINT "Non-positive"
END IF
Generated Assembly:
; Evaluate X
movsd xmm0, QWORD PTR [rbp - 8]

; Evaluate 0
xorpd xmm1, xmm1

; Compare X > 0
ucomisd xmm0, xmm1
seta al
movzx eax, al
neg eax ; -1 if true, 0 if false

; Test condition
test eax, eax
je .Lelse_0

; THEN branch
lea rdi, [rip + _str_0] ; "Positive"
mov rsi, 8
call _rt_print_string
call _rt_print_newline
jmp .Lendif_0

.Lelse_0:
; ELSE branch

113
 lea rdi, [rip + _str_1] ; "Non-positive"
mov rsi, 12
call _rt_print_string
call _rt_print_newline

.Lendif_0:
Explanation: - ucomisd compares two doubles (unordered compare) - seta sets al to 1 if above
(unsigned), 0 otherwise - neg eax converts 1 to -1 (BASIC true value) - test eax, eax checks if
zero, je jumps if equal (false)

6.6.5 Example 5: FOR Loop

BASIC:
FOR I = 1 TO 10 STEP 2
PRINT I
NEXT I
Generated Assembly:
; Initialize I = 1
mov eax, 1
cvtsi2sd xmm0, eax
movsd QWORD PTR [rbp - 8], xmm0

; Store end value (10)

mov eax, 10
cvtsi2sd xmm0, eax
movsd QWORD PTR [rbp - 16], xmm0

; Store step value (2)

mov eax, 2
cvtsi2sd xmm0, eax
movsd QWORD PTR [rbp - 24], xmm0

.Lfor_0:
; Load I, end, step
movsd xmm0, QWORD PTR [rbp - 8] ; I
movsd xmm1, QWORD PTR [rbp - 16] ; end
movsd xmm2, QWORD PTR [rbp - 24] ; step

; Check if step is negative

xorpd xmm3, xmm3
ucomisd xmm2, xmm3
jb .Lfor_neg_0

; Positive step: exit if I > end

ucomisd xmm0, xmm1
ja .Lendfor_0

114
 jmp .Lfor_body_0

.Lfor_neg_0:
; Negative step: exit if I < end
ucomisd xmm0, xmm1
jb .Lendfor_0

.Lfor_body_0:
; PRINT I
movsd xmm0, QWORD PTR [rbp - 8]
call _rt_print_float
call _rt_print_newline

; Increment I by step
movsd xmm0, QWORD PTR [rbp - 8]
addsd xmm0, QWORD PTR [rbp - 24]
movsd QWORD PTR [rbp - 8], xmm0

jmp .Lfor_0

.Lendfor_0:
Explanation: - Loop variable, end, and step are all stored as doubles - The loop checks step sign
to determine exit condition - Positive step: exit when I > end - Negative step: exit when I < end
- Loop variable is incremented by adding step value

6.6.6 Example 6: Function Call

BASIC:
Y# = SIN(X#) + COS(X#)
Generated Assembly:
; Evaluate SIN(X#)
movsd xmm0, QWORD PTR [rbp - 8] ; Load X#
call sin ; Call libc sin()

; Save SIN(X#)
sub rsp, 16
movsd QWORD PTR [rsp], xmm0

; Evaluate COS(X#)
movsd xmm0, QWORD PTR [rbp - 8] ; Load X# again
call cos ; Call libc cos()

; Restore SIN(X#), move COS(X#) to xmm1

movsd xmm1, xmm0
movsd xmm0, QWORD PTR [rsp]
add rsp, 16

115
 ; SIN(X#) + COS(X#)
addsd xmm0, xmm1

; Store Y#
movsd QWORD PTR [rbp - 16], xmm0
Explanation: - Math functions call the C standard library (sin, cos, etc.) - Arguments are
passed in xmm0 (System V ABI for float args) - Return values come back in xmm0 - Results are
saved/restored like any other subexpression

6.6.7 Example 7: String Operations

BASIC:
Name$ = "Hello"
Greeting$ = Name$ + " World"
PRINT Greeting$
Generated Assembly:
; Name$ = "Hello"
lea rax, [rip + _str_0] ; Pointer to "Hello"
mov rdx, 5 ; Length
mov QWORD PTR [rbp - 8], rax ; Store pointer
mov QWORD PTR [rbp - 16], rdx ; Store length

; Evaluate Name$ (left operand)

mov rax, QWORD PTR [rbp - 8]
mov rdx, QWORD PTR [rbp - 16]

; Save Name$ on stack

push rdx ; Length
push rax ; Pointer

; Evaluate " World" (right operand)

lea rax, [rip + _str_1] ; Pointer to " World"
mov rdx, 6 ; Length

; Call string concatenation

mov rcx, rdx ; right_len → rcx (4th arg)
mov rdx, rax ; right_ptr → rdx (3rd arg)
pop rdi ; left_ptr → rdi (1st arg)
pop rsi ; left_len → rsi (2nd arg)
call _rt_strcat
; Result: ptr in rax, len in rdx

; Store Greeting$
mov QWORD PTR [rbp - 24], rax
mov QWORD PTR [rbp - 32], rdx

116
 ; PRINT Greeting$
mov rax, QWORD PTR [rbp - 24]
mov rdx, QWORD PTR [rbp - 32]
mov rdi, rax
mov rsi, rdx
call _rt_print_string
call _rt_print_newline
Explanation: - Strings are represented as (pointer, length) pairs - String variables occupy 16
bytes (two 8-byte slots) - String concatenation calls the runtime function _rt_strcat - Arguments
follow System V ABI: rdi, rsi, rdx, rcx

6.6.8 Example 8: Array Access

BASIC:
DIM A(10, 20)
A(5, 10) = 42.0
X# = A(5, 10)
Generated Assembly:
; DIM A(10, 20)
; Evaluate first dimension (10)
mov eax, 10
movsxd rax, eax
inc rax ; 11 elements (0-10)
mov QWORD PTR [rbp - 8], rax

; Evaluate second dimension (20)

mov eax, 20
movsxd rax, eax
inc rax ; 21 elements (0-20)
mov QWORD PTR [rbp - 16], rax

; Calculate total elements: 11 * 21 = 231

mov rax, QWORD PTR [rbp - 8]
imul rax, QWORD PTR [rbp - 16]

; Allocate: 231 * 8 = 1848 bytes

imul rdi, rax, 8
call malloc

; Store array pointer

mov QWORD PTR [rbp - 24], rax

; A(5, 10) = 42.0

; Calculate index: 5 * 21 + 10 = 115
mov eax, 5

117
 movsxd rax, eax
imul rax, QWORD PTR [rbp - 16] ; 5 * 21
mov ecx, 10
movsxd rcx, ecx
add rax, rcx ; + 10

; Calculate address: base + (115 * 8)

imul rax, 8
add rax, QWORD PTR [rbp - 24]

; Save address
sub rsp, 16
mov QWORD PTR [rsp], rax

; Evaluate 42.0
mov rax, 0x4045000000000000
movq xmm0, rax

; Store to array
mov rcx, QWORD PTR [rsp]
add rsp, 16
movsd QWORD PTR [rcx], xmm0

; X# = A(5, 10)
; Calculate same index and address
mov eax, 5
movsxd rax, eax
imul rax, QWORD PTR [rbp - 16]
mov ecx, 10
movsxd rcx, ecx
add rax, rcx
imul rax, 8
add rax, QWORD PTR [rbp - 24]

; Load from array

movsd xmm0, QWORD PTR [rax]

; Store to X#
movsd QWORD PTR [rbp - 32], xmm0
Explanation: - Arrays are allocated on the heap using malloc - Dimensions are stored on the
stack for index calculation - Multi-dimensional arrays use row-major order: index = (i * dim1)
+ j - Element address: base_ptr + (index * element_size)

118
6.7 Common Patterns and Idioms
6.7.1 Pattern 1: Zero a Register
xor eax, eax ; Set eax to 0 (faster than mov eax, 0)
xorpd xmm0, xmm0 ; Set xmm0 to 0.0

6.7.2 Pattern 2: Boolean to Integer

BASIC uses -1 for true, 0 for false:
; Convert comparison result to BASIC boolean
sete al ; Set al to 1 if equal, 0 otherwise
movzx eax, al ; Zero-extend to 32 bits
neg eax ; Negate: 1 becomes -1, 0 stays 0

6.7.3 Pattern 3: Load Floating-Point Constant

; Load 1.0 into xmm0
mov rax, 0x3FF0000000000000 ; 1.0 as 64-bit hex
movq xmm0, rax

6.7.4 Pattern 4: Sign Extension

; Load 16-bit integer with sign extension
movsx eax, WORD PTR [rbp - 8]

; Sign-extend 32-bit to 64-bit

movsxd rax, eax

6.7.5 Pattern 5: Function Prologue/Epilogue

; Prologue
push rbp
mov rbp, rsp
sub rsp, 64 ; Allocate locals (16-byte aligned)

; Epilogue
xor eax, eax ; Return 0
leave ; Restore rbp and rsp
ret ; Return to caller

6.8 Optimization Opportunities

While xbasic64 prioritizes simplicity over optimization, here are some improvements a production
compiler might make:

6.8.1 1. Register Allocation

Current approach: All temporaries spill to stack

119
Optimization: Track register liveness and reuse registers - Reduces memory traffic - Improves
cache performance - Requires liveness analysis and register allocation algorithm

6.8.2 2. Constant Folding

Current approach: Evaluate all expressions at runtime
Optimization: Evaluate constant expressions at compile time
X = 2 + 3 * 4 ' Could compile to: mov eax, 14

6.8.3 3. Common Subexpression Elimination

Current approach: Recompute identical subexpressions
Optimization: Compute once and reuse
Y = (A + B) * 2
Z = (A + B) * 3
' Could compute (A + B) once and reuse

6.8.4 4. Dead Code Elimination

Current approach: Generate code for all statements
Optimization: Remove code that has no effect
X = 10
X = 20 ' First assignment is dead code

6.8.5 5. Strength Reduction

Current approach: Use general instructions for all operations
Optimization: Replace expensive operations with cheaper ones
X = Y * 2 ' Could use: add eax, eax (faster than imul)
X = Y / 4 ' Could use: sar eax, 2 (shift right)

6.8.6 6. Loop Invariant Code Motion

Current approach: Recompute invariants in every iteration
Optimization: Move loop-invariant computations outside the loop
FOR I = 1 TO 100
X = A * B + I ' A * B is loop-invariant
NEXT I

6.9 Summary
The code generation phase transforms the AST into executable x86-64 assembly through:
1. Direct translation: One-pass traversal of the AST

120
 2. Simple register allocation: Convention-based, predictable register usage
3. Stack-based temporaries: All intermediate values spill to stack
4. ABI compliance: Follows System V AMD64 calling convention
5. Type coercion: Automatic conversion between numeric types
Key takeaways: - Code generation is the bridge between high-level semantics and machine execu-
tion - Register allocation and calling conventions are critical for correctness - Stack alignment is
essential for ABI compliance - Direct translation is simple but leaves optimization opportunities -
Understanding assembly output helps debug compiler issues
The generated code is correct and functional, though not optimized. For an educational compiler,
this trade-off favors clarity and simplicity over performance.

6.10 Further Reading

• Intel 64 and IA-32 Architectures Software Developer’s Manual: Complete x86-64
instruction reference
• System V AMD64 ABI: Official calling convention specification
• Dragon Book Chapter 8: Code generation techniques and algorithms
• Engineering a Compiler (Cooper & Torczon): Modern code generation approaches
• GCC Assembly Output: Study gcc -S output to see production code generation

6.11 Exercises
1. Modify the code generator to use lea (load effective address) for simple arithmetic like
X = Y + 4
2. Add optimization to detect multiplication by powers of 2 and use shift instructions instead
3. Implement peephole optimization to eliminate redundant load/store pairs
4. Add register pressure tracking to count how many registers are in use at each point
5. Generate code with debug symbols to enable source-level debugging with gdb
6. Compare assembly output between xbasic64 and gcc -O0 for equivalent C code
7. Measure code size and execution time for various BASIC programs with and without
optimizations

Next: Runtime System →

6.12 Previous: ← Semantic Analysis

title: “Runtime System” chapter: 7 prev: “[Link]” next: “08-language-
[Link]” dragon_book_chapters: [7] difficulty: intermediate estimated_time: “45 minutes”
—

121
Chapter 7

Runtime System

7.1 Introduction
The runtime system is the support library that provides essential services to compiled BASIC pro-
grams. While the compiler translates BASIC source code into x86-64 assembly, many operations—
like printing to the console, reading user input, manipulating strings, and performing complex
math—are too complex or platform-specific to generate inline. Instead, the compiler generates
calls to runtime functions that handle these operations.
This document explores xbasic64’s runtime library: its design philosophy, implementation strategies,
and how compiled programs interact with it. You’ll learn how high-level BASIC operations like
PRINT "Hello" and INPUT X are implemented at the assembly level.

7.2 Table of Contents

• Runtime Library Overview
• String Handling
• I/O Operations
• Math Functions
• Runtime Implementation Overview
• Summary
• Further Reading

7.3 Runtime Library Overview

7.3.1 Purpose and Design
The runtime library serves several critical purposes:
1. Platform Abstraction
Different operating systems have different system call interfaces. Rather than generating platform-
specific code for every I/O operation, the compiler generates calls to runtime functions that use libc
(the C standard library) for portability. This allows xbasic64 to work on both Linux and macOS
with minimal changes.

122
2. Code Reuse
Many BASIC operations are used repeatedly throughout a program. For example, every PRINT
statement needs to format and output data. Rather than generating the same formatting code
inline at every PRINT statement, the compiler generates a call to a shared runtime function. This
produces smaller executables and makes the compiler simpler.
3. Complex Operations
Some operations are too complex to generate inline efficiently: - String concatenation requires
memory allocation - String search (INSTR) requires sophisticated algorithms - Math functions
(SIN, COS, LOG) require floating-point algorithms - File I/O requires buffering and error handling
The runtime library implements these operations once, correctly, and efficiently.
4. Consistent Behavior
By centralizing operations in the runtime library, xbasic64 ensures consistent behavior across all
programs. For example, all BASIC programs format numbers the same way because they all call
the same _rt_print_float function.

7.3.2 Runtime Architecture

The xbasic64 runtime library is organized into several modules, each handling a specific category
of operations:
src/runtime/
��� data_defs.s # Data section definitions (format strings, buffers)
��� print.s # Output functions (PRINT statement)
��� input.s # Input functions (INPUT statement)
��� string.s # String manipulation (concatenation, substring, search)
��� math.s # Math and utility functions (RND, TIMER, CLS)
��� data.s # DATA/READ/RESTORE support
��� file.s # File I/O (OPEN, CLOSE, PRINT#, INPUT#)
Each module is written in x86-64 assembly and follows the System V AMD64 ABI calling convention.
The src/[Link] module assembles these files into a complete runtime library that’s linked with
every compiled BASIC program.

7.3.3 How Compiled Programs Use the Runtime

When the compiler encounters a BASIC statement that requires runtime support, it generates a
call instruction to the appropriate runtime function:
BASIC Code:
PRINT "Hello, World!"
Generated Assembly:
lea rdi, [rip + .Lstr_1] # String pointer
mov rsi, 13 # String length
call _rt_print_string # Call runtime function
call _rt_print_newline # Print newline

123
The runtime function _rt_print_string handles all the details of formatting and outputting the
string using libc’s printf.

7.3.4 Calling Convention

All runtime functions follow the System V AMD64 ABI calling convention:
Integer/Pointer Arguments: - 1st argument: rdi - 2nd argument: rsi - 3rd argument: rdx -
4th argument: rcx - 5th argument: r8 - 6th argument: r9 - Additional arguments: stack
Floating-Point Arguments: - 1st-8th arguments: xmm0-xmm7
Return Values: - Integer/pointer: rax - Floating-point: xmm0 - String: rax (pointer), rdx (length)
Callee-Saved Registers: - rbx, rbp, r12-r15 must be preserved by called functions - All other
registers are caller-saved
This convention ensures that runtime functions can call libc functions and that compiled BASIC
code can call runtime functions seamlessly.

7.3.5 Libc Integration

The runtime library uses libc for most low-level operations:
• I/O: printf, scanf, fopen, fclose, fprintf, fscanf, fgets
• String: strlen, memcpy, memcmp, strtod, sprintf
• Memory: malloc, free
• Math: pow (for exponentiation)
• Time: time (for TIMER function)
Platform Differences:
On macOS, C library functions require an underscore prefix (_printf), while on Linux they don’t
(printf). The runtime code uses a placeholder {libc} that’s replaced with the appropriate prefix
at compile time:
call {libc}printf # Becomes "call _printf" on macOS, "call printf" on Linux
This is handled by src/[Link]:
#[cfg(target_os = "macos")]
let libc_prefix = "_";
#[cfg(not(target_os = "macos"))]
let libc_prefix = "";

output.push_str(&PRINT_FUNCS.replace("{libc}", libc_prefix));

7.3.6 Runtime Initialization

The runtime library requires minimal initialization:
Data Section: - Format strings for printf/scanf - Static buffers for string conversion - Random
number generator state - ANSI escape sequences

124
No Explicit Initialization: - Most runtime state is initialized statically in the data section - The
RNG state is initialized to a fixed seed (programs can call RANDOMIZE to reseed) - No constructor
functions need to be called
This simplicity means compiled programs can start executing immediately without runtime setup
overhead.

7.4 String Handling

7.4.1 String Representation
BASIC strings in xbasic64 are represented as (pointer, length) pairs, not null-terminated C
strings. This representation has several advantages:
Advantages: 1. O(1) length queries: Length is stored, not computed 2. Efficient substrings:
LEFT$, MID$, RIGHT$ return pointers into the original string without copying 3. Embedded nulls:
Strings can contain null characters 4. No buffer overruns: Length is always known
Memory Layout:
When a string variable is stored on the stack, it occupies 16 bytes (two 8-byte slots):
High addresses
�������������������
� String pointer � [rbp - 8] (rax register)
�������������������
� String length � [rbp - 16] (rdx register)
�������������������
Low addresses
Example:
Name$ = "Alice"
After this assignment: - [rbp - 8] contains a pointer to heap memory holding “Alice” - [rbp -
16] contains 5 (the length)

7.4.2 String Return Convention

Runtime functions that return strings use a two-register convention:
• rax: Pointer to string data
• rdx: String length
This matches the stack storage layout and allows efficient string passing without memory copies.
Example:
; Call CHR$(65) to get "A"
mov rdi, 65 # ASCII code for 'A'
call _rt_chr # Returns: rax = pointer, rdx = 1

; Store result in Name$

125
mov QWORD PTR [rbp-8], rax # Store pointer
mov QWORD PTR [rbp-16], rdx # Store length

7.4.3 String Operations

The runtime library provides several string manipulation functions:

[Link] String Conversion Functions

_rt_val - Convert String to Number (VAL function)
Parses a string as a floating-point number using libc’s strtod:
; VAL("123.45")
lea rdi, [rip + .Lstr_1] # String pointer
mov rsi, 6 # String length (ignored by strtod)
call _rt_val # Returns: xmm0 = 123.45
Implementation:
_rt_val:
push rbp
mov rbp, rsp
xor rsi, rsi # endptr = NULL
call {libc}strtod # Parse string, returns double in xmm0
leave
ret
_rt_str - Convert Number to String (STR$ function)
Formats a number as a string using sprintf with %g format (compact representation):
; STR$(3.14159)
movsd xmm0, QWORD PTR [rbp-8] # Load number
call _rt_str # Returns: rax = pointer, rdx = length
Implementation:
_rt_str:
push rbp
mov rbp, rsp
sub rsp, 16

; sprintf(_str_buf, "%g", value)

lea rdi, [rip + _str_buf]
lea rsi, [rip + _fmt_float]
mov eax, 1 # 1 vector register arg
call {libc}sprintf

; Calculate length by scanning for null terminator

lea rax, [rip + _str_buf]
mov rdx, rax
xor rcx, rcx

126
.Lstr_len:
cmp BYTE PTR [rax + rcx], 0
je .Lstr_done
inc rcx
jmp .Lstr_len
.Lstr_done:
mov rax, rdx
mov rdx, rcx # Length in rdx
leave
ret
Note: Uses static buffer _str_buf (64 bytes). Result is only valid until the next STR$() call.
_rt_chr - Convert ASCII Code to Character (CHR$ function)
Creates a 1-character string from an ASCII code:
; CHR$(65) returns "A"
mov rdi, 65
call _rt_chr # Returns: rax = pointer, rdx = 1
Implementation:
_rt_chr:
push rbp
mov rbp, rsp
lea rax, [rip + _chr_buf]
mov BYTE PTR [rax], dil # Store character
mov BYTE PTR [rax + 1], 0 # Null terminate
mov rdx, 1 # Length = 1
leave
ret
Note: Uses static buffer _chr_buf (2 bytes). Result is only valid until the next CHR$() call.

[Link] Substring Functions

All substring functions are zero-copy operations—they return pointers into the original string
without allocating new memory.
_rt_left - Extract Leftmost Characters (LEFT$ function)
Returns the first N characters of a string:
; LEFT$("Hello", 3) returns "Hel"
lea rdi, [rip + .Lstr_1] # Source pointer
mov rsi, 5 # Source length
mov rdx, 3 # Count
call _rt_left # Returns: rax = pointer, rdx = 3
Implementation:
_rt_left:
mov rax, rdi # Result pointer = source pointer

127
 cmp rdx, rsi # If count > length
cmova rdx, rsi # count = length
ret
_rt_right - Extract Rightmost Characters (RIGHT$ function)
Returns the last N characters of a string:
; RIGHT$("Hello", 3) returns "llo"
lea rdi, [rip + .Lstr_1] # Source pointer
mov rsi, 5 # Source length
mov rdx, 3 # Count
call _rt_right # Returns: rax = pointer + 2, rdx = 3
Implementation:
_rt_right:
cmp rdx, rsi # If count > length
cmova rdx, rsi # count = length
mov rax, rdi # Start with source pointer
add rax, rsi # Point to end
sub rax, rdx # Back up by count
ret
_rt_mid - Extract Substring (MID$ function)
Returns a substring starting at a given position (1-based):
; MID$("Hello", 2, 3) returns "ell"
lea rdi, [rip + .Lstr_1] # Source pointer
mov rsi, 5 # Source length
mov rdx, 2 # Start position (1-based)
mov rcx, 3 # Count
call _rt_mid # Returns: rax = pointer + 1, rdx = 3
Implementation:
_rt_mid:
dec rdx # Convert to 0-based
cmp rdx, rsi # If start >= length
jae .Lmid_empty # return empty string

mov rax, rdi

add rax, rdx # Result pointer = source + start
sub rsi, rdx # Remaining = length - start

cmp rcx, 0 # If count < 0 (means "rest")

jl .Lmid_rest
cmp rcx, rsi # If count > remaining
cmova rcx, rsi # count = remaining
mov rdx, rcx
ret

128
.Lmid_rest:
mov rdx, rsi # Return rest of string
ret

.Lmid_empty:
mov rax, rdi
xor rdx, rdx # Length = 0
ret

[Link] String Search

_rt_instr - Find Substring Position (INSTR function)
Searches for a substring within a string, returning its 1-based position (or 0 if not found):
; INSTR("Hello World", "World") returns 7
lea rdi, [rip + .Lstr_haystack] # Haystack pointer
mov rsi, 11 # Haystack length
lea rdx, [rip + .Lstr_needle] # Needle pointer
mov rcx, 5 # Needle length
mov r8, 1 # Start position (1-based)
call _rt_instr # Returns: rax = 7
Implementation:
Uses memcmp to compare at each position:
_rt_instr:
push rbp
mov rbp, rsp
push rbx
push r12
push r13
push r14
push r15

; Save arguments in callee-saved registers

mov r12, rdi # Haystack pointer
mov r13, rsi # Haystack length
mov r14, rdx # Needle pointer
mov r15, rcx # Needle length
mov rbx, r8 # Start position

; Adjust for start position

dec rbx # Convert to 0-based
add r12, rbx # Advance haystack
sub r13, rbx # Reduce remaining length

; Special case: empty needle

test r15, r15

129
 jz .Linstr_at_start

.Linstr_loop:
; Check if enough room for needle
cmp r13, r15
jb .Linstr_not_found

; Compare: memcmp(haystack_pos, needle, needle_len)

mov rdi, r12
mov rsi, r14
mov rdx, r15
call {libc}memcmp
test eax, eax
jz .Linstr_found

; Not found at this position, advance

inc r12
dec r13
inc rbx
jmp .Linstr_loop

.Linstr_found:
mov rax, rbx
add rax, 1 # Convert to 1-based
jmp .Linstr_done

.Linstr_at_start:
mov rax, rbx
add rax, 1
jmp .Linstr_done

.Linstr_not_found:
xor rax, rax # Return 0

.Linstr_done:
pop r15
pop r14
pop r13
pop r12
pop rbx
leave
ret

[Link] String Concatenation

_rt_strcat - Concatenate Strings (+ operator)
Allocates new memory and copies both strings:

130
; "Hello" + " World"
lea rdi, [rip + .Lstr_left] # Left pointer
mov rsi, 5 # Left length
lea rdx, [rip + .Lstr_right] # Right pointer
mov rcx, 6 # Right length
call _rt_strcat # Returns: rax = new pointer, rdx = 11
Implementation:
_rt_strcat:
push rbp
mov rbp, rsp
push r12
push r13
push r14
push r15

; Save arguments
mov r12, rdi # Left pointer
mov r13, rsi # Left length
mov r14, rdx # Right pointer
mov r15, rcx # Right length

; Allocate memory: malloc(left_len + right_len + 1)

lea rdi, [rsi + rcx + 1]
call {libc}malloc

; Copy left string: memcpy(result, left, left_len)

mov rdi, rax
mov rsi, r12
mov rdx, r13
push rax
call {libc}memcpy

; Copy right string: memcpy(result + left_len, right, right_len)

pop rdi
push rdi
add rdi, r13
mov rsi, r14
mov rdx, r15
call {libc}memcpy

; Null terminate
pop rax
lea rcx, [r13 + r15] # Total length
mov BYTE PTR [rax + rcx], 0

; Return: rax = pointer, rdx = length

mov rdx, rcx

131
 pop r15
pop r14
pop r13
pop r12
leave
ret
Memory Management:
String concatenation allocates heap memory using malloc. In xbasic64’s simple memory model,
this memory is never freed—the program relies on the OS to reclaim memory when the process
exits. For long-running programs with many string operations, this could lead to memory leaks. A
production compiler would implement garbage collection or reference counting.

7.4.4 Static Buffers

Some runtime functions use static buffers for temporary storage:

Buffer Size Used By Notes

_str_buf 64 bytes STR$() Numeric-to-string conversion
_chr_buf 2 bytes CHR$() Single character + null
_input_buf 1024 bytes INPUT Console string input
_file_input_buf 1024 bytes INPUT# File string input
_file_name_buf 1024 bytes OPEN Null-terminated filename

Important: Functions using static buffers return pointers that are only valid until the next call
to the same function. For example:
A$ = STR$(123)
B$ = STR$(456)
PRINT A$ ' Prints "456" (not "123"!) because A$ points to overwritten buffer
To avoid this issue, the compiler should copy static buffer results to heap-allocated strings when
they’re assigned to variables. Currently, xbasic64 doesn’t do this, which is a known limitation.

7.5 I/O Operations

7.5.1 Console Output (PRINT Statement)
The PRINT statement is implemented through several runtime functions that handle different data
types:

[Link] Print Functions

_rt_print_string - Print a String
Prints a BASIC string (pointer, length pair) using printf with precision specifier:

132
; PRINT "Hello"
lea rdi, [rip + .Lstr_1] # String pointer
mov rsi, 5 # String length
call _rt_print_string
Implementation:
_rt_print_string:
push rbp
mov rbp, rsp

; Rearrange arguments for printf("%.*s", len, ptr)

mov rdx, rdi # ptr → rdx (3rd arg)
; rsi already has len (2nd arg, as precision)
lea rdi, [rip + _fmt_str] # format string → rdi (1st arg)
xor eax, eax # no vector registers
call {libc}printf

leave
ret
Format string: "%.*s" - The .* precision specifier takes the length as an argument, allowing us
to print non-null-terminated strings.
_rt_print_float - Print a Number
Prints a numeric value, automatically choosing between integer and floating-point format:
; PRINT 3.14159
movsd xmm0, QWORD PTR [rbp-8]
call _rt_print_float
Implementation:
_rt_print_float:
push rbp
mov rbp, rsp
sub rsp, 16

; Check if value is a whole number

cvttsd2si rax, xmm0 # Truncate to integer
cvtsi2sd xmm1, rax # Convert back to double
ucomisd xmm0, xmm1 # Compare original with truncated
jne .Lprint_as_float

; Print as integer (cleaner output)

mov rsi, rax
lea rdi, [rip + _fmt_int] # "%ld"
xor eax, eax
call {libc}printf
jmp .Lprint_float_done

133
.Lprint_as_float:
; Print as floating point
lea rdi, [rip + _fmt_float] # "%g"
mov eax, 1 # 1 vector register argument
call {libc}printf

.Lprint_float_done:
leave
ret
Smart Formatting: - Whole numbers (3.0, 42.0) print without decimal point: 3, 42 - Fractional
numbers print with decimals: 3.14159 - Uses %g format which automatically chooses between %f
and %e notation
_rt_print_char - Print a Single Character
Prints a single ASCII character:
; PRINT CHR$(65) ' Prints "A"
mov rdi, 65
call _rt_print_char
Implementation:
_rt_print_char:
push rbp
mov rbp, rsp
mov rsi, rdi # char → rsi (2nd arg)
lea rdi, [rip + _fmt_char] # "%c"
xor eax, eax
call {libc}printf
leave
ret
_rt_print_newline - Print a Newline
Prints a newline character (called at end of PRINT statement unless suppressed with ; or ,):
; PRINT "Hello" (implicit newline)
lea rdi, [rip + .Lstr_1]
mov rsi, 5
call _rt_print_string
call _rt_print_newline # Add newline
Implementation:
_rt_print_newline:
push rbp
mov rbp, rsp
lea rdi, [rip + _fmt_newline] # "\n"
xor eax, eax
call {libc}printf

134
 leave
ret

[Link] PRINT Statement Compilation

The compiler generates different code depending on the PRINT statement format:
Simple PRINT:
PRINT "Hello"
Generated assembly:
lea rdi, [rip + .Lstr_1]
mov rsi, 5
call _rt_print_string
call _rt_print_newline
PRINT with semicolon (suppress newline):
PRINT "Hello";
Generated assembly:
lea rdi, [rip + .Lstr_1]
mov rsi, 5
call _rt_print_string
; No newline call
PRINT with multiple items:
PRINT "X ="; X
Generated assembly:
lea rdi, [rip + .Lstr_1]
mov rsi, 4
call _rt_print_string
movsd xmm0, QWORD PTR [rbp-8]
call _rt_print_float
call _rt_print_newline

7.5.2 Console Input (INPUT Statement)

The INPUT statement reads data from the keyboard:
_rt_input_number - Read a Number
Reads a double-precision floating-point number:
; INPUT X
call _rt_input_number # Returns: xmm0 = value
movsd QWORD PTR [rbp-8], xmm0 # Store in X
Implementation:

135
_rt_input_number:
push rbp
mov rbp, rsp
sub rsp, 16

; scanf("%lf", &result)
lea rsi, [rbp - 8] # Address of local variable
lea rdi, [rip + _fmt_input] # "%lf"
xor eax, eax
call {libc}scanf

; Consume trailing newline

call {libc}getchar

; Load result into xmm0

movsd xmm0, QWORD PTR [rbp - 8]
leave
ret
Note: getchar() is called after scanf to consume the trailing newline that scanf leaves in the
input buffer.
_rt_input_string - Read a String
Reads a line of text (up to 1023 characters):
; INPUT Name$
call _rt_input_string # Returns: rax = pointer, rdx = length
mov QWORD PTR [rbp-8], rax # Store pointer
mov QWORD PTR [rbp-16], rdx # Store length
Implementation:
_rt_input_string:
push rbp
mov rbp, rsp
sub rsp, 16

; Clear buffer for empty input case

lea rdi, [rip + _input_buf]
mov BYTE PTR [rdi], 0

; scanf("%1023[^\n]", buffer)
lea rsi, [rip + _input_buf]
lea rdi, [rip + _fmt_input_str] # "%1023[^\n]"
xor eax, eax
call {libc}scanf

; Consume trailing newline

call {libc}getchar

136
 ; Calculate string length
lea rax, [rip + _input_buf]
xor rdx, rdx
.Linput_len:
cmp BYTE PTR [rax + rdx], 0
je .Linput_done
inc rdx
jmp .Linput_len
.Linput_done:
leave
ret
Format string: "%1023[^\n]" - Reads up to 1023 characters, stopping at newline (which is not
included in the result).

7.5.3 File I/O

xbasic64 supports file operations through the OPEN, CLOSE, PRINT#, and INPUT# statements:

[Link] File Handle Management

Files are referenced by number (1-15). The runtime maintains a table of FILE pointers:
.data
_file_handles: .skip 128 # 16 * 8 bytes = 16 FILE* pointers
Index 0 is unused; indices 1-15 correspond to BASIC file numbers #1-#15.

[Link] File Operations

_rt_file_open - Open a File (OPEN statement)
Associates a filename with a file number:
OPEN "[Link]" FOR OUTPUT AS #1
Generated assembly:
lea rdi, [rip + .Lstr_filename] # Filename pointer
mov rsi, 8 # Filename length
mov rdx, 1 # Mode: 1=OUTPUT
mov rcx, 1 # File number: #1
call _rt_file_open
Modes: - 0 = INPUT (read, “r”) - 1 = OUTPUT (write/create, “w”) - 2 = APPEND (append,
“a”)
Implementation:
_rt_file_open:
push rbp
mov rbp, rsp
push rbx
push r12

137
 push r13
push r14

; Save arguments
mov r12, rdi # Filename pointer
mov r13, rsi # Filename length
mov r14d, edx # Mode
mov ebx, ecx # File number

; Copy filename to buffer and null-terminate

lea rdi, [rip + _file_name_buf]
mov rsi, r12
mov rdx, r13
call {libc}memcpy
lea rax, [rip + _file_name_buf]
mov BYTE PTR [rax + r13], 0

; Select mode string

cmp r14d, 0
je .Lmode_read
cmp r14d, 1
je .Lmode_write
lea rsi, [rip + _mode_append]
jmp .Ldo_fopen
.Lmode_read:
lea rsi, [rip + _mode_read]
jmp .Ldo_fopen
.Lmode_write:
lea rsi, [rip + _mode_write]

.Ldo_fopen:
; fopen(filename, mode)
lea rdi, [rip + _file_name_buf]
call {libc}fopen

; Store FILE* in handle table

lea rcx, [rip + _file_handles]
mov [rcx + rbx*8], rax

pop r14
pop r13
pop r12
pop rbx
leave
ret
_rt_file_close - Close a File (CLOSE statement)
Closes a file and clears its handle:

138
CLOSE #1
Generated assembly:
mov rdi, 1 # File number
call _rt_file_close
Implementation:
_rt_file_close:
push rbp
mov rbp, rsp

; Get FILE* from handle table

lea rax, [rip + _file_handles]
mov rdi, [rax + rdi*8]
test rdi, rdi # Check for NULL
jz .Lclose_done
call {libc}fclose
.Lclose_done:
leave
ret
_rt_file_print_string - Write String to File (PRINT# statement)
Writes a string to a file:
PRINT #1, "Hello"
Generated assembly:
mov rdi, 1 # File number
lea rsi, [rip + .Lstr_1] # String pointer
mov rdx, 5 # String length
call _rt_file_print_string
Implementation:
_rt_file_print_string:
push rbp
mov rbp, rsp
push rbx
sub rsp, 8

mov ebx, edi # Save file number

mov rcx, rsi # String pointer → 4th arg
mov r8, rdx # String length → will become 3rd arg

; Get FILE* from handle table

lea rax, [rip + _file_handles]
mov rdi, [rax + rbx*8] # FILE* → 1st arg

; fprintf(file, "%.*s", len, ptr)

139
 lea rsi, [rip + _file_fmt_str]
mov rdx, r8 # Length (precision)
xor eax, eax
call {libc}fprintf

add rsp, 8
pop rbx
leave
ret
_rt_file_print_float - Write Number to File
Similar to _rt_print_float, but writes to a file instead of stdout.
_rt_file_input_number - Read Number from File (INPUT# statement)
Reads a number from a file:
INPUT #1, X
Generated assembly:
mov rdi, 1 # File number
call _rt_file_input_number # Returns: xmm0 = value
movsd QWORD PTR [rbp-8], xmm0 # Store in X
_rt_file_input_string - Read String from File
Reads a line from a file using fgets:
INPUT #1, Name$
Generated assembly:
mov rdi, 1 # File number
call _rt_file_input_string # Returns: rax = pointer, rdx = length
mov QWORD PTR [rbp-8], rax # Store pointer
mov QWORD PTR [rbp-16], rdx # Store length
Implementation:
_rt_file_input_string:
push rbp
mov rbp, rsp
push rbx
sub rsp, 8

mov ebx, edi # Save file number

; fgets(buffer, size, file)

lea rdi, [rip + _file_input_buf]
mov rsi, 1023
lea rax, [rip + _file_handles]
mov rdx, [rax + rbx*8] # FILE*
call {libc}fgets

140
 ; Check for EOF/error
test rax, rax
jz .Lfile_input_string_empty

; Calculate length using strlen

lea rdi, [rip + _file_input_buf]
call {libc}strlen
mov rdx, rax

; Strip trailing newline if present

test rdx, rdx
jz .Lfile_input_string_done
lea rax, [rip + _file_input_buf]
mov cl, BYTE PTR [rax + rdx - 1]
cmp cl, 10 # Newline?
jne .Lfile_input_string_done
dec rdx # Reduce length
mov BYTE PTR [rax + rdx], 0 # Remove newline

.Lfile_input_string_done:
lea rax, [rip + _file_input_buf]
add rsp, 8
pop rbx
leave
ret

.Lfile_input_string_empty:
lea rax, [rip + _file_input_buf]
mov BYTE PTR [rax], 0
xor edx, edx
add rsp, 8
pop rbx
leave
ret

7.5.4 DATA/READ/RESTORE Support

The DATA, READ, and RESTORE statements allow programs to embed constant data:

[Link] Data Table Format

The compiler collects all DATA values and emits them into a table in the .data section. Each entry
is 16 bytes:
Offset Size Content
------ ---- -------
0 8 Type tag: 0=integer, 1=float, 2=string
8 8 Value: integer, double bits, or string pointer

141
Example:
DATA 42, 3.14, "hello"
Generates:
.data
_data_table:
.quad 0 # Type: integer
.quad 42 # Value: 42
.quad 1 # Type: float
.quad 0x40091EB851EB851F # Value: 3.14 (double bits)
.quad 2 # Type: string
.quad .Ldata_str_1 # Value: pointer to "hello"

_data_count: .quad 3 # Number of entries

_data_ptr: .quad 0 # Current read position

[Link] Runtime Functions

_rt_read_number - Read Next DATA Value as Number
; READ X
call _rt_read_number # Returns: xmm0 = value
movsd QWORD PTR [rbp-8], xmm0
_rt_read_string - Read Next DATA Value as String
; READ Name$
call _rt_read_string # Returns: rax = pointer, rdx = length
mov QWORD PTR [rbp-8], rax
mov QWORD PTR [rbp-16], rdx
_rt_restore - Reset DATA Pointer
; RESTORE
xor rdi, rdi # Position = 0
call _rt_restore

7.6 Math Functions

7.6.1 Implementation Strategies
xbasic64 uses two strategies for implementing math functions:
1. Inline Generation (Most Functions)
Simple math functions are generated inline by the code generator using x86-64 instructions:
• Arithmetic: +, -, *, /, \, MOD - Integer and SSE instructions
• Trigonometry: SIN, COS, TAN - x87 FPU instructions (fsin, fcos, fptan)
• Logarithms: LOG, EXP - x87 FPU instructions (fyl2x, f2xm1)
• Square Root: SQR - SSE instruction (sqrtsd)
• Absolute Value: ABS - Bit manipulation or conditional move

142
 • Sign: SGN - Comparison and conditional moves
These functions are implemented directly in src/[Link] and don’t require runtime support.
2. Runtime Library Functions (Complex Operations)
More complex operations are implemented in the runtime library:
• Exponentiation: ^ operator - Uses libc pow()
• Random Numbers: RND - Custom Xorshift64 PRNG
• Timer: TIMER - Uses libc time()
• Screen Control: CLS - ANSI escape sequences

7.6.2 Runtime Math Functions

_rt_rnd - Random Number Generator (RND function)
Returns a pseudo-random number in the range [0, 1) using the Xorshift64 algorithm:
; X = RND(1)
movsd xmm0, QWORD PTR [rbp-8] # Seed (ignored in current implementation)
call _rt_rnd # Returns: xmm0 = random value in [0, 1)
movsd QWORD PTR [rbp-16], xmm0 # Store in X
Implementation:
_rt_rnd:
push rbp
mov rbp, rsp

; Load current state

mov rax, QWORD PTR [rip + _rng_state]

; Xorshift64 algorithm
mov rcx, rax
shl rcx, 13
xor rax, rcx # state ^= state << 13

mov rcx, rax

shr rcx, 7
xor rax, rcx # state ^= state >> 7

mov rcx, rax

shl rcx, 17
xor rax, rcx # state ^= state << 17

; Save new state

mov QWORD PTR [rip + _rng_state], rax

; Convert to double in [0, 1)

shr rax, 12 # Keep top 52 bits
mov rcx, 0x3FF0000000000000 # IEEE 754: exponent=1023 (value=1.0)

143
 or rax, rcx # Combine: value in [1, 2)
movq xmm0, rax

; Subtract 1.0 to get [0, 1)

mov rcx, 0x3FF0000000000000
movq xmm1, rcx
subsd xmm0, xmm1

leave
ret
Algorithm: Xorshift64
Xorshift64 is a fast, high-quality pseudo-random number generator with 64-bit state:
1. Apply three XOR-shift operations to the state
2. Period: 2^64 - 1 (all non-zero states)
3. Passes statistical tests (TestU01 SmallCrush)
Conversion to [0, 1):
1. Take top 52 bits of state (mantissa precision of IEEE 754 double)
2. Set exponent to 1023 (representing 1.0 in binary: [Link])
3. This gives a value in [1, 2)
4. Subtract 1.0 to get [0, 1)
Initial State:
.data
_rng_state: .quad 0x12345678DEADBEEF
The RNG is initialized with a fixed seed. Programs can call RANDOMIZE to reseed based on the
current time (though this isn’t currently implemented in xbasic64).
_rt_timer - Seconds Since Midnight (TIMER function)
Returns the number of seconds elapsed since midnight as a floating-point number:
; T = TIMER
call _rt_timer # Returns: xmm0 = seconds since midnight
movsd QWORD PTR [rbp-8], xmm0
Implementation:
_rt_timer:
push rbp
mov rbp, rsp
sub rsp, 16

; time(NULL) returns seconds since epoch

xor rdi, rdi
call {libc}time # Returns: rax = Unix timestamp

; Compute seconds mod 86400 (seconds per day)

144
 xor rdx, rdx
mov rcx, 86400
div rcx # rax = quotient, rdx = remainder

; Convert remainder to double

cvtsi2sd xmm0, rdx

leave
ret
Note: This returns UTC-based “seconds since midnight”, not local time. For timing purposes
(measuring elapsed time), this doesn’t matter.
_rt_cls - Clear Screen (CLS statement)
Clears the terminal screen using ANSI escape sequences:
; CLS
call _rt_cls
Implementation:
_rt_cls:
push rbp
mov rbp, rsp
lea rdi, [rip + _cls_seq] # ANSI escape sequence
xor eax, eax
call {libc}printf
leave
ret
ANSI Escape Sequence:
.data
_cls_seq: .asciz "\033[2J\033[H"
• \033[2J - Clear entire screen
• \033[H - Move cursor to home position (top-left)
This works on most modern terminals (Linux, macOS, Windows 10+).

7.6.3 Inline Math Functions

While not part of the runtime library, it’s worth noting how common math functions are imple-
mented inline:
Trigonometric Functions (x87 FPU)
; Y = SIN(X)
movsd xmm0, QWORD PTR [rbp-8] # Load X
sub rsp, 8 # Align stack
movsd [rsp], xmm0 # Store to memory
fld QWORD PTR [rsp] # Load to x87 stack
fsin # Compute sine

145
fstp QWORD PTR [rsp] # Store result
movsd xmm0, [rsp] # Load to SSE
add rsp, 8
movsd QWORD PTR [rbp-16], xmm0 # Store in Y
Square Root (SSE)
; Y = SQR(X)
movsd xmm0, QWORD PTR [rbp-8] # Load X
sqrtsd xmm0, xmm0 # Compute square root
movsd QWORD PTR [rbp-16], xmm0 # Store in Y
Exponentiation (libc pow)
; Y = X ^ 2.5
movsd xmm0, QWORD PTR [rbp-8] # Load X (base)
movsd xmm1, QWORD PTR [rbp-16] # Load 2.5 (exponent)
call {libc}pow # Returns: xmm0 = X ^ 2.5
movsd QWORD PTR [rbp-24], xmm0 # Store in Y
Absolute Value (Bit Manipulation)
; Y = ABS(X)
movsd xmm0, QWORD PTR [rbp-8] # Load X
mov rax, 0x7FFFFFFFFFFFFFFF # Mask: clear sign bit
movq xmm1, rax
andpd xmm0, xmm1 # Clear sign bit
movsd QWORD PTR [rbp-16], xmm0 # Store in Y
Sign Function (Comparison)
; Y = SGN(X)
movsd xmm0, QWORD PTR [rbp-8] # Load X
xorpd xmm1, xmm1 # Zero
ucomisd xmm0, xmm1 # Compare X with 0
ja .Lsgn_positive # X > 0
jb .Lsgn_negative # X < 0
xor eax, eax # X = 0, result = 0
jmp .Lsgn_done
.Lsgn_positive:
mov eax, 1 # Result = 1
jmp .Lsgn_done
.Lsgn_negative:
mov eax, -1 # Result = -1
.Lsgn_done:
cvtsi2sd xmm0, eax # Convert to double
movsd QWORD PTR [rbp-16], xmm0 # Store in Y

7.6.4 Math Function Summary

146
Function Implementation Location Notes
+, -, *, / SSE instructions Inline addsd, subsd,
mulsd, divsd
\ (integer div) Integer division Inline idiv
instruction
MOD Integer modulo Inline idiv
(remainder in
edx)
^ (power) libc pow() Inline call Always
returns
Double
SIN, COS, TAN x87 FPU Inline fsin, fcos,
fptan
ASIN, ACOS, ATAN x87 FPU Inline fpatan with
setup
LOG x87 FPU Inline fyl2x (log
base 2, scaled)
EXP x87 FPU Inline f2xm1 (2^x -
1, adjusted)
SQR SSE Inline sqrtsd
ABS Bit manipulation Inline Clear sign bit
SGN Comparison Inline Compare with
zero
INT Truncation Inline cvttsd2si
then cvtsi2sd
FIX Truncation Inline Same as INT
RND Xorshift64 PRNG Runtime _rt_rnd
TIMER Unix time mod 86400 Runtime _rt_timer
CLS ANSI escape Runtime _rt_cls

7.6.5 Why Inline vs. Runtime?

Inline generation is preferred when: - The operation is simple (1-3 instructions) - No memory
allocation or complex state is needed - The operation is performance-critical
Runtime functions are used when: - The operation is complex (many instructions) - State
management is required (RNG state, file handles) - Platform-specific code is needed (system calls)
- Code size matters (avoid duplicating large code blocks)
For xbasic64, most math functions are simple enough to generate inline, which produces faster code
by avoiding function call overhead.

7.7 Runtime Implementation Overview

7.7.1 Source File Organization
The runtime library is split into multiple assembly files for maintainability and clarity. Each file
focuses on a specific category of functionality:

147
[Link] src/runtime/data_defs.s - Data Section Definitions
Contains all static data used by the runtime:
Format Strings:
_fmt_str: .asciz "%.*s" # String with precision (for PRINT)
_fmt_int: .asciz "%ld" # Long integer
_fmt_float: .asciz "%g" # Floating point (compact)
_fmt_char: .asciz "%c" # Single character
_fmt_newline: .asciz "\n" # Newline
_fmt_input: .asciz "%lf" # Read double (for INPUT)
_fmt_input_str: .asciz "%1023[^\n]" # Read string (for INPUT)
Static Buffers:
_input_buf: .skip 1024 # Console string input buffer
_chr_buf: .skip 2 # CHR$() result buffer
_str_buf: .skip 64 # STR$() result buffer
Global State:
_rng_state: .quad 0x12345678DEADBEEF # RNG state (Xorshift64)
_cls_seq: .asciz "\033[2J\033[H" # ANSI clear screen sequence
Purpose: Centralizes all data definitions in one place, making it easy to see what static resources
the runtime uses.

[Link] src/runtime/print.s - Print Functions

Implements output functions for the PRINT statement:
Functions: - _rt_print_string - Print a BASIC string (pointer, length pair) - _rt_print_char -
Print a single ASCII character - _rt_print_newline - Print a newline - _rt_print_float - Print
a number (smart formatting: integers without decimals)
Key Features: - Uses printf with format strings from data_defs.s - Smart number formatting
(3.0 prints as “3”, 3.14 prints as “3.14”) - Handles BASIC’s (pointer, length) string representation
Lines of Code: ~100 lines

[Link] src/runtime/input.s - Input Functions

Implements input functions for the INPUT statement:
Functions: - _rt_input_string - Read a line of text from stdin - _rt_input_number - Read a
numeric value from stdin
Key Features: - Uses scanf for parsing - Consumes trailing newlines with getchar() - Calculates
string length by scanning for null terminator - Handles empty input gracefully
Lines of Code: ~80 lines

148
[Link] src/runtime/string.s - String Functions
Implements string manipulation operations:
Conversion Functions: - _rt_val - Convert string to number (VAL function) - _rt_str - Convert
number to string (STR$ function) - _rt_chr - Convert ASCII code to character (CHR$ function)
Substring Functions (Zero-Copy): - _rt_left - Extract leftmost characters (LEFT$ function) -
_rt_right - Extract rightmost characters (RIGHT$ function) - _rt_mid - Extract substring (MID$
function)
Search and Concatenation: - _rt_instr - Find substring position (INSTR function) -
_rt_strcat - Concatenate strings (+ operator)
Key Features: - Substring functions are zero-copy (return pointers into original string) - String
concatenation allocates new memory with malloc - Uses memcmp for efficient substring search -
Conversion functions use static buffers
Lines of Code: ~300 lines

[Link] src/runtime/math.s - Math and Utility Functions

Implements miscellaneous functions:
Functions: - _rt_rnd - Random number generator (RND function) - _rt_timer - Seconds since
midnight (TIMER function) - _rt_cls - Clear screen (CLS statement)
Key Features: - Xorshift64 PRNG for high-quality random numbers - Uses time() for TIMER -
ANSI escape sequences for CLS
Lines of Code: ~100 lines
Note: Most math functions (SIN, COS, SQR, etc.) are implemented inline by the code generator,
not in the runtime library.

[Link] src/runtime/data.s - DATA/READ/RESTORE Support

Implements support for BASIC’s DATA statements:
Functions: - _rt_read_number - Read next DATA value as number - _rt_read_string - Read
next DATA value as string - _rt_restore - Reset DATA pointer
Key Features: - Reads from compiler-generated _data_table - Handles type conversion (inte-
ger/float/string) - Maintains read position in _data_ptr
Lines of Code: ~120 lines
Data Table Format: Each entry is 16 bytes: - Bytes 0-7: Type tag (0=int, 1=float, 2=string) -
Bytes 8-15: Value (integer, double bits, or string pointer)

[Link] src/runtime/file.s - File I/O Functions

Implements file operations:
File Management: - _rt_file_open - Open a file (OPEN statement) - _rt_file_close - Close
a file (CLOSE statement)

149
File Output: - _rt_file_print_string - Write string to file (PRINT# statement) -
_rt_file_print_float - Write number to file - _rt_file_print_char - Write character to
file - _rt_file_print_newline - Write newline to file
File Input: - _rt_file_input_number - Read number from file (INPUT# statement) -
_rt_file_input_string - Read string from file
Key Features: - Uses libc file operations (fopen, fclose, fprintf, fscanf, fgets) - Maintains
file handle table (16 FILE* pointers) - Supports three modes: INPUT (read), OUTPUT (write),
APPEND - Null-terminates filenames for libc compatibility
Lines of Code: ~400 lines

7.7.2 Runtime Assembly Process

The src/[Link] module assembles all runtime components into a single assembly output:
pub fn generate_runtime() -> String {
// Platform-specific libc prefix
#[cfg(target_os = "macos")]
let libc_prefix = "_";
#[cfg(not(target_os = "macos"))]
let libc_prefix = "";

let mut output = String::new();

// Header
output.push_str("# BASIC Runtime Library\n");
output.push_str(".intel_syntax noprefix\n\n");

// Data section
output.push_str(DATA_DEFS);
output.push_str("\[Link]\n\n");

// Function sections (with libc prefix replacement)

output.push_str(&PRINT_FUNCS.replace("{libc}", libc_prefix));
output.push_str(&INPUT_FUNCS.replace("{libc}", libc_prefix));
output.push_str(&STRING_FUNCS.replace("{libc}", libc_prefix));
output.push_str(&MATH_FUNCS.replace("{libc}", libc_prefix));
output.push_str(&DATA_FUNCS.replace("{libc}", libc_prefix));
output.push_str(&FILE_FUNCS.replace("{libc}", libc_prefix));

output
}
Process: 1. Determine platform-specific libc prefix 2. Assemble header and data section 3. Con-
catenate all function sections 4. Replace {libc} placeholder with appropriate prefix 5. Return
complete assembly code
Result: A single assembly file containing the entire runtime library, ready to be appended to the
generated program code.

150
7.7.3 Linking Process
When compiling a BASIC program, xbasic64:
1. Generates program code from the AST
2. Appends runtime library using generate_runtime()
3. Writes combined assembly to a temporary file
4. Invokes system assembler (as) to create object file
5. Invokes linker (cc) to create executable, linking with libc
Example compilation:
# User runs:
xbasic64 [Link]

# Compiler internally does:

# 1. Parse [Link] → AST
# 2. Generate assembly from AST → program.s
# 3. Append runtime library → program.s
# 4. Assemble: as program.s -o program.o
# 5. Link: cc program.o -o program
The final executable contains both the compiled BASIC program and the runtime library, with no
external dependencies except libc.

7.7.4 Runtime Function Naming Convention

All runtime functions use the _rt_ prefix to avoid name collisions:
• _rt_print_* - Output functions
• _rt_input_* - Input functions
• _rt_file_* - File I/O functions
• _rt_* - Other runtime functions (string, math, etc.)
This convention makes it clear which functions are part of the runtime library when reading gener-
ated assembly code.

7.7.5 Performance Considerations

Function Call Overhead:
Runtime functions have call overhead (saving registers, stack alignment, etc.). For performance-
critical operations, the compiler generates inline code instead:
• Inline: Arithmetic, comparisons, simple math (SIN, COS, SQR)
• Runtime: I/O, string operations, complex algorithms
Static Buffers:
Functions like STR$() and CHR$() use static buffers to avoid heap allocation overhead. This is fast
but means results are only valid until the next call.
Zero-Copy Substrings:

151
LEFT$, RIGHT$, and MID$ return pointers into the original string without copying. This is extremely
fast (O(1)) but means the original string must remain valid.
Memory Allocation:
String concatenation (+) allocates heap memory with malloc. In xbasic64’s simple memory model,
this memory is never freed. For programs with many string operations, this could lead to memory
growth.

7.7.6 Debugging Runtime Functions

When debugging compiled BASIC programs, you can step through runtime functions in a debugger:
# Compile with debug symbols
xbasic64 [Link]
as -g program.s -o program.o
cc -g program.o -o program

# Debug with gdb

gdb program
(gdb) break _rt_print_string
(gdb) run
The runtime assembly code includes labels and comments that make it easier to understand what’s
happening at each step.

7.7.7 Extending the Runtime

To add a new runtime function:
1. Choose the appropriate file (print.s, string.s, etc.)
2. Write the assembly function following System V AMD64 ABI
3. Add any needed data to data_defs.s
4. Update [Link] if adding a new file
5. Generate calls from the code generator
Example: Adding a new string function
# In src/runtime/string.s

# _rt_reverse - Reverse a string

# Arguments:
# rdi = source pointer
# rsi = source length
# Returns:
# rax = new string pointer
# rdx = length
_rt_reverse:
push rbp
mov rbp, rsp
push r12
push r13

152
 mov r12, rdi # Save source pointer
mov r13, rsi # Save length

# Allocate memory
lea rdi, [rsi + 1] # length + 1 for null terminator
call {libc}malloc

# Copy characters in reverse

mov rcx, r13 # Counter
xor r8, r8 # Destination index
.Lreverse_loop:
test rcx, rcx
jz .Lreverse_done
dec rcx
mov dl, BYTE PTR [r12 + rcx] # Load from end
mov BYTE PTR [rax + r8], dl # Store at beginning
inc r8
jmp .Lreverse_loop

.Lreverse_done:
mov BYTE PTR [rax + r13], 0 # Null terminate
mov rdx, r13 # Return length

pop r13
pop r12
leave
ret
Then in the code generator, generate calls to _rt_reverse when compiling a hypothetical
REVERSE$() function.

7.8 Summary
The xbasic64 runtime library is a collection of assembly functions that provide essential services to
compiled BASIC programs. By centralizing complex operations like I/O, string manipulation, and
file handling in the runtime, the compiler can generate simpler, more maintainable code.
Key Takeaways:
1. Platform Abstraction: The runtime uses libc for portability across Linux and macOS, with
platform-specific prefixes handled at compile time.
2. String Representation: BASIC strings are (pointer, length) pairs, not null-terminated.
This enables efficient substring operations and O(1) length queries.
3. Zero-Copy Operations: Substring functions (LEFT$, RIGHT$, MID$) return pointers into
the original string without copying, providing excellent performance.
4. Smart Formatting: The print functions automatically format numbers cleanly (whole num-

153
 bers without decimals, fractional numbers with appropriate precision).
5. Modular Design: The runtime is organized into focused modules (print, input, string, math,
data, file), making it easy to understand and extend.
6. Inline vs. Runtime: Simple operations are generated inline for performance, while complex
operations use runtime functions for code reuse and maintainability.
7. System V AMD64 ABI: All runtime functions follow the standard calling convention,
ensuring seamless integration with libc and compiled BASIC code.
8. Static Buffers: Some functions use static buffers to avoid allocation overhead, trading off
thread-safety and persistence for performance.
The runtime library demonstrates how high-level language features are implemented at the assembly
level, bridging the gap between BASIC’s user-friendly syntax and the low-level operations required
to interact with the operating system.

7.9 Further Reading

7.9.1 Related Documentation
• Code Generation: Learn how the compiler generates calls to runtime functions
• Semantic Analysis: Understand the type system that runtime functions operate on
• Language Reference: Complete reference for all BASIC statements and functions

7.9.2 External Resources

System V AMD64 ABI: - System V AMD64 ABI Specification - Official calling convention
specification - x86-64 Calling Conventions - Wikipedia overview
x86-64 Assembly: - Intel 64 and IA-32 Architectures Software Developer Manuals - Complete
instruction reference - x86-64 Assembly Language Programming - Tutorial and reference
C Library (libc): - GNU C Library Manual - Documentation for libc functions - Linux man
pages - Reference for system calls and library functions
String Algorithms: - Boyer-Moore String Search - More efficient than the linear search used in
_rt_instr - Rope Data Structure - Efficient string concatenation for large strings
Random Number Generation: - Xorshift RNGs - Fast, high-quality PRNGs - TestU01 - Sta-
tistical test suite for RNGs - PCG Random - Modern PRNG family with better properties
Runtime System Design: - Crafting Interpreters - Chapter 24: Garbage Collection - Memory
management strategies - The Implementation of Lua 5.0 - Runtime design in a dynamic language -
CPython Internals - Python’s runtime implementation

7.9.3 Exercises
Try these exercises to deepen your understanding of the runtime system:
Beginner: 1. Add a BEEP statement that prints the ASCII bell character (7) 2. Implement
LCASE$() and UCASE$() functions for case conversion 3. Add a SPACE$() function that returns a
string of N spaces

154
Intermediate: 4. Implement proper memory management for string concatenation (reference
counting or garbage collection) 5. Add a REPLACE$() function that replaces all occurrences of a
substring 6. Implement LTRIM$() and RTRIM$() functions to remove leading/trailing whitespace
Advanced: 7. Replace the linear search in _rt_instr with Boyer-Moore algorithm 8. Implement
a rope data structure for efficient string concatenation 9. Add support for Unicode strings (UTF-8
encoding) 10. Implement a mark-and-sweep garbage collector for heap-allocated strings

Navigation: ← Back to Code Generation | Next: Language Reference →

155
Chapter 8

xbasic64 Language Reference

8.1 Overview
This document provides a complete formal specification of the BASIC dialect supported by xba-
sic64. It serves as both a reference for users writing BASIC programs and a specification for
compiler implementers. The language targets 1980s-era BASIC dialects, particularly GW-BASIC
and QuickBASIC, with some modern simplifications.
Key Characteristics: - Case-insensitive keywords and identifiers - Optional line numbers for
labels - Five data types with suffix notation - Implicit variable declaration - Pass-by-value parameter
semantics - Direct compilation to x86-64 native code

8.2 Table of Contents

1. Formal Grammar
2. Lexical Structure
3. Statements
4. Expressions
5. Language Examples

8.3 1. Formal Grammar

This section provides the complete grammar for xbasic64 in Extended Backus-Naur Form (EBNF).

8.3.1 1.1 Notation Conventions

The grammar uses the following EBNF notation:
::= Definition
| Alternative
( ) Grouping
[ ] Optional (zero or one)
{ } Repetition (zero or more)

156
" " Terminal symbol (literal)
< > Non-terminal symbol

8.3.2 1.2 Program Structure

<program> ::= { <statement> }

<statement> ::= [ <line-number> ] <stmt> ( <newline> | <colon> )

<line-number> ::= <integer>

<stmt> ::= <assignment-stmt>

| <print-stmt>
| <input-stmt>
| <line-input-stmt>
| <if-stmt>
| <for-stmt>
| <while-stmt>
| <do-loop-stmt>
| <select-case-stmt>
| <goto-stmt>
| <gosub-stmt>
| <return-stmt>
| <on-goto-stmt>
| <dim-stmt>
| <sub-stmt>
| <function-stmt>
| <call-stmt>
| <data-stmt>
| <read-stmt>
| <restore-stmt>
| <open-stmt>
| <close-stmt>
| <cls-stmt>
| <end-stmt>
| <stop-stmt>

8.3.3 1.3 Assignment Statement

<assignment-stmt> ::= [ "LET" ] <variable> "=" <expression>

<variable> ::= <identifier> [ "(" <expr-list> ")" ]

8.3.4 1.4 Print Statement

<print-stmt> ::= "PRINT" [ "#" <file-number> "," ] [ <print-list> ]

<print-list> ::= <print-item> { <separator> <print-item> } [ <separator> ]

157
<print-item> ::= <expression>

<separator> ::= ";" | ","

<file-number> ::= <integer>

8.3.5 1.5 Input Statements

<input-stmt> ::= "INPUT" [ "#" <file-number> "," ]
[ <string-literal> ( "," | ";" ) ]
<variable> { "," <variable> }

<line-input-stmt> ::= "LINE" "INPUT"

[ <string-literal> ( "," | ";" ) ]
<variable>

8.3.6 1.6 Control Flow Statements

<if-stmt> ::= "IF" <expression> "THEN" <then-part> [ <else-part> ]

<then-part> ::= <statement> (* single-line form *)

| <newline> { <statement> } (* block form *)

<else-part> ::= "ELSE" <statement> (* single-line form *)

| "ELSE" <newline> { <statement> } "END" "IF" (* block form *)
| "ELSEIF" <expression> "THEN" <then-part> [ <else-part> ]

<for-stmt> ::= "FOR" <identifier> "=" <expression> "TO" <expression>

[ "STEP" <expression> ]
<newline>
{ <statement> }
"NEXT" [ <identifier> ]

<while-stmt> ::= "WHILE" <expression>

<newline>
{ <statement> }
"WEND"

<do-loop-stmt> ::= "DO" [ <loop-condition> ]

<newline>
{ <statement> }
"LOOP" [ <loop-condition> ]

<loop-condition> ::= ( "WHILE" | "UNTIL" ) <expression>

<select-case-stmt> ::= "SELECT" "CASE" <expression>

<newline>
{ <case-clause> }

158
 "END" "SELECT"

<case-clause> ::= "CASE" <case-value>

<newline>
{ <statement> }

<case-value> ::= "ELSE"

| <expression> [ "TO" <expression> ]
| "IS" <relational-op> <expression>
| <expression> { "," <expression> }

8.3.7 1.7 Jump Statements

<goto-stmt> ::= "GOTO" <goto-target>

<gosub-stmt> ::= "GOSUB" <goto-target>

<return-stmt> ::= "RETURN"

<on-goto-stmt> ::= "ON" <expression> "GOTO" <goto-target> { "," <goto-target> }

<goto-target> ::= <line-number> | <identifier>

8.3.8 1.8 Array Declaration

<dim-stmt> ::= "DIM" <array-decl> { "," <array-decl> }

<array-decl> ::= <identifier> "(" <expr-list> ")"

8.3.9 1.9 Procedure Definitions

<sub-stmt> ::= "SUB" <identifier> [ "(" <param-list> ")" ]
<newline>
{ <statement> }
"END" "SUB"

<function-stmt> ::= "FUNCTION" <identifier> [ "(" <param-list> ")" ]

<newline>
{ <statement> }
"END" "FUNCTION"

<call-stmt> ::= <identifier> [ "(" <expr-list> ")" ]

| <identifier> <expr-list>

<param-list> ::= <identifier> { "," <identifier> }

159
8.3.10 1.10 Data Statements
<data-stmt> ::= "DATA" <literal> { "," <literal> }

<read-stmt> ::= "READ" <variable> { "," <variable> }

<restore-stmt> ::= "RESTORE" [ <goto-target> ]

8.3.11 1.11 File I/O Statements

<open-stmt> ::= "OPEN" <expression> "FOR" <file-mode> "AS" "#" <file-number>

<file-mode> ::= "INPUT" | "OUTPUT" | "APPEND"

<close-stmt> ::= "CLOSE" "#" <file-number>

8.3.12 1.12 Other Statements

<cls-stmt> ::= "CLS"

<end-stmt> ::= "END"

<stop-stmt> ::= "STOP"

8.3.13 1.13 Expressions

<expression> ::= <logical-or-expr>

<logical-or-expr> ::= <logical-xor-expr> { ( "OR" ) <logical-xor-expr> }

<logical-xor-expr> ::= <logical-and-expr> { ( "XOR" ) <logical-and-expr> }

<logical-and-expr> ::= <relational-expr> { ( "AND" ) <relational-expr> }

<relational-expr> ::= <additive-expr> [ <relational-op> <additive-expr> ]

<relational-op> ::= "=" | "<>" | "<" | ">" | "<=" | ">="

<additive-expr> ::= <multiplicative-expr> { ( "+" | "-" ) <multiplicative-expr> }

<multiplicative-expr> ::= <power-expr> { ( "*" | "/" | "\" | "MOD" ) <power-expr> }

<power-expr> ::= <unary-expr> [ "^" <power-expr> ]

<unary-expr> ::= [ "+" | "-" | "NOT" ] <primary-expr>

<primary-expr> ::= <literal>

| <variable>
| <function-call>

160
 | "(" <expression> ")"

<function-call> ::= <identifier> "(" [ <expr-list> ] ")"

<expr-list> ::= <expression> { "," <expression> }

8.3.14 1.14 Literals and Identifiers

<literal> ::= <integer> | <float> | <string-literal>

<integer> ::= <decimal-integer> | <hex-integer> | <octal-integer>

<decimal-integer> ::= <digit> { <digit> }

<hex-integer> ::= "&H" <hex-digit> { <hex-digit> }

| "&h" <hex-digit> { <hex-digit> }

<octal-integer> ::= "&O" <octal-digit> { <octal-digit> }

| "&o" <octal-digit> { <octal-digit> }

<float> ::= <digit> { <digit> } "." { <digit> } [ <exponent> ]

| "." <digit> { <digit> } [ <exponent> ]
| <digit> { <digit> } <exponent>

<exponent> ::= ( "E" | "e" | "D" | "d" ) [ "+" | "-" ] <digit> { <digit> }

<string-literal> ::= '"' { <string-char> } '"'

<string-char> ::= <any-char-except-quote> | '""'

<identifier> ::= <letter> { <letter> | <digit> | "_" } [ <type-suffix> ]

<type-suffix> ::= "%" | "&" | "!" | "#" | "$"

<letter> ::= "A" | "B" | ... | "Z" | "a" | "b" | ... | "z"

<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

<hex-digit> ::= <digit> | "A" | "B" | "C" | "D" | "E" | "F"

| "a" | "b" | "c" | "d" | "e" | "f"

<octal-digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7"

161
8.4 2. Lexical Structure
This section describes the lexical elements that make up xbasic64 programs: the character set,
comments, identifiers, keywords, literals, and operators.

8.4.1 2.1 Character Set and Encoding

Character Set: xbasic64 programs are written in ASCII text. While UTF-8 input is accepted by
the compiler, only ASCII characters (0x00-0x7F) are recognized as meaningful tokens in the source
code.
Case Sensitivity: The language is case-insensitive for keywords and identifiers. The following
are equivalent: - PRINT, Print, print, PrInT - MyVariable, MYVARIABLE, myvariable
The lexer converts all keywords and identifiers to uppercase internally.
Whitespace: Spaces, tabs, and carriage returns are treated as whitespace and are ignored except
as token separators. Newlines are significant as statement terminators.

8.4.2 2.2 Comments

xbasic64 supports two comment styles:
REM Comments:
REM This is a comment
10 PRINT "Hello" REM This is also valid
Apostrophe Comments:
' This is a comment
X = 42 ' This is an inline comment
Both comment styles extend from the comment marker to the end of the line. Comments are
treated as statement terminators by the lexer.

8.4.3 2.3 Line Numbers and Statement Separators

Line Numbers: Optional numeric labels that appear at the start of a line:
10 PRINT "Hello"
20 GOTO 10
Line numbers serve as targets for GOTO, GOSUB, and RESTORE statements. They must be non-negative
integers.
Statement Separators: - Newline: The primary statement separator - Colon (:): Allows
multiple statements on one line basic X = 1 : Y = 2 : PRINT X + Y

8.4.4 2.4 Identifiers

Syntax: Identifiers start with a letter (A-Z, a-z) followed by any combination of letters, digits
(0-9), or underscores (_).

162
Type Suffixes: Identifiers may end with a type suffix character: - % - Integer (16-bit signed) - &
- Long (32-bit signed) - ! - Single-precision float (32-bit) - # - Double-precision float (64-bit) - $ -
String
Examples:
Counter ' Unsuffixed (defaults to Double)
Count% ' Integer
TotalAmount& ' Long
Temperature! ' Single
PreciseValue# ' Double
UserName$ ' String
my_var_123 ' Valid identifier with underscore
Reserved Words: The following keywords cannot be used as identifiers:
AND APPEND AS CASE CLOSE CLS DATA
DIM DO ELSE ELSEIF END ENDIF ENDFUNCTION
ENDSUB ENDSELECT FOR FUNCTION GOSUB GOTO IF
INPUT LET LINE LOOP MOD NEXT NOT
ON OPEN OR OUTPUT PRINT READ REM
RESTORE RETURN SELECT STEP STOP SUB THEN
TO UNTIL WEND WHILE XOR

8.4.5 2.5 Literals

[Link] 2.5.1 Integer Literals
Decimal Integers:
42
-17
0
32767
Hexadecimal Integers: Prefixed with &H or &h:
&HFF ' 255 in decimal
&h10 ' 16 in decimal
&HFFFF ' 65535 in decimal
Octal Integers: Prefixed with &O or &o:
&O377 ' 255 in decimal
&o10 ' 8 in decimal

[Link] 2.5.2 Floating-Point Literals

Standard Notation:
3.14159
.5 ' Leading zero optional
2.0
-1.5

163
Scientific Notation: Using E or e for exponent:
1E5 ' 100000.0
2.5E-3 ' 0.0025
1.23E+10 ' 12300000000.0
Double-Precision Notation: Using D or d for exponent:
1D5 ' 100000.0 (double precision)
2.5D-3 ' 0.0025 (double precision)
The D exponent marker is converted to E internally but indicates double-precision intent.

[Link] 2.5.3 String Literals

Syntax: Enclosed in double quotes ("):
"Hello, World!"
"BASIC Programming"
"" ' Empty string
Embedded Quotes: Use two consecutive double quotes ("") to include a quote in a string:
"He said ""Hello""" ' Results in: He said "Hello"
"It's a ""test""" ' Results in: It's a "test"
Escape Sequences: xbasic64 does not support backslash escape sequences. Use "" for quotes and
CHR$() for special characters:
TAB$ = CHR$(9) ' Tab character
NEWLINE$ = CHR$(10) ' Newline character

8.4.6 2.6 Operators and Punctuation

Arithmetic Operators:
+ Addition
- Subtraction (also unary negation)
* Multiplication
/ Division (always returns Double)
\ Integer division (returns Long)
^ Exponentiation
MOD Modulo
Comparison Operators:
= Equal
<> Not equal
< Less than
> Greater than
<= Less than or equal
>= Greater than or equal
Logical Operators:

164
AND Bitwise/logical AND
OR Bitwise/logical OR
XOR Bitwise/logical XOR
NOT Bitwise/logical NOT (unary)
Punctuation:
( Left parenthesis
) Right parenthesis
, Comma (separator)
; Semicolon (print separator, no space)
: Colon (statement separator)
# Hash (file number marker)

8.4.7 2.7 Token Classification

The lexer produces the following token types:
1. Keywords: Reserved words like PRINT, IF, FOR
2. Identifiers: Variable and procedure names
3. Literals: Integer, float, and string constants
4. Operators: Arithmetic, comparison, and logical operators
5. Punctuation: Parentheses, commas, semicolons, etc.
6. Special: Line numbers, newlines, end-of-file

8.5 3. Statements
This section documents all statement types supported by xbasic64, including their syntax and
semantics.

8.5.1 3.1 Assignment Statement

Syntax:
[LET] variable = expression
[LET] array(index [, index...]) = expression
Semantics: Assigns the value of an expression to a variable or array element. The LET keyword
is optional and typically omitted in modern usage.
Examples:
X = 42
LET Y = X + 10
Name$ = "Alice"
A(5) = 100
Matrix(2, 3) = 42
Type Coercion: If the variable and expression have different types, automatic type promotion
occurs following the hierarchy: Integer → Long → Single → Double.

165
8.5.2 3.2 PRINT Statement
Syntax:
PRINT [#filenumber,] [item [separator item]...] [separator]
Separators: - ; (semicolon) - No space between items - , (comma) - Tab to next print zone
Semantics: Outputs values to the console or a file. A trailing semicolon suppresses the newline.
Examples:
PRINT "Hello, World!"
PRINT X; Y; Z ' No spaces
PRINT A, B, C ' Tab-separated
PRINT "Value: "; X ' Mixed
PRINT "Enter value: "; ' No newline
PRINT ' Blank line
PRINT #1, "File output" ' Write to file #1

8.5.3 3.3 INPUT Statement

Syntax:
INPUT [#filenumber,] [prompt {; | ,}] variable [, variable...]
Semantics: Reads user input from console or file. With a prompt, displays the prompt string.
Multiple variables can be read, separated by commas in the input.
Examples:
INPUT X
INPUT "Enter your name: ", Name$
INPUT "X, Y: ", X, Y
INPUT #1, A, B, C ' Read from file #1
Behavior: - Without prompt: Displays ? as default prompt - With prompt and ;: Displays
prompt with ? appended - With prompt and ,: Displays prompt without ?

8.5.4 3.4 LINE INPUT Statement

Syntax:
LINE INPUT [#filenumber,] [prompt {; | ,}] variable
Semantics: Reads an entire line of input as a string, without parsing. Unlike INPUT, commas and
quotes in the input are treated as literal characters.
Examples:
LINE INPUT Text$
LINE INPUT "Enter text: ", UserInput$
LINE INPUT #1, FileLine$

166
8.5.5 3.5 IF Statement
Single-Line Syntax:
IF condition THEN statement [ELSE statement]
Block Syntax:
IF condition THEN
statements...
[ELSEIF condition THEN
statements...]
[ELSE
statements...]
END IF
Semantics: Conditional execution. The condition is evaluated; if non-zero (true), the THEN
branch executes; otherwise, the ELSE branch (if present) executes.
Examples:
' Single-line
IF X > 0 THEN PRINT "Positive"
IF X > 0 THEN Y = 1 ELSE Y = 0

' Block form

IF Score >= 90 THEN
PRINT "Grade: A"
ELSEIF Score >= 80 THEN
PRINT "Grade: B"
ELSEIF Score >= 70 THEN
PRINT "Grade: C"
ELSE
PRINT "Grade: F"
END IF

8.5.6 3.6 FOR…NEXT Loop

Syntax:
FOR variable = start TO end [STEP increment]
statements...
NEXT [variable]
Semantics: Counted loop. The loop variable is initialized to start, and the loop body executes
repeatedly, incrementing by increment (default 1) until the variable exceeds end.
Examples:
FOR I = 1 TO 10
PRINT I
NEXT I

167
FOR J = 10 TO 1 STEP -1
PRINT J
NEXT

FOR K = 0 TO 1 STEP 0.1

PRINT K
NEXT K
Behavior: - STEP can be positive or negative - STEP can be fractional - Loop variable name
after NEXT is optional - Loop executes at least once if start � end (positive step) or start � end
(negative step)

8.5.7 3.7 WHILE…WEND Loop

Syntax:
WHILE condition
statements...
WEND
Semantics: Pre-test loop. The condition is evaluated before each iteration. If true (non-zero), the
loop body executes. If false (zero), the loop terminates.
Examples:
WHILE X < 100
X = X * 2
WEND

WHILE NOT EOF(1)

LINE INPUT #1, Line$
PRINT Line$
WEND

8.5.8 3.8 DO…LOOP Statement

Syntax:
DO [WHILE | UNTIL condition]
statements...
LOOP [WHILE | UNTIL condition]
Semantics: Flexible loop with optional pre-test or post-test condition. Four variants: 1.
DO...LOOP - Infinite loop (use EXIT or GOTO to break) 2. DO WHILE...LOOP - Pre-test, continues
while condition is true 3. DO UNTIL...LOOP - Pre-test, continues until condition is true 4.
DO...LOOP WHILE - Post-test, continues while condition is true 5. DO...LOOP UNTIL - Post-test,
continues until condition is true
Examples:
' Infinite loop
DO
INPUT X

168
 IF X = 0 THEN GOTO ExitLoop
LOOP

' Pre-test WHILE

DO WHILE X < 100
X = X + 1
LOOP

' Pre-test UNTIL

DO UNTIL X >= 100
X = X + 1
LOOP

' Post-test WHILE

DO
X = X + 1
LOOP WHILE X < 100

' Post-test UNTIL

DO
X = X + 1
LOOP UNTIL X >= 100

8.5.9 3.9 SELECT CASE Statement

Syntax:
SELECT CASE expression
CASE value [, value...]
statements...
[CASE value TO value
statements...]
[CASE IS relop value
statements...]
[CASE ELSE
statements...]
END SELECT
Semantics: Multi-way branch based on the value of an expression. Each CASE clause specifies
one or more values or ranges. The first matching case executes.
Examples:
SELECT CASE Grade
CASE 90 TO 100
PRINT "A"
CASE 80 TO 89
PRINT "B"
CASE 70 TO 79
PRINT "C"

169
 CASE ELSE
PRINT "F"
END SELECT

SELECT CASE Choice$

CASE "yes", "y", "Y"
PRINT "Confirmed"
CASE "no", "n", "N"
PRINT "Cancelled"
CASE ELSE
PRINT "Invalid choice"
END SELECT
Case Expressions: - Single value: CASE 1 - Multiple values: CASE 1, 2, 3 - Range: CASE 1 TO
10 - Relational: CASE IS > 100 - Default: CASE ELSE

8.5.10 3.10 GOTO Statement

Syntax:
GOTO line-number | label
Semantics: Unconditional jump to the specified line number or label.
Examples:
10 PRINT "Loop"
20 GOTO 10

GOTO StartLoop
GOTO 1000
Warning: Excessive use of GOTO can lead to “spaghetti code.” Prefer structured control flow
(FOR, WHILE, DO) when possible.

8.5.11 3.11 GOSUB and RETURN Statements

Syntax:
GOSUB line-number | label
RETURN
Semantics: GOSUB calls a subroutine at the specified line, saving the return address. RETURN
returns to the statement following the most recent GOSUB.
Examples:
GOSUB 1000
PRINT "Back from subroutine"
END

1000 REM Subroutine

170
1000 PRINT "In subroutine"
1000 RETURN
Note: For modern code, prefer SUB and FUNCTION procedures over GOSUB.

8.5.12 3.12 ON…GOTO Statement

Syntax:
ON expression GOTO line-number [, line-number...]
Semantics: Computed jump. Evaluates the expression (must be integer). If the value is 1, jumps
to the first target; if 2, to the second target, etc. If the value is out of range, execution continues
with the next statement.
Examples:
ON Choice GOTO 100, 200, 300
' If Choice=1, goto 100; if Choice=2, goto 200; if Choice=3, goto 300

ON MenuOption GOTO MainMenu, Settings, Help, Quit

8.5.13 3.13 DIM Statement

Syntax:
DIM array(size [, size...]) [, array(size [, size...])...]
Semantics: Declares arrays with specified dimensions. Arrays can have up to 3 dimensions. Array
indices start at 0 by default.
Examples:
DIM Scores(10) ' 11 elements: 0 to 10
DIM Matrix(5, 5) ' 6x6 array: 0-5 in each dimension
DIM Cube(3, 3, 3) ' 4x4x4 array
DIM Names$(100) ' String array
DIM A(10), B(20), C$(50) ' Multiple arrays
Array Indexing: - DIM A(10) creates 11 elements: A(0) through A(10) - Multi-dimensional:
Matrix(row, col) - Type suffix applies to all elements: Names$(i) is a string

8.5.14 3.14 SUB Statement

Syntax:
SUB name [(parameter [, parameter...])]
statements...
END SUB
Semantics: Defines a subroutine (procedure that doesn’t return a value). Parameters are passed
by value.
Examples:

171
SUB PrintGreeting(Name$)
PRINT "Hello, "; Name$; "!"
END SUB

SUB Swap(A, B)
Temp = A
A = B
B = Temp
END SUB

' Calling subroutines

PrintGreeting "World"
PrintGreeting("Alice")
Swap X, Y
Calling Convention: - Parentheses are optional when calling - Parameters are passed by value
(changes don’t affect caller) - Local variables are scoped to the subroutine

8.5.15 3.15 FUNCTION Statement

Syntax:
FUNCTION name [(parameter [, parameter...])]
statements...
name = return-value
END FUNCTION
Semantics: Defines a function (procedure that returns a value). The return value is assigned to
the function name within the function body.
Examples:
FUNCTION Square(X)
Square = X * X
END FUNCTION

FUNCTION Factorial(N)
IF N <= 1 THEN
Factorial = 1
ELSE
Factorial = N * Factorial(N - 1)
END IF
END FUNCTION

' Using functions

PRINT Square(5)
Result = Factorial(10)
Return Value: - Assign to function name to set return value - Type suffix on function name
determines return type - Supports recursion

172
8.5.16 3.16 Call Statement
Syntax:
name [([argument [, argument...]])]
name argument [, argument...]
Semantics: Calls a user-defined subroutine or function. Parentheses are optional for subroutines.
Examples:
MySub ' No arguments
MySub X, Y ' With arguments
MySub(X, Y) ' With parentheses
Result = MyFunc(A, B) ' Function call

8.5.17 3.17 DATA, READ, and RESTORE Statements

DATA Syntax:
DATA literal [, literal...]
READ Syntax:
READ variable [, variable...]
RESTORE Syntax:
RESTORE [line-number | label]
Semantics: - DATA defines inline data values - READ reads values from DATA statements into
variables - RESTORE resets the data pointer to the beginning or a specific line
Examples:
DATA 10, 20, 30, "Hello", "World"
DATA 3.14, 2.71, 1.41

READ A, B, C
READ X$, Y$
PRINT A, B, C
PRINT X$, Y$

RESTORE ' Reset to beginning

READ A ' Reads 10 again

100 DATA 100, 200, 300

RESTORE 100 ' Reset to line 100
READ Value
Behavior: - DATA statements can appear anywhere in the program - READ consumes data
sequentially across all DATA statements - Type coercion occurs if variable and data types differ -
Reading past the end of data causes a runtime error

173
8.5.18 3.18 File I/O Statements
[Link] 3.18.1 OPEN Statement
Syntax:
OPEN filename$ FOR mode AS #filenumber
Modes: - INPUT - Open for reading - OUTPUT - Open for writing (truncates existing file) - APPEND
- Open for writing (appends to existing file)
Examples:
OPEN "[Link]" FOR INPUT AS #1
OPEN "[Link]" FOR OUTPUT AS #2
OPEN "[Link]" FOR APPEND AS #3
File Numbers: Range from 1 to 255. Each open file must have a unique number.

[Link] 3.18.2 CLOSE Statement

Syntax:
CLOSE #filenumber
CLOSE
Semantics: Closes an open file. Without a file number, closes all open files.
Examples:
CLOSE #1
CLOSE #2
CLOSE ' Close all files

[Link] 3.18.3 File PRINT Statement

Syntax:
PRINT #filenumber, [item [separator item]...] [separator]
Semantics: Writes data to a file. Syntax is identical to console PRINT.
Examples:
PRINT #1, "Hello, File!"
PRINT #1, X; Y; Z
PRINT #1, A, B, C

[Link] 3.18.4 File INPUT Statement

Syntax:
INPUT #filenumber, variable [, variable...]
LINE INPUT #filenumber, variable
Semantics: Reads data from a file. Syntax is identical to console INPUT.
Examples:

174
INPUT #1, X, Y, Z
LINE INPUT #1, TextLine$
Complete File I/O Example:
' Write data
OPEN "[Link]" FOR OUTPUT AS #1
PRINT #1, "John"
PRINT #1, 25
PRINT #1, 50000.00
CLOSE #1

' Read data

OPEN "[Link]" FOR INPUT AS #1
INPUT #1, Name$
INPUT #1, Age%
INPUT #1, Salary#
CLOSE #1

PRINT Name$; " is "; Age%; " years old"

8.5.19 3.19 CLS Statement

Syntax:
CLS
Semantics: Clears the screen (console).
Example:
CLS
PRINT "Screen cleared"

8.5.20 3.20 END Statement

Syntax:
END
Semantics: Terminates program execution normally. Closes all open files and returns to the
operating system.
Example:
PRINT "Program complete"
END

8.5.21 3.21 STOP Statement

Syntax:
STOP

175
Semantics: Terminates program execution. Historically used for debugging breakpoints. In xba-
sic64, behaves identically to END.
Example:
IF Error THEN STOP

8.6 4. Expressions
This section describes the expression syntax, operators, precedence, and associativity rules in xba-
sic64.

8.6.1 4.1 Expression Types

Expressions in xbasic64 can be: - Arithmetic: Numeric calculations - Relational: Comparisons
returning true (-1) or false (0) - Logical: Bitwise/logical operations on integers - String: String
concatenation

8.6.2 4.2 Data Types

xbasic64 supports five data types:

Type Suffix Size Range/Description

INTEGER % 16-bit -32,768 to 32,767
LONG & 32-bit -2,147,483,648 to 2,147,483,647
SINGLE ! 32-bit ~7 digits precision (IEEE 754)
DOUBLE # 64-bit ~15 digits precision (IEEE 754)
STRING $ Dynamic Heap-allocated character sequences

Default Type: Variables without a type suffix default to DOUBLE (#).

8.6.3 4.3 Type Coercion

When operands of different numeric types are combined, automatic type promotion occurs:
INTEGER → LONG → SINGLE → DOUBLE
The result takes the wider (more precise) type.
Examples:
X% = 10 ' Integer
Y# = 3.14 ' Double
Z = X% + Y# ' Z is Double (10.0 + 3.14 = 13.14)

A% = 5 ' Integer
B& = 1000000 ' Long
C = A% + B& ' C is Long

176
String/Numeric Mixing: Not allowed. Use VAL() to convert string to number, STR$() to
convert number to string.

8.6.4 4.4 Arithmetic Operators

Operator Description Precedence Associativity Example

^ Exponentiation 7 (highest) Right 2 ^ 3 =8
- Unary negation 6 Right -X
* Multiplication 5 Left 3 * 4 = 12
/ Division (→ Double) 5 Left 7 / 2 = 3.5
\ Integer division (→ Long) 5 Left 7 \ 2 =3
MOD Modulo 5 Left 7 MOD 3=1
+ Addition 4 Left 2 + 3 =5
- Subtraction 4 Left 5 - 2 =3

Division Semantics: - / always produces a Double result: 7 / 2 = 3.5 - \ produces a Long

result: 7 \ 2 = 3 - MOD returns the remainder: 7 MOD 3 = 1
Exponentiation: - Right-associative: 2 ^ 3 ^ 2 = 2 ^ (3 ^ 2) = 2 ^ 9 = 512 - Can use
fractional exponents: 4 ^ 0.5 = 2.0 (square root)
Examples:
PRINT 2 + 3 * 4 ' 14 (not 20, due to precedence)
PRINT (2 + 3) * 4 ' 20 (parentheses override)
PRINT 2 ^ 3 ^ 2 ' 512 (right-associative)
PRINT 10 / 3 ' 3.333... (Double)
PRINT 10 \ 3 ' 3 (Long)
PRINT 10 MOD 3 ' 1
PRINT -5 ^ 2 ' -25 (negation after exponentiation)
PRINT (-5) ^ 2 ' 25 (parentheses change order)

8.6.5 4.5 Comparison Operators

Operator Description Precedence Example Result

= Equal 3 5 = 5 -1
<> Not equal 3 5 <> 3 -1
< Less than 3 3 < 5 -1
> Greater than 3 5 > 3 -1
<= Less than or equal 3 3 <= 5 -1
>= Greater than or equal 3 5 >= 5 -1

Boolean Values: - True: -1 (all bits set: 0xFFFFFFFF for Long, 0xFFFF for Integer) - False:
0
This matches GW-BASIC/QuickBASIC semantics and allows bitwise operations on boolean results.
Examples:

177
PRINT 5 > 3 ' -1 (true)
PRINT 5 < 3 ' 0 (false)
PRINT 5 = 5 ' -1 (true)
PRINT 5 <> 5 ' 0 (false)

IF X > 0 THEN PRINT "Positive"

IF A = B THEN PRINT "Equal"

' String comparison (lexicographic)

PRINT "ABC" < "XYZ" ' -1 (true)
PRINT "apple" = "APPLE" ' 0 (false, case-sensitive for strings)

8.6.6 4.6 Logical Operators

Operator Description Precedence Associativity Example

NOT Bitwise/logical NOT 2 Right NOT X
AND Bitwise/logical AND 1 Left X AND Y
OR Bitwise/logical OR 0 (lowest) Left X OR Y
XOR Bitwise/logical XOR 0 Left X XOR Y

Dual Purpose: These operators work as both logical operators (for boolean expressions) and
bitwise operators (for integer manipulation).
Logical Examples:
IF X > 0 AND Y > 0 THEN PRINT "Both positive"
IF A = 1 OR B = 1 THEN PRINT "At least one is 1"
IF NOT (X = 0) THEN PRINT "X is not zero"
IF (A > 0) XOR (B > 0) THEN PRINT "Exactly one is positive"
Bitwise Examples:
Flags% = &H0F ' Binary: 00001111
Mask% = &H03 ' Binary: 00000011

PRINT Flags% AND Mask% ' 3 (binary: 00000011)

PRINT Flags% OR Mask% ' 15 (binary: 00001111)
PRINT Flags% XOR Mask% ' 12 (binary: 00001100)
PRINT NOT Mask% ' -4 (binary: 11111100, two's complement)

' Set bit 0

Flags% = Flags% OR &H01

' Clear bit 1

Flags% = Flags% AND NOT &H02

' Toggle bit 2

Flags% = Flags% XOR &H04

178
8.6.7 4.7 String Concatenation
Operator: +
Syntax:
string1 + string2
Semantics: Concatenates two strings into a new string.
Examples:
First$ = "Hello"
Last$ = "World"
Full$ = First$ + " " + Last$ ' "Hello World"

PRINT "Value: " + STR$(42) ' "Value: 42"

PRINT "2" + "2" ' "22" (not 4)
Note: The + operator is overloaded: it performs addition for numbers and concatenation for strings.
Mixing types requires explicit conversion.

8.6.8 4.8 Operator Precedence Table

From highest to lowest precedence:

Level Operators Associativity Description

7 ^ Right Exponentiation
6 - (unary) Right Negation
5 *, /, \, MOD Left Multiplicative
4 +, - Left Additive
3 =, <>, <, >, <=, >= Left Relational
2 NOT Right Logical NOT
1 AND Left Logical AND
0 OR, XOR Left Logical OR/XOR

Associativity: - Left: Operators at the same level evaluate left-to-right: a - b - c = (a - b)

- c - Right: Operators at the same level evaluate right-to-left: a ^ b ^ c = a ^ (b ^ c)
Parentheses: Use parentheses ( ) to override precedence:
PRINT 2 + 3 * 4 ' 14
PRINT (2 + 3) * 4 ' 20

PRINT 10 / 2 + 3 ' 8.0

PRINT 10 / (2 + 3) ' 2.0

8.6.9 4.9 Built-in Functions

xbasic64 provides built-in functions for common operations. Functions are called with parentheses.

179
[Link] 4.9.1 Mathematical Functions

Function Description Example

ABS(x) Absolute value ABS(-5) = 5
INT(x) Floor (largest integer � x) INT(3.7) = 3
FIX(x) Truncate toward zero FIX(-3.7) = -3
SGN(x) Sign: -1, 0, or 1 SGN(-5) = -1
SQR(x) Square root SQR(16) = 4
SIN(x) Sine (radians) SIN(0) = 0
COS(x) Cosine (radians) COS(0) = 1
TAN(x) Tangent (radians) TAN(0) = 0
ATN(x) Arctangent (returns radians) ATN(1) = 0.785...
EXP(x) e raised to power x EXP(1) = 2.718...
LOG(x) Natural logarithm LOG(2.718) � 1
RND Random number 0 � r < 1 RND

RND Behavior:
X = RND ' Next random number
X = RND(0) ' Same as RND
X = RND(-1) ' Reseed with system time

[Link] 4.9.2 String Functions

Function Description Example

LEN(s$) Length of string LEN("Hello") = 5
LEFT$(s$, n) Leftmost n characters LEFT$("Hello", 2) =
"He"
RIGHT$(s$, n) Rightmost n characters RIGHT$("Hello", 2) =
"lo"
MID$(s$, start, Substring (1-based index) MID$("Hello", 2, 3) =
len) "ell"
MID$(s$, start) Substring from start to end MID$("Hello", 3) =
"llo"
INSTR(s$, find$) Position of find$ in s$ (0 if not found) INSTR("Hello", "ll") =
3
INSTR(start, s$, Search starting at position INSTR(2, "Hello", "l")
find$) =3
ASC(s$) ASCII code of first character ASC("A") = 65
CHR$(n) Character from ASCII code CHR$(65) = "A"
VAL(s$) Convert string to number VAL("123") = 123
STR$(x) Convert number to string STR$(123) = "123"

String Indexing: String functions use 1-based indexing (first character is at position 1).
Examples:

180
S$ = "Hello, World!"
PRINT LEN(S$) ' 13
PRINT LEFT$(S$, 5) ' "Hello"
PRINT RIGHT$(S$, 6) ' "World!"
PRINT MID$(S$, 8, 5) ' "World"
PRINT INSTR(S$, "World") ' 8

' Type conversion

X = VAL("123.45") ' 123.45
S$ = STR$(42) ' "42"

[Link] 4.9.3 Type Conversion Functions

Function Description Example

CINT(x) Convert to Integer (with rounding) CINT(3.7) = 4
CLNG(x) Convert to Long (with rounding) CLNG(3.7) = 4
CSNG(x) Convert to Single CSNG(3) = 3.0!
CDBL(x) Convert to Double CDBL(3) = 3.0#

Rounding: CINT and CLNG use “banker’s rounding” (round to nearest even).

[Link] 4.9.4 Other Functions

Function Description Example

TIMER Seconds since midnight (Double) TIMER

Example:
Start# = TIMER
' ... do work ...
Elapsed# = TIMER - Start#
PRINT "Time: "; Elapsed#; " seconds"

8.6.10 4.10 Expression Examples

Complex Arithmetic:
' Quadratic formula: x = (-b ± √(b²-4ac)) / 2a
A = 1
B = -5
C = 6
Discriminant = B ^ 2 - 4 * A * C
X1 = (-B + SQR(Discriminant)) / (2 * A)
X2 = (-B - SQR(Discriminant)) / (2 * A)
Boolean Logic:

181
' Check if X is in range [10, 20]
InRange = (X >= 10) AND (X <= 20)

' Check if year is leap year

LeapYear = ((Year MOD 4 = 0) AND (Year MOD 100 <> 0)) OR (Year MOD 400 = 0)
String Manipulation:
' Extract filename from path
Path$ = "C:\DOCS\[Link]"
Pos = INSTR(Path$, "\")
WHILE Pos > 0
Path$ = MID$(Path$, Pos + 1)
Pos = INSTR(Path$, "\")
WEND
PRINT "Filename: "; Path$

8.7 5. Language Examples

This section provides comprehensive examples demonstrating every major language feature in xba-
sic64.

8.7.1 5.1 Variables and Data Types

REM Demonstrate all five data types

' Integer (16-bit)

Count% = 100
MaxValue% = 32767

' Long (32-bit)

Population& = 1000000
BigNumber& = 2147483647

' Single (32-bit float)

Temperature! = 98.6
Pi! = 3.14159

' Double (64-bit float) - DEFAULT

PreciseValue# = 3.14159265358979
Distance = 93000000.0 ' Unsuffixed = Double

' String
Name$ = "Alice"
Message$ = "Hello, World!"

PRINT "Integer: "; Count%

182
PRINT "Long: "; Population&
PRINT "Single: "; Temperature!
PRINT "Double: "; PreciseValue#
PRINT "String: "; Name$

8.7.2 5.2 Arithmetic Operations

REM Demonstrate arithmetic operators

A = 10
B = 3

PRINT "Addition: "; A + B ' 13

PRINT "Subtraction: "; A - B ' 7
PRINT "Multiplication: "; A * B ' 30
PRINT "Division: "; A / B ' 3.333...
PRINT "Integer Division: "; A \ B ' 3
PRINT "Modulo: "; A MOD B ' 1
PRINT "Exponentiation: "; A ^ B ' 1000

' Unary negation

X = 5
PRINT "Negation: "; -X ' -5

' Precedence
PRINT "2 + 3 * 4 = "; 2 + 3 * 4 ' 14
PRINT "(2 + 3) * 4 = "; (2 + 3) * 4 ' 20

8.7.3 5.3 Comparison and Logical Operations

REM Demonstrate comparison and logical operators

X = 10
Y = 20

' Comparisons (return -1 for true, 0 for false)

PRINT "X = Y: "; X = Y ' 0 (false)
PRINT "X <> Y: "; X <> Y ' -1 (true)
PRINT "X < Y: "; X < Y ' -1 (true)
PRINT "X > Y: "; X > Y ' 0 (false)
PRINT "X <= Y: "; X <= Y ' -1 (true)
PRINT "X >= Y: "; X >= Y ' 0 (false)

' Logical operators

A = 5
B = 10
PRINT "A > 0 AND B > 0: "; (A > 0) AND (B > 0) ' -1 (true)
PRINT "A < 0 OR B > 0: "; (A < 0) OR (B > 0) ' -1 (true)

183
PRINT "NOT (A = 0): "; NOT (A = 0) ' -1 (true)

' Bitwise operations

Flags% = &H0F ' Binary: 00001111
Mask% = &H03 ' Binary: 00000011
PRINT "Flags AND Mask: "; Flags% AND Mask% ' 3
PRINT "Flags OR Mask: "; Flags% OR Mask% ' 15
PRINT "Flags XOR Mask: "; Flags% XOR Mask% ' 12

8.7.4 5.4 String Operations

REM Demonstrate string operations

First$ = "Hello"
Last$ = "World"

' Concatenation
Full$ = First$ + " " + Last$
PRINT Full$ ' "Hello World"

' String functions

S$ = "BASIC Programming"
PRINT "Length: "; LEN(S$) ' 18
PRINT "Left 5: "; LEFT$(S$, 5) ' "BASIC"
PRINT "Right 11: "; RIGHT$(S$, 11) ' "Programming"
PRINT "Mid 7,4: "; MID$(S$, 7, 4) ' "Prog"
PRINT "Position of 'gram': "; INSTR(S$, "gram") ' 12

' Character functions

PRINT "ASCII of 'A': "; ASC("A") ' 65
PRINT "Char 65: "; CHR$(65) ' "A"

' Type conversion

NumStr$ = "123.45"
Num = VAL(NumStr$)
PRINT "String to number: "; Num ' 123.45

Value = 42
Str$ = STR$(Value)
PRINT "Number to string: "; Str$ ' "42"

8.7.5 5.5 Arrays

REM Demonstrate array usage

' Declare arrays

DIM Numbers(10) ' 11 elements: 0-10
DIM Matrix(3, 3) ' 4x4 matrix

184
DIM Names$(5) ' String array

' Populate 1D array

FOR I = 0 TO 10
Numbers(I) = I * I
NEXT I

' Print 1D array

PRINT "Squares:"
FOR I = 0 TO 10
PRINT Numbers(I);
NEXT I
PRINT

' Populate 2D array (identity matrix)

FOR Row = 0 TO 3
FOR Col = 0 TO 3
IF Row = Col THEN
Matrix(Row, Col) = 1
ELSE
Matrix(Row, Col) = 0
END IF
NEXT Col
NEXT Row

' Print 2D array

PRINT "Identity Matrix:"
FOR Row = 0 TO 3
FOR Col = 0 TO 3
PRINT Matrix(Row, Col);
NEXT Col
PRINT
NEXT Row

' String array

Names$(0) = "Alice"
Names$(1) = "Bob"
Names$(2) = "Charlie"

FOR I = 0 TO 2
PRINT Names$(I)
NEXT I

8.7.6 5.6 Control Flow - IF Statement

REM Demonstrate IF statement variations

' Single-line IF

185
X = 10
IF X > 0 THEN PRINT "Positive"

' Single-line IF...ELSE

IF X > 0 THEN PRINT "Positive" ELSE PRINT "Non-positive"

' Block IF
Score = 85
IF Score >= 90 THEN
PRINT "Grade: A"
PRINT "Excellent!"
ELSEIF Score >= 80 THEN
PRINT "Grade: B"
PRINT "Good job!"
ELSEIF Score >= 70 THEN
PRINT "Grade: C"
PRINT "Passing"
ELSE
PRINT "Grade: F"
PRINT "Need improvement"
END IF

' Nested IF
Age = 25
HasLicense = -1 ' True

IF Age >= 16 THEN

IF HasLicense THEN
PRINT "Can drive"
ELSE
PRINT "Need license"
END IF
ELSE
PRINT "Too young to drive"
END IF

8.7.7 5.7 Control Flow - Loops

REM Demonstrate all loop types

' FOR loop

PRINT "FOR loop (1 to 5):"
FOR I = 1 TO 5
PRINT I;
NEXT I
PRINT

' FOR loop with STEP

186
PRINT "FOR loop (10 to 1, step -2):"
FOR I = 10 TO 1 STEP -2
PRINT I;
NEXT I
PRINT

' WHILE loop

PRINT "WHILE loop:"
X = 1
WHILE X <= 5
PRINT X;
X = X + 1
WEND
PRINT

' DO...LOOP (infinite, with exit)

PRINT "DO...LOOP with exit:"
Count = 0
DO
Count = Count + 1
PRINT Count;
IF Count >= 5 THEN GOTO ExitLoop
LOOP
ExitLoop:
PRINT

' DO WHILE...LOOP (pre-test)

PRINT "DO WHILE...LOOP:"
X = 1
DO WHILE X <= 5
PRINT X;
X = X + 1
LOOP
PRINT

' DO...LOOP WHILE (post-test)

PRINT "DO...LOOP WHILE:"
X = 1
DO
PRINT X;
X = X + 1
LOOP WHILE X <= 5
PRINT

' DO UNTIL...LOOP (pre-test)

PRINT "DO UNTIL...LOOP:"
X = 1
DO UNTIL X > 5

187
 PRINT X;
X = X + 1
LOOP
PRINT

' DO...LOOP UNTIL (post-test)

PRINT "DO...LOOP UNTIL:"
X = 1
DO
PRINT X;
X = X + 1
LOOP UNTIL X > 5
PRINT

8.7.8 5.8 SELECT CASE Statement

REM Demonstrate SELECT CASE

INPUT "Enter a number (1-5): ", Choice

SELECT CASE Choice

CASE 1
PRINT "You chose ONE"
CASE 2
PRINT "You chose TWO"
CASE 3
PRINT "You chose THREE"
CASE 4, 5
PRINT "You chose FOUR or FIVE"
CASE ELSE
PRINT "Invalid choice"
END SELECT

' SELECT CASE with ranges

INPUT "Enter your age: ", Age

SELECT CASE Age

CASE 0 TO 12
PRINT "Child"
CASE 13 TO 19
PRINT "Teenager"
CASE 20 TO 64
PRINT "Adult"
CASE IS >= 65
PRINT "Senior"
CASE ELSE
PRINT "Invalid age"
END SELECT

188
' SELECT CASE with strings
INPUT "Continue (yes/no)? ", Answer$

SELECT CASE Answer$

CASE "yes", "y", "Y"
PRINT "Continuing..."
CASE "no", "n", "N"
PRINT "Stopping..."
CASE ELSE
PRINT "Invalid response"
END SELECT

8.7.9 5.9 Subroutines and Functions

REM Demonstrate SUB and FUNCTION

' Define a subroutine

SUB PrintBanner(Title$)
PRINT STRING$(40, "=")
PRINT Title$
PRINT STRING$(40, "=")
END SUB

' Define functions

FUNCTION Square(X)
Square = X * X
END FUNCTION

FUNCTION Factorial(N)
IF N <= 1 THEN
Factorial = 1
ELSE
Factorial = N * Factorial(N - 1)
END IF
END FUNCTION

FUNCTION Max(A, B)
IF A > B THEN
Max = A
ELSE
Max = B
END IF
END FUNCTION

' Use subroutine

PrintBanner "Math Examples"

189
' Use functions
PRINT "Square of 5: "; Square(5)
PRINT "Factorial of 5: "; Factorial(5)
PRINT "Max of 10 and 20: "; Max(10, 20)

' Function with type suffix

FUNCTION Add$(A$, B$)
Add$ = A$ + " " + B$
END FUNCTION

PRINT Add$("Hello", "World")

8.7.10 5.10 DATA, READ, and RESTORE

REM Demonstrate DATA/READ/RESTORE

' Define data

DATA 10, 20, 30, 40, 50
DATA "Alice", "Bob", "Charlie"
DATA 3.14, 2.71, 1.41

' Read numeric data

READ A, B, C, D, E
PRINT "Numbers: "; A; B; C; D; E

' Read string data

READ Name1$, Name2$, Name3$
PRINT "Names: "; Name1$; " "; Name2$; " "; Name3$

' Read more numeric data

READ Pi, E, Root2
PRINT "Constants: "; Pi; E; Root2

' Reset and read again

RESTORE
READ First
PRINT "First value again: "; First

' Restore to specific line

100 DATA 100, 200, 300
RESTORE 100
READ X, Y, Z
PRINT "From line 100: "; X; Y; Z

8.7.11 5.11 File I/O

REM Demonstrate file input/output

190
' Write to file
OPEN "[Link]" FOR OUTPUT AS #1
PRINT #1, "Line 1: Hello"
PRINT #1, "Line 2: World"
PRINT #1, 42
PRINT #1, 3.14159
CLOSE #1

PRINT "Data written to [Link]"

' Read from file

OPEN "[Link]" FOR INPUT AS #1
LINE INPUT #1, Line1$
LINE INPUT #1, Line2$
INPUT #1, Number%
INPUT #1, FloatNum#
CLOSE #1

PRINT "Data read from [Link]:"

PRINT Line1$
PRINT Line2$
PRINT "Number: "; Number%
PRINT "Float: "; FloatNum#

' Append to file

OPEN "[Link]" FOR APPEND AS #1
PRINT #1, "Line 3: Appended"
CLOSE #1

PRINT "Data appended to [Link]"

8.7.12 5.12 GOTO and GOSUB

REM Demonstrate GOTO and GOSUB

' GOTO example

PRINT "Start"
GOTO SkipThis
PRINT "This is skipped"
SkipThis:
PRINT "After GOTO"

' GOSUB example

PRINT "Before subroutine"
GOSUB 1000
PRINT "After subroutine"
END

191
1000 REM Subroutine
1000 PRINT "Inside subroutine"
1000 RETURN

' ON...GOTO example

INPUT "Enter choice (1-3): ", Choice
ON Choice GOTO 100, 200, 300
PRINT "Invalid choice"
GOTO 400

100 PRINT "Option 1"

100 GOTO 400

200 PRINT "Option 2"

200 GOTO 400

300 PRINT "Option 3"

400 PRINT "Done"

8.7.13 5.13 Complete Program Example: Guessing Game

REM Number Guessing Game
REM The computer picks a random number and you guess it

CLS
PRINT "==================================="
PRINT " NUMBER GUESSING GAME"
PRINT "==================================="
PRINT

' Initialize random number generator

Dummy = RND(-1)

' Pick random number between 1 and 100

Target = INT(RND * 100) + 1
Guesses = 0
MaxGuesses = 10

PRINT "I'm thinking of a number between 1 and 100."

PRINT "You have "; MaxGuesses; " guesses."
PRINT

' Game loop

DO WHILE Guesses < MaxGuesses
INPUT "Enter your guess: ", Guess
Guesses = Guesses + 1

192
 IF Guess = Target THEN
PRINT "Congratulations! You guessed it in "; Guesses; " tries!"
GOTO GameOver
ELSEIF Guess < Target THEN
PRINT "Too low! ";
ELSE
PRINT "Too high! ";
END IF

PRINT "Guesses remaining: "; MaxGuesses - Guesses

PRINT
LOOP

' Out of guesses

PRINT "Sorry, you're out of guesses."
PRINT "The number was "; Target

GameOver:
PRINT
INPUT "Play again (yes/no)? ", Answer$

SELECT CASE Answer$

CASE "yes", "y", "Y"
GOTO 10
CASE ELSE
PRINT "Thanks for playing!"
END SELECT

8.7.14 5.14 Complete Program Example: Fibonacci Sequence

REM Calculate and display Fibonacci sequence

CLS
PRINT "Fibonacci Sequence Calculator"
PRINT "=============================="
PRINT

INPUT "How many terms? ", N

IF N < 1 THEN
PRINT "Must be at least 1"
END
END IF

' Use function to calculate

FUNCTION Fib(N)
IF N <= 1 THEN
Fib = N

193
 ELSE
Fib = Fib(N - 1) + Fib(N - 2)
END IF
END FUNCTION

' Display sequence

PRINT "First "; N; " Fibonacci numbers:"
FOR I = 0 TO N - 1
PRINT Fib(I);
IF I < N - 1 THEN PRINT ", ";
NEXT I
PRINT

' Alternative: iterative approach (faster)

SUB FibIterative(N)
A& = 0
B& = 1

PRINT "Iterative: ";

FOR I = 0 TO N - 1
PRINT A&;
IF I < N - 1 THEN PRINT ", ";

Temp& = A& + B&

A& = B&
B& = Temp&
NEXT I
PRINT
END SUB

FibIterative N

8.7.15 5.15 Complete Program Example: Array Sorting

REM Bubble sort demonstration

CLS
PRINT "Array Sorting Example"
PRINT "====================="
PRINT

' Initialize array with random values

DIM A(9)
PRINT "Original array:"
FOR I = 0 TO 9
A(I) = INT(RND * 100)
PRINT A(I);
NEXT I

194
PRINT
PRINT

' Bubble sort

SUB BubbleSort(Arr(), Size)
FOR I = 0 TO Size - 1
FOR J = 0 TO Size - I - 1
IF Arr(J) > Arr(J + 1) THEN
' Swap
Temp = Arr(J)
Arr(J) = Arr(J + 1)
Arr(J + 1) = Temp
END IF
NEXT J
NEXT I
END SUB

' Sort the array

BubbleSort A(), 9

' Display sorted array

PRINT "Sorted array:"
FOR I = 0 TO 9
PRINT A(I);
NEXT I
PRINT

8.8 Summary
This language reference provides a complete specification of xbasic64, including:
1. Formal Grammar: EBNF notation for all language constructs
2. Lexical Structure: Character set, comments, identifiers, literals, and operators
3. Statements: Complete documentation of all 21 statement types
4. Expressions: Operators, precedence, associativity, and built-in functions
5. Examples: Comprehensive code examples for every language feature
For implementation details and compiler internals, see the other documentation files in this series.

Navigation: - Previous: [Link] - Runtime System - Next: [Link] - Hands-on

Exercises - Home: [Link] - Documentation Index

195