Game Scripting Mastery. Premier Press

Alex Varanese

Premier Press, a division of Course Technology

Publisher: Stacy L. Hiquet
Marketing Manager: Heather Hurley
Acquisitions Editor: Mitzi Koontz
Series Editor: André LaMothe
Project Editor: Estelle Manticas
Copy Editor: Kezia Endsley
Interior Layout: Bill Hartman
Cover Designer: Mike Tanamachi
Indexer: Kelly Talbot
Proofreader: Sara Gullion

Game Scripting Mastery

Acknowledgments
It all started as I was standing around with some friends of mine on the second day of the 2001
Xtreme Game Developer's Conference in Santa Clara, California, discussing the Premier Press
game development series. At the time, I'd been doing a lot of research on the subject of compiler
theory—specifically, how it could be applied to game scripting—and at the exact moment I mentioned
that a scripting book would be a good idea, André Lamothe just happened to walk by.
"Let's see what he thinks," I said, and pulled him aside. "Hey André, have you ever thought about
a book on game scripting for your series?" I expected something along the lines of "that's not a
bad idea", or "sure-- it's already in production." What I got was surprising, to say the least.
"Why don't you write it?"

That was literally what he said. Unless you're on some sort of weird version of Jeopardy! where the
rules of the game require you to phrase your answer in the form of a book deal, this is a pretty
startling response. I blinked, thought about it for about a nanosecond, and immediately said
okay. This is how I handle most important decisions, but the sheer magnitude of the events that
would be set into motion by this particular one could hardly have been predicted at the time.
Never question the existence of fate.

With the obligatory anecdote out of the way, there are a number of very important people I'd like
to thank for providing invaluable support during the production of this book. It'd be nothing
short of criminal if this list didn't start with Mitzi Foster, my acquisitions editor who demonstrated
what can only be described as superhuman patience during the turbulent submission and evolution
of the book's manuscript. Having to handle the eleventh-hour rewrites of entire chapters
(and large ones at that) after they've been submitted and processed is an editor's nightmare—
and only one of the many she put up with—but she managed to handle it in stride, with a consistently
friendly and supportive attitude.

Next up is my copy editor, Kezia Endsley; if you notice the thorough grammatical correctness of
even the comments in this book's code listings, you'll have her to thank. Granted, it'll only be a
matter of time before the latest version of Microsoft's compilers have a comment grammar checking
paperclip, dancing monkey, robot dog, or ethnically ambiguous baby, but her eye for detail is
safely appreciated for now.

Lastly, rounding out the Game Scripting Mastery pit crew is Estelle Manticas, my project editor
who really stepped up to the plate during the later parts of the project, somehow maintaining a
sense of humor while planet Earth crumbled around us. Few people have what it takes to manage
the workload of an entire book when the pressure's on, and she managed to make it look easy.
Of course, due to my relatively young age and penchant for burning through cash like NASA, I've
relied on others to provide a roof over my head. The honor here, not surprisingly, goes to my
parents. I'd like to thank my mom for spreading news of my book deal to every friend, relative,
teacher, and mailman our family has ever known, and my dad for deciding that the best time to
work so loudly on rebuilding the deck directly outside my room is somewhere around zero o'clock
in the morning. I also can't forget my sister, Katherine—her constant need for me to drive her to
work is the only thing that keeps me waking up at a decent hour. Thanks a lot, guys!
And last, and most certainly least, I suppose I should thank that Lamothe guy. Seriously though—I
may have toiled endlessly on the code and manuscript, but André is the real reason this book
happened (and was also its technical editor). I've gotta say thanks for letting my raid your fridge
on a regular basis, teaching me everything I know about electrical engineering, dumping so many
free books on me, answering my incessant and apparently endless questions, restraining yourself
from ending our more heated arguments with a golf club, and of course, extending such an
obscenely generous offer to begin with. It should be known that there's literally no one else in
the industry that goes out of their way to help people out this much, and I'm only one of many
who've benefited from it.

I'd also like to give a big thanks to John Romero, who took time out of his understandably
packed schedule to save the day and write the book's Foreword. If not for him, I probably
would've had to get my mom to do it.

Oh and by the way, just because I think they'll get a kick out of it, I'd like to close with some horrendously
geeky shout-outs: thanks to Ironblayde, xms and Protoman—three talented coders,
and the few people I actually talk to regularly online—for listening to my constant ranting, and
encouraging me to finish what I start (if for no other reason than the fact that I'll stop blabbering
about it). You guys suck. Seriously.

Now if you'll excuse me, I'm gonna wrap this up. I feel like I'm signing a yearbook.


About the Author
Alex Varanese has been obsessed with game development since the mid-1980's when, at age five,
he first laid eyes—with both fascination and a strange and unexplainable sense of familiarity—on
the 8-bit Nintendo Entertainment System. He's been an avid artist since birth as well, but didn't
really get going as a serious coder until later in life, at around age 15, with QBASIC. He got his
start as a professional programmer at age 18 as a Java programmer in the Silicon Valley area,
working on a number of upstart B2B projects on the J2EE platform before working for about a
year as both a semi-freelance and in-house graphic designer.

Feeling that life in the office was too restrictive, however, he's since shifted his focus back to game
development and the pursuit of future technology. He currently holds the position of head
designer and systems architect for eGameZone (http://www.egamezone.net), the successor venture
to André LaMothe's Xtreme Games LLC. He spends his free time programming, rendering, writing
about himself in the third person, yelling at popup ads, starring in an off-Broadway production
of Dude, Where's My Car? The Musical, and demonstrating a blatant disregard for the posted speed limit.
Alex Varanese can be reached at alex@amvbooks.com, and is always ready and willing to answer any
questions you may have about the book. Please, don't hesitate to ask!


Introduction

If you've been programming games for any reasonable amount of time, you've probably

learned that at the end of the day, the really hard part of the job has nothing to do with illumination

models, doppler shift, file formats, or frame rates, as the majority of game development

books on the shelves would have you believe. These days, it's more or less evident that everyone

knows everything. Gone are the days where game development gurus separated themselves from

the common folk with their in-depth understanding of VGA registers or their ability to write an 8-

bit mixer in 4K of code. Nowadays, impossibly fast hardware accelerators and monolithic APIs

that do everything short of opening your mail pretty much have the technical details covered.

No, what really make the creation of a phenomenal game difficult are the characters, the plot,

and the suspension of disbelief.

Until Microsoft releases "DirectStoryline"—which probably won't be long, considering the

amount of artificial intelligence driving DirectMusic—the true challenge will be immersing players

in settings and worlds that exert a genuine sense of atmosphere and organic life. The floor

should creak and groan when players walk across aging hardwood. The bowels of a ship should

be alive with scurrying rats and the echoey drip-drop sounds of leaky pipes. Characters should

converse and interact with both the player and one another in ways that suggest a substantial set

of gears is turning inside their heads. In a nutshell, a world without compellingly animated detail

and believable responsiveness won't be suitable for the games of today and tomorrow.

The problem, as the first chapter of this book will explain, is that the only solution to this problem

directly offered by languages like C and C++ is to clump the code for implementing a peripheral

character's quirky attitude together with code you use to multiply matrices and sort vertex

lists. In other words, you're forced to write all of your game—from the low-level details to the

high-level logic—in the same place. This is an illogical grouping and one that leads to all sorts of

hazards and inconveniences.

And let's not forget the modding community. Every day it seems that players expect more flexibility

and expansion capabilities from their games. Few PC titles last long on the shelves if a

community of rabid, photosensitive code junkies can't tear it open and rewire its guts. The problem

is, you can't just pop up an Open File dialog box and let the player chose a DLL or other

dynamically linked solution, because doing so opens you up to all sorts of security holes. What if

a malicious mod author decides that the penalty for taking a rocket blast to the gut is a freshly

reformatted hard drive? Because of this, despite their power and speed, DLLs aren't necessarily

the ideal solution.

This is where the book you're currently reading comes into play. As you'll soon find out, a solution

that allows you to both easily script and control your in-game entities and environments, as

well as give players the ability to write mods and extensions, can only really come in the form of a

custom-designed language whose programs can run within an embeddable execution environment

inside the game engine. This is scripting.

If that last paragraph seemed like a mouthful, don't worry. This book is like an elevator that truly

starts from the bottom floor, containing everything you need to step out onto the roof and enjoy

the view when you're finished. But as a mentally unstable associate of mine is often heard to say,

"The devil is in the details." It's not enough to simply know what scripting is all about; in order to

really make something happen, you need to know everything. From the upper echelons of the

compiler, all the way down to the darkest corners of the virtual machine, you need to know what

goes where, and most importantly, why. That's what this book aims to do. If you start at the beginning

and follow along with me until the end, you should pick up everything you need to genuinely

understand what's going on.

How This Book is Organized

With the dramatic proclamations out of the way, let's take a quick look at how this book is set up;

then we'll be ready to get started.

This book is organized into a number of sections:

• Part One: Scripting Fundamentals. The majority of this material won't do you much

good if you don't know what scripting is or why it's important. Like I said, you can follow

this book whether or not you've even heard of scripting. The introduction provides

enough background information to get you up to speed quick.

• Part Two: Command-Based Scripting. Developing a complete, high-level scripting system

for a procedural language is a complex task. A very complex task. So, we start off by setting

our sights a bit lower and implementing what I like to call a "command-based language."

As you'll see, command-based languages are dead simple to implement and

capable of performing rather interesting tasks.

• Part Three: Introduction to Procedural Scripting Languages. Part 3 is where things start

to heat up, as we get our feet wet with real world, high-level scripting. Also covered in

this section are complete tutorials on using the Lua, Python and Tcl languages, as well as

integrating their associated runtime environments with a host application.

• Part Four: Designing and Implementing a Low-Level Langauge. At the bottom of our

scripting system will lie an assembly language and corresponding machine code (or bytecode).

The design and implementation of this low-level environment will provide a vital

foundation for the later chapters.

• Part Five: Designing and Implementing a Virtual Machine. Scripts—even compiled

ones—don't matter much if you don't have a way to run them. This section of the book

covers the design and implementation of a feature-packed virtual machine that's ready to

be dropped into a game engine.

• Part Six: Compiling High-Level Code. The belly of the beast itself. Executing compiled

bytecode is one thing, but being able to compile and ultimately run a high-level, procedural

language of your own design is what real scripting is all about.

• Part Seven: Completing Your Training. Once you've earned your stripes, it's time to

direct that knowledge somewhere. This final section aims to clear up any questions you

may have in regards to furthering your study. You'll also see how the scripting system

designed throughout the course of the book was applied to a complete game.

So that's it! You've got a roadmap firmly planted in your brain, and an interest in scripting that's

hopefully piqued by now. It's time to roll our sleeves up and turn this mutha out.

Screenshot

Purchase Now !
Just with Paypal

Product details

Price
File Size	53,251 KB
Pages	1273 p
File Type	PDF format
ISBN	1-931841-57-8
Copyright	2003 by Premier Press

Contents at a Glance
Introduction
Part One
Scripting Fundamentals
Chapter 1 An Introduction to Scripting
Chapter 2 Applications of Scripting Systems
Part Two Command-Based Scripting
Chapter 3 Introduction to Command-Based Scripting
Chapter 4 Advanced Command-Based Scripting
Part Three
Introduction to Procedural Scripting Languages
Chapter 5 Introduction to Procedural Scripting Systems
Chapter 6 Integration: Using Existing Scripting Systems
Chapter 7 Designing a Procedural Scripting Language
Part Four
Designing and Implementing a Low-Level Language
Chapter 8 Assembly Language Primer
Chapter 9 Building the XASM Assembler
Part Five
Designing and Implementing a Virtual Machine
Chapter 10 Basic VM Design and Implementation
Chapter 11 Advanced VM Concepts and Issues
Part Six
Compiling High-Level Code
Chapter 12 Compiler Theory Overview
Chapter 13 Lexical Analysis
Chapter 14 Building the XtremeScript Compiler Framework
Chapter 15 Parsing and Semantic Analysis
Part Seven
Completing Your Training
Chapter 16 Applying the System to a Full Game
Chapter 17 Where to Go From Here
Appendix A
What’s on the CD?
INDEX


Table of Contents

Introduction..................................xliv

Part One Scripting Fundamentals...............1

Chapter 1 An Introduction to Scripting..........3

What Is Scripting? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Structured Game Content—A Simple Approach. . . . . . . . . . . . . 6

Improving the Method with Logical and Physical Separation . . 10

The Perils of Hardcoding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Storing Functionality in External Files . . . . . . . . . . . . . . . . . . . . 14

How Scripting Actually Works. . . . . . . . . . . . . . . . . . . . . . . . . . . 15

An Overview of Computer Programming . . . . . . . . . . . . . . . . . . . . . . . . . . 16

An Overview of Scripting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

The Fundamental Types of Scripting Systems . . . . . . . . . . . . . . 20

Procedural/Object-Oriented Language Systems . . . . . . . . . . . . . . . . . . . . . . 21

Command-Based Language Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Dynamically Linked Module Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Compiled versus Interpreted Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Existing Scripting Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Ruby . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Lua. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Chapter 2 Applications of Scripting Systems.......29

The General Purpose of Scripting . . . . . . . . . . . . . . . . . . . . . . . 30

Role Playing Games (RPGs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Complex, In-Depth Stories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Non-Player Characters (NPCs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Items and Weapons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Enemies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

First-Person Shooters (FPSs) . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Objects, Puzzles, and Switches (Obligatory Oh My!) . . . . . . . . . . . . . . . . . . 51

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

Enemy AI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

Part Two Command-Based Scripting ..........61

Chapter 3 Introduction to Command-Based Scripting.......................63

The Basics of Command-Based Scripting. . . . . . . . . . . . . . . . . . 64

High-Level Engine Control. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Master of Your Domain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Actually Getting Something Done . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Command-Based Scripting Overview. . . . . . . . . . . . . . . . . . . . . 69

Engine Functionality Assessment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

Loading and Executing Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Looping Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

Implementing a Command-Based Language . . . . . . . . . . . . . . . 74

Designing the Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

Writing the Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Basic Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Execution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

Command and Parameter Extraction. . . . . . . . . . . . . . . . . . . . . . . . . . . 81

The Command Handlers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Scripting a Game Intro Sequence. . . . . . . . . . . . . . . . . . . . . . . . 90

The Language. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

The Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

The Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

Scripting an RPG Character’s Behavior . . . . . . . . . . . . . . . . . . . 95

The Language. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

Improving the Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Managing a Game Character . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

The Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

The Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

The Demo’s Main Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

Concurrent Script Execution . . . . . . . . . . . . . . . . . . . . . . . . . . 109

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Chapter 4 Advanced Command-Based Scripting.....113

New Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Boolean Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Floating-Point Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

General-Purpose Symbolic Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

An Internal Constant List. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

A Two-Pass Approach. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

Loading Before Executing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

Simple Iterative and Conditional Logic . . . . . . . . . . . . . . . . . . 125

Conditional Logic and Game Flags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Grouping Code with Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

The Block List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

Iterative Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

Nesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

Event-Based Scripting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

Compiling Scripts to a Binary Format . . . . . . . . . . . . . . . . . . . 137

Increased Execution Speed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

Detecting Compile-Time Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

Malicious Script Hacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

How a CBL Compiler Works. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

Executing Compiled Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

Compile-Time Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

Parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

Basic Script Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

File-Inclusion Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

Part Three Introduction to Procedural 

Scripting Languages ..153

Chapter 5 Introduction to Procedural Scripting Systems ..............155

Overall Scripting Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 156

High-Level Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

Low-Level Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

The Virtual Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

A Deeper Look at XtremeScript . . . . . . . . . . . . . . . . . . . . . . . 161

High-Level Code/Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

Lexical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

Parsing/Syntactic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

Intermediate Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

Assembly Language Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

The Symbol Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

The Front End versus the Back End . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

Low-Level Code/Assembly. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

The Assembler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

The Disassembler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

The Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

The Virtual Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

The XtremeScript System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

High-Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

Low-Level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

Runtime. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

Chapter 6 Integration: Using Existing Scripting Systems ................173

Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

Implementation of Scripting Systems. . . . . . . . . . . . . . . . . . . . 179

The Bouncing Head Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

Lua (and Basic Scripting Concepts) . . . . . . . . . . . . . . . . . . . . . 185

The Lua System at a Glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

The Lua Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

The luac Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

The lua Interactive Interpreter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

The Lua Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

Tables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

Advanced String Features. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

Conditional Logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

Iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

Integrating Lua with C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

Compiling a Lua Project. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

Initializing Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

Loading Scripts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

The Lua Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

Exporting C Functions to Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

Executing Lua Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

Importing Lua Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

Manipulating Global Lua Variables from C . . . . . . . . . . . . . . . . . . . . . . 226

Re-coding the Alien Demo in Lua . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

Advanced Lua Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

Web Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

The Python System at a Glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Directory Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

The Python Interactive Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

The Python Language. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

Basic Strings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

String Manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248

Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

Conditional Logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

Iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

Integrating Python with C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

Compiling a Python Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

Initializing Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

Python Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

Re-coding the Alien Head Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

Web Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

Tcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

ActiveStateTcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

The Distribution at a Glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

The tclsh Interactive Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289

What, No Compiler? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

Tcl Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

The Tcl Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

Commands—The Basis of Tcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

Conditional Logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

Iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

Functions (User-Defined Commands) . . . . . . . . . . . . . . . . . . . . . . . . . 310

Integrating Tcl with C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

Compiling a Tcl Project . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

Initializing Tcl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

Loading and Running Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

Calling Tcl Commands from C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

Exporting C Functions as Tcl Commands. . . . . . . . . . . . . . . . . . . . . . . 316

Returning Values from Tcl Commands . . . . . . . . . . . . . . . . . . . . . . . . . 319

Manipulating Global Tcl Variables from C . . . . . . . . . . . . . . . . . . . . . . . 320

Recoding the Alien Head Demo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322

Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330

Web Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330

Which Scripting System Should You Use? . . . . . . . . . . . . . . . . 331

Scripting an Actual Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

Chapter 7 Designing a Procedural Scripting Language..................335

General Types of Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

Assembly-Style Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

Upping the Ante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

Object-Oriented Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

XtremeScript Language Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

Syntax and Features. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

Operators and Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354

Code Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

Control Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361

Escape Sequences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

The Preprocessor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

Reserved Word List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

Part Four Designing and 

Implementing a Low-Level Language .............367

Chapter 8 Assembly Language Primer ..............369

What Is Assembly Language? . . . . . . . . . . . . . . . . . . . . . . . . . . 370

Why Assembly Now? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371

How Assembly Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

Operands. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373

Jump Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375

Conditional Logic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

Iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

Mnemonics versus Opcodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

RISC versus CISC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386

Orthogonal Instruction Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388

Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389

The Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389

Stack Frames/Activation Records. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392

Local Variables and Scope. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

Introducing XVM Assembly. . . . . . . . . . . . . . . . . . . . . . . . . . . . 397

Initial Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398

The XVM Instruction Set. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400

Bitwise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

String Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402

Conditional Branching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402

The Stack Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

The Function Interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

Miscellaneous. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

XASM Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404

Stack and Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405

Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406

Escape Sequences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407

Summary of XVM Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

Chapter 9 Building the XASM Assembler ...........411

How a Simple Assembler Works . . . . . . . . . . . . . . . . . . . . . . . . 413

Assembling Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414

Assembling Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416

Assembling Operands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420

Assembling String Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422

Assembling Jumps and Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423

XASM Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428

Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429

Input: Structure of an XVM Assembly Script . . . . . . . . . . . . . . . . . . . . . . . 430

Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431

Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439

Line Labels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440

Host API Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440

The _Main () Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441

The _RetVal Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441

Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442

A Complete Example Script. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442

Output: Structure of an XVM Executable . . . . . . . . . . . . . . . . . . . . . . . . . 444

Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444

The Main Header. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447

The String Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453

The Host API Call Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454

Implementing the Assembler . . . . . . . . . . . . . . . . . . . . . . . . . . 455

Basic Lexing/Parsing Theory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456

Lexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457

Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459

Basic String Processing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

Vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462

A String-Processing Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464

The Assembler’s Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469

The General Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470

A Structural Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470

Lexical Analysis/Tokenization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495

The Lexer’s Interface and Implementation . . . . . . . . . . . . . . . . . . . . . . 496

Error Handling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525

Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527

Initializing the Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528

Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529

Line Labels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542

Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543

Building the .XSE Executable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552

The Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553

The String Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556

The Host API Call Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557

The Assembly Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558

Loading the Source File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558

The First Pass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559

The Second Pass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560

Producing the .XSE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564

Part Five Designing and

 Implementing a Virtual Machine..................565

Chapter 10 Basic VM Design and Implementation ..567

Ghost in the Virtual Machine. . . . . . . . . . . . . . . . . . . . . . . . . . . 568

Mimicking Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569

The VM’s Major Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

The Runtime Stack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

Global Data Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573

Integration with the Host Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573

A Brief Overview of a VM’s Lifecycle . . . . . . . . . . . . . . . . . . . . 574

Loading the Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574

Beginning Execution at the Entry Point . . . . . . . . . . . . . . . . . . . . . . . . . . . 576

The Execution Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576

Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578

Calling a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578

Returning From a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580

Termination and Shut Down . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581

Structural Overview of the XVM Prototype. . . . . . . . . . . . . . . 582

The Script Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583

Runtime Values. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584

The Runtime Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585

The Frame Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587

The Host API Call Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587

The Final Script Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588

Building the XVM Prototype. . . . . . . . . . . . . . . . . . . . . . . . . . . 589

Loading an .XSE Executable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590

An .XSE Format Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590

The Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595

The String Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601

The Host API Call Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602

Structure Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603

The Instruction Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604

The Runtime Stack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621

The Host API Call Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622

Initializing the VM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624

The Execution Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627

Instruction Set Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628

Handling Script Pauses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633

Incrementing the Instruction Pointer . . . . . . . . . . . . . . . . . . . . . . . . . . 634

Operand Resolution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636

Instruction Execution and Result Storage. . . . . . . . . . . . . . . . . . . . . . . 637

Termination and Shut Down . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649

Chapter 11 Advanced VM Concepts and Issues......651

A Next Generation Virtual Machine . . . . . . . . . . . . . . . . . . . . . 652

Two Versions of the Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652

Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653

Multithreading Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654

Cooperative vs. Preemptive Multitasking . . . . . . . . . . . . . . . . . . . . . . . 654

From Tasks to Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658

Concurrent Execution Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659

Loading and Storing Multiple Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667

The g_Script Structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667

Loading Scripts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671

Initialization and Shutdown . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674

Handling a Script Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674

Executing Multiple Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677

Tracking Active Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678

The Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679

The First Completed XVM Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682

Host Application Integration. . . . . . . . . . . . . . . . . . . . . . . . . . . 682

Running Scripts in Parallel with the Host . . . . . . . . . . . . . . . . . . . . . . . . . . 683

Manual Time Slicing vs. Native Threads. . . . . . . . . . . . . . . . . . . . . . . . . 684

Introducing the Integration Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686

Calling Host API Functions from a Script . . . . . . . . . . . . . . . . . . . . . . . 686

Calling Script Functions from the Host . . . . . . . . . . . . . . . . . . . . . . . . 687

Tracking Global Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689

The XVM’s Public Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694

Which Functions Should Be Public? . . . . . . . . . . . . . . . . . . . . . . . . . . . 694

Name Clashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695

Public Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696

Implementing the Integration Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . 696

Basic Script Control Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 697

Host API Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700

Script Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711

Invoking a Script Function: Synchronous Calls . . . . . . . . . . . . . . . . . . . 713

Calling a Scripting Function:Asynchronous Calls . . . . . . . . . . . . . . . . . 719

Adding Thread Priorities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728

Priority Ranks vs.Time Slice Durations . . . . . . . . . . . . . . . . . . . . . . . . 730

Updating the .XSE Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731

Updating XASM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733

Parsing the SetPriority Directive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734

Updating the XVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735

Demonstrating the Final XVM . . . . . . . . . . . . . . . . . . . . . . . . . 739

The Host Application. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739

The Demo Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739

Embedding the XVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 741

Defining the Host API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742

The Main Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742

The Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747

Part Six Compiling High-Level Code .......749

Chapter 12 Compiler Theory Overview ................751

An Overview of Compiler Theory. . . . . . . . . . . . . . . . . . . . . . . 752

Phases of Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753

Lexical Analysis/Tokenization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755

Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 760

Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764

I-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765

Single-Pass versus Multi-Pass Compilers. . . . . . . . . . . . . . . . . . . . . . . . 766

Target Code Emission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768

The Front and Back Ends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768

Compiler Compilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769

How XtremeScript Works with XASM . . . . . . . . . . . . . . . . . . . . . . . . . . . 769

Advanced Compiler Theory Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 771

Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 771

Preprocessing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773

Retargeting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 778

Linking, Loading, and Relocatable Code . . . . . . . . . . . . . . . . . . . . . . . . 779

Targeting Hardware Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 780

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782

Chapter 13 Lexical Analysis ............................783

The Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785

From Characters to Lexemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785

Tokenization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787

Lexing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787

Lexer Generation Utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788

Hand-Written Lexers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788

The Lexer’s Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793

Reading and Storing the Text File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793

Displaying the Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795

Error Handling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797

A Numeric Lexer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797

A Lexing Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 798

State Diagrams. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799

States and Token Types. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800

Initializing the Lexer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800

Beginning the Lexing Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 801

The Lexing Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 802

Completing the Demo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809

Lexing Identifiers and Reserved Words. . . . . . . . . . . . . . . . . . . 811

New States and Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 812

The Test File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813

Upgrading the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814

Completing the Demo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819

The Final Lexer: Delimiters, Operators, and Strings . . . . . . . . 822

Lexing Delimiters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822

New States and Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822

Upgrading the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 823

Lexing Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 827

New States and Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 827

Upgrading the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828

Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 831

Breaking Operators Down. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832

Building Operator State Transition Tables . . . . . . . . . . . . . . . . . . . . . . . 836

New States and Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 840

Upgrading the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 841

Completing the Demo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 849

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856

Chapter 14 Building the XtremeScript Compiler Framework.............857

A Strategic Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 858

The Front End . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859

The Loader Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 860

The Preprocessor Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 861

The Lexical Analyzer Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 861

The Parser Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 862

The I-Code Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 862

The Back End . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863

The Code Emitter Module. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863

The XASM Assembler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863

Major Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863

The Source Code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863

The Script Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864

The Symbol Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865

The String Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866

The I-Code Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866

Interfaces and Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 866

The Compiler’s Lifespan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867

Reading the Command Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867

Loading the Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867

Preprocessing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867

Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867

Code Emission. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868

Invoking XASM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868

The Compiler’s main () Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868

The Command-Line Interface. . . . . . . . . . . . . . . . . . . . . . . . . . 870

The Logo and Usage Info. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 870

Reading Filenames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 871

Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 872

Reading Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874

Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 875

Elementary Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 880

Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 880

The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 881

Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 888

The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 888

Initialization and Shutdown. . . . . . . . . . . . . . . . . . . . . . . . . . . . 890

Global Variables and Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 890

Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 891

Shutting Down. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 892

The Compiler’s Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893

The Loader Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 895

The Preprocessor Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897

Single-Line Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898

Block Comments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899

Preprocessor Directives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 902

Implementing #include . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 902

Implementing #define. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903

The Compiler’s Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 904

The Symbol Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905

The SymbolNode Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905

The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907

The Function Table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 910

The FuncNode Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 911

The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 911

The String Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915

Integrating the Lexical Analyzer Module . . . . . . . . . . . . . . . . . 916

Rewinding the Token Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916

Lexer States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917

A New Source Code Format. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919

New Miscellaneous Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922

Adding a Look-Ahead Character . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922

Handling Invalid Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 923

Returning the Current Token . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925

Copying the Current Lexeme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 926

Error-Printing Helper Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 927

Resetting the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928

The Parser Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928

Error Handling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928

General Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928

Code Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928

Cascading Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 930

The I-Code Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 932

Approaches to I-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 932

A Simplified Instruction Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 933

The XtremeScript I-Code Instruction Set . . . . . . . . . . . . . . . . . . . . . . 935

The XtremeScript I-Code Implementation . . . . . . . . . . . . . . . . . . . . . . . . 935

Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 936

Jump Targets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 938

Source Code Annotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 940

The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 942

Adding Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 943

Adding Operands. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944

Retrieving Operands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945

Adding Jump Targets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 946

Adding Source Code Annotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947

Retrieving I-Code Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 948

The Code-Emitter Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . 949

Code-Emission Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 949

The General Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 950

Global Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 951

Emitting the Header. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 952

Emitting Directives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 953

Emitting Symbol Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955

Emitting Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 958

Emitting a Complete XVM Assembly File . . . . . . . . . . . . . . . . . . . . . . . 966

Generating the Final Executable. . . . . . . . . . . . . . . . . . . . . . . . 969

Wrapping It All Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 972

Initiating the Compilation Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 972

Printing Compilation Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 972

Hard-coding a Test Script. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 975

The Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 976

The Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 976

The Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 977

The Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 980

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 981

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 981

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 982

Chapter 15 Parsing and Semantic Analysis .........983

What Is Parsing? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985

Syntactic versus Semantic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985

Expressing Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 987

Syntax Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 987

Backus-Naur Form. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 988

Choosing a Method of Grammar Expression . . . . . . . . . . . . . . . . . . . . 989

Parse Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 989

How Parsing Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 993

Recursive Descent Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 994

The XtremeScript Parser Module . . . . . . . . . . . . . . . . . . . . . . 996

The Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 996

Tracking Scope. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 996

Reading Specific Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997

The Parsing Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1000

Parsing Statements and Code Blocks . . . . . . . . . . . . . . . . . . . 1001

Syntax Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1002

The Implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004

ParseSourceCode () . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004

Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1005

Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1007

Parsing Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1008

Function Declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1008

Parsing and Verifying the Function Name . . . . . . . . . . . . . . . . . . . . . . 1010

Parsing the Parameter List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1011

Parsing the Function’s Body . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1015

Variable and Array Declarations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1017

Host API Function Declarations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1021

The host Keyword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1022

Upgrading the Lexer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1022

Parsing and Processing the host Keyword . . . . . . . . . . . . . . . . . . . . . 1023

Testing Code Emitter Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1026

Parsing Simple Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . 1028

An Expression Parsing Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1028

Parsing Addition and Subtraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1028

Multiplication, Division, and Operator Precedence . . . . . . . . . . . . . . . 1030

Stack-Based Expression Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1031

Understanding the Expression Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . 1033

Coding the Expression Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1037

Parsing Full Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1048

New Factor Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1048

Parsing Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1051

New Unary Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1053

New Binary Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054

Logical and Relational Operators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1054

The Logical And Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1055

Relational Greater Than or Equal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1056

The Rest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1058

L-Values and R-Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1058

A Standalone Runtime Environment . . . . . . . . . . . . . . . . . . . 1058

The Host Application. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1059

Reading the Command Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1060

Loading the Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1061

Running the Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062

The Host API. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1062

PrintString () . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1063

PrintNewline () and PrintTab () . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1063

Registering the API. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1064

Parsing Advanced Statements and Constructs . . . . . . . . . . . . 1064

Assignment Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1065

Function Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1073

return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1075

while Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1079

while Loop Assembly Representation. . . . . . . . . . . . . . . . . . . . . . . . . 1079

Parsing while Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1081

break . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1086

Parsing break . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1088

continue. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1090

for Loops. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1092

Branching with if . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1092

if Block Assembly Representation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1092

Parsing if Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1094

Syntax Diagram Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 1099

The Test Drive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1099

Hello,World! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1099

Drawing Rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1102

The Bouncing Head Demo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1106

Anatomy of the Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1107

The Host Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1109

The Low-Level XVM Assembly Script. . . . . . . . . . . . . . . . . . . . . . . . . 1116

The High-Level XtremeScript Script. . . . . . . . . . . . . . . . . . . . . . . . . . 1127

The Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1132

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1134

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1134

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1135

Part Seven Completing Your Training ........1137

Chapter 16 Applying the System to a Full Game..............1139

Introducing Lockdown. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1140

The Premise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1140

Initial Planning and Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1142

Phase One—Game Logic and Storyboarding . . . . . . . . . . . . . . . . . . . 1142

Phase Two—Asset Requirement Assessment . . . . . . . . . . . . . . . . . . . 1150

Phase Three—Planning the Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1155

Scripting Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1157

Integrating XtremeScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1158

The Host API. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1158

Miscellaneous Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1159

Enemy Droid Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1159

Player Droid Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1159

Registering the Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1160

Writing the Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1161

The Ambience Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1161

The Blue Droid’s Behavior Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1162

The Grey Droid’s Behavior Script . . . . . . . . . . . . . . . . . . . . . . . . . . . 1163

The Red Droid’s Behavior Script . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1167

Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1171

Loading and Running the Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1171

Speed Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1173

Minimizing Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1174

The XVM’s Internal Timer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1174

How to Play Lockdown . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1175

Controls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1175

Interacting with Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1176

The Zone Map. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1176

Battle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1176

Completing the Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1176

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1177

On the CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1177

Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1178

Chapter 17 Where to Go From Here .................1179

So What Now? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1180

Expanding Your Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . 1181

Compiler Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1181

More Advanced Parsing Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1182

Object-Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1182

Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1183

Runtime Environments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1184

The Java Virtual Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1184

Alternative Operating Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1185

Operating System Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1186

Advanced Topics and Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . 1186

The Assembler and Runtime Environment . . . . . . . . . . . . . . . . . . . . . . . . 1186

A Lower-Level Assembler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1186

A Lower-Level Virtual Machine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1187

Dynamic Memory Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1189

The Compiler and High-Level Language . . . . . . . . . . . . . . . . . . . . . . . 1190

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1199

Appendix A What’s on the CD? ........................1201

The CD-ROM Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1202

Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203

DirectX SDK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1203

INDEX .......................................1205

  ●▬▬▬▬▬❂❂❂▬▬▬▬▬●

●▬▬❂❂▬▬●

●▬❂▬●

●❂●

═════● ●═════