Wednesday, November 26, 2008

Recursive Descent and grander ideas

I've spent the past week or so of spare time in between working on shipping projects refining my adventure game idea, and I've come to a decision. I'm not going to make an adventure game; instead, I'm going to reinvent MUDs. I have some experience with MUDs, and while I enjoy the concept greatly (especially allowing users to create the environment), I have never enjoyed the command interface. Too many non-intuitive commands to do things (especially allowing users to create the environment).

Part of my reinvention is to fix what I find to be this most annoying of issues - the lack of a natural-language-esque command system. To that end, I've been studying parsing, compiler-compilers, EBNF rules, all sorts of fun things. My initial path through this landscape took me to compiler-compilers like YACC, ANTLR, etc., but I grew frustrated by my lack of understanding into the problem domain.

So yesterday I decided to take a different route. I figured I'd retrace the steps it takes to create a compiler-compiler; that is, I must first understand compilers. To this end, I wrote a very simple expression parser, using recursive descent over an LL(1) grammar. Here's the grammar:

    1 //assignment:    ID EQU expression EOF

    2 //expression:    term (PLUSMINUS term)*

    3 //term:            factor (MULDIV factor)*

    4 //factor:        MINUS? (NUMBER | ID | LPAREN expression RPAREN)


    6 //ID:            [a..z A..Z]+

    7 //NUMBER:        [0..9]+

    8 //PLUSMINUS:    '+' | '-'

    9 //MULDIV:        '*' | '/'

   10 //EQU:            '='

   11 //LPAREN:        '('

   12 //RPAREN:        ')'

   13 //EOF:            [EOF]

The purpose is to parse expressions such as 'vara = 1 + 2 / (3 * varb)' and then evaluate the resulting tree. I'm not really sure if what I'm building is an Abstract Syntax Tree or not, but it suits my purposes. Anyway this is just my first attempt.

I wrote a scanner, which takes an input stream and returns tokens from it sequentially (a token being one valid element in the grammar), a parser which uses the scanner and returns a tree by consuming the tokens, and an evaluator which performs the work of turning the tree structure into run-time instructions. I added some state to the evaluator, such that it will store the expressions as assigned to variables so that other expressions can make use of them.

One neat feature I added was persistent expression evaluation - instead of storing just the result value of an expression with its label, I store the expression itself. This means that changing the value of one variable will change the value of all other variables that depend on the changed variable, and so on. Say I've got the following:

a = 1
b = a + 1
c = b + 1
d = a + b + c

d's final value here is '6' - but when I change a = 5, b becomes 6, c becomes 7, and d becomes 18. One challenge here of course is circular reference, but thanks to the answers I received to my question on StackOverflow regarding this I was able to detect when this is the case and throw an exception before an (appropriate) StackOverflowException occurs.

So I'll cut to the chase. What I'd like to build is a web-based MUD-like system that allows multiple people to interact in an environment that they can have a hand in building. I'd like the syntax to work something like this:

semantic openable has open and closed.
openable property open is not closed.
openable property closed is not open.
openable hearing open sets open and says "You open the @name." when closed; otherwise says "The @name is already open.".
openable hearing close sets closed and says "You close the @name." when open; otherwise says "The @name is already closed.".
openable hearing slam says "You slam the @name." when open; otherwise says "You must open the @name before you can slam it shut.".

The scenario the above demonstrates is the case when a player wants to define a class of behavior (called a Semantic) that represents something that can be opened and closed. I'll write another post soon about what this means and how I'm going to design this system.

No comments: