Thursday, September 22, 2005

Grammars

I had a couple of goes at creating a grammar programming language before. I posted some my results in this venture here and here. I never finished my implementation because I ran up against something tricky problems and got bored. Well, recently I started playing with this again but this time I finished!

If you're not familiar with grammars (I talked about using them for generating random names) they are collections of rules. As an example, let's make one production rule for all the vowels. We'll call the rule V.


[V] -> a | i | e | u | o


Pretty simple. Any [V], a non-terminal, can be reduced to anyone one of the vowels, a terminal. Now imagine we had the constants, too and something called "ends".


[C] -> b | c | d | ... | z //assume I've written them all out here
[ends] -> dar | ug | hir


We can line up these non-terminals ([C][V][ends]) to create names.


[name] -> [C][V][C][ends]


Then if we reduce [name] by randomly picking elements we'll be given a variety of randomly generated names. Of the form a constant, a vowel, a constant.


pick1: Nogdar
pick2: Hilug
pick3: Yahdar
etc


Pretty cool! Not just for names either - we can build random descriptions. Also grammars don't have to be reduced to strings they could be reduced to a list of functions or instructions.

At first I tried to create a nice parser written entirely in Lua. My last attempt had also been in Lua ... and it's painfully obvious it's just not the right language, for me, to do this stuff. So I did it in C#, the traditional way -- I parsed it and built a symbol tree.

There a lot of things that can be done witha symbol tree - it can be used to generate a C# data structure, that can the make use of the grammar. This would probably be the expected thing to do. If you want to go the program language route then you might change the tree to an ASM program or program for virtual machine (like the one .net uses). I didn't do either.

The program outputs the tree as a Lua program. (Previously I'd had written a Lua program that would write a lua program according to a grammar, that worked but had a restrictive syntax). Then the program generated works just like the grammar and can be run in Lua. The reductions are randomly picked (there's no options for probabilities like from the vowels be more likely to select 'e'. This is something that can be added later) Grammars can also be written that call Lua functions too! So that's quite a lot of power right there!

I had intended this program for world generation but currently I'll be using it for names and title generation. I may add a few extra steps like randomly generating the grammar itself (possibly with a grammar :D).


[metaEnds] -> "ends ->[" [C] [V] [C] "]"


If I polish it I may upload it as a sourceforge project as its potentially quite useful to others as well.

That's it! Following are grammar examples!

(These are taken (an converted) from http://www.ruf.rice.edu/~pound/ but it seems to be dead at the momement. The names are left undescriptive)

Psuedo French



Why did I choose this one it's massive! Oh well. Imagine in your game you could, on the fly create random foreign books - or have people randomly speak (say before you've learnt the language).


[words] -> [C][D][F] | [C][V]"n"[A][X] | [C][V]"n"[A][U] |
[C][V]"n"[A][T] | [C][V][M][T] | [C][D][M][U] |
[C][V][M][U] | [I][V][M][T] | [E][C][T] [C][V][Z][X]

[I] -> "in" | "ad" | "con" | "des" | "mal" | "pour" | "sous"

[E] -> "entre" | "re"

[T] -> [V][F]

[M] -> "l" | "ll" | "t" | "ss" | "n" | "m"

[U] -> "eur" | "ien" | "ant" | "esse" | "ent" | "able" | "oir" |
"eau" | "aire" | "erie" | "e" | "er" | "ir" | "ain" | "age" |
"ule" | "on" | "ade"

[C] -> "b" | "c" | "ch" | "d" | "f" | "g" | "j" | "l" | "m" | "n" |
"p" | "qu" | "r" | "s" | "t" | "v" | "s"[P] | [R]"r" | [L]"l"

[F] -> "c" | "f" | "gne" | "m" | "n" | "nt" | "p" | "r" | "sse" |
"t" | "s" | "l"

[Z] -> "c" | "f" | "gn" | "m" | "n" | "nt" | "p" | "r" | "t" | "s" | "l"

[A] -> "c" | "p" | "s" | "t"

[P] -> "p" | "t"

[Q] -> "b" | "d" | "g"

[L] -> "b" | "f" | "p" | "c"

[R] -> [P] | [Q] | "f"

[V] -> "a" | "e" | "i" | "o" | "u"

[D] -> "au" | "ai" | "oi" | "ou" | "ie" | "eau" | "oeu"

[X] -> "ee" | "e" | "ou" | "ie" | "eau" | "oi"

No comments: