next »

[MrGando]

Hello guys,

I have to propose a YACC/FLEX parser for a University project. The subject is open and I want to do something Game Related, I have like a month to work on this.

Does anyone have some suggestion about something that would be useful to do for a project like this ?, I'm open for ideas :-)

Cheers!
 

[increpare]

Obvious candidate would be writing a scripting language for a game?

(I take it you mean LEX rather than Flex).

[muku]

(I take it you mean LEX rather than Flex).

http://flex.sourceforge.net/  

Scripting language is the obvious choice, but they're a dime a dozen... Maybe something more specialized? It could be simpler and still produce more interesting results. Maybe an interpreter for an L-system, to create trees and plants for a game? Or some dialogue system language? Or a simple variant of one of those programming games a la http://www.robotbattle.com/ or http://www.corewars.org/ ? Or some music sequencing format a la MML? Dunno. I'd make something domain-specific.

[Cthulhu32]

One thing that the Lex/Yacc is good at is English language. So you could do some really interesting adventure style games where you ask a player for user input, then drive each state according to a series of questions/answers and content and parse out their answer according to your rules.

[Overkill]

Yacc is meant for writing context-free grammars. On the other hand, natural language like English is very context-heavy and ambiguous. Syntactic validation should be easy enough, but semantic checking could be painful. So make sure to only accept sentences of limited structure, like commands: "look at the treasure chest" (action article proper noun). But remember to support alternative actions that may mean the same thing, like "inspect the treasure", "examine the chest", "look at the red treasure chest". I think that could be a lot of fun.

My alternative suggestion is to make a simple scripting language with a few basic constructs. Parse it into an abstract syntax tree, (optionally) do semantic passes, then interpret/execute the tree. If you only have a month, I suggest keeping the feature set limited. Maybe support just a single number type for variables (one type = no real type-checking required), if statements, while loops, printing to stdout/reading from stdin, functions, maybe allow 1D arrays (and make strings into arrays of numbers). This is not as fun though.

Of course, you could go for something in-depth, but the time-frame sounds kind of tight, and if you get to choose what you're doing, you might as well avoid some work for yourself.

Oh! Maybe a dialogue scripting system for an RPG or something that's laid out sort of like a play?

[Cthulhu32]

Yacc is meant for writing context-free grammars. On the other hand, natural language like English is very context-heavy and ambiguous. Syntactic validation should be easy enough, but semantic checking could be painful. So make sure to only accept sentences of limited structure, like commands: "look at the treasure chest" (action article proper noun). But remember to support alternative actions that may mean the same thing, like "inspect the treasure", "examine the chest", "look at the red treasure chest". I think that could be a lot of fun.

Oops yeah thats what I meant when I said English language. So you could parse out their input as like "Look at the dog" or "Fight the grue" or something

[MrGando]

Thanks for the suggestions! ,

I really like them, the RPG dialog thing is quite cool.

Something I could also do was to script a particle engine that I have, do you think something like that could take a lot of work ?? Suggestions about scripting a particle engine are also welcome 

[Pineapple]

Thanks for the suggestions! ,

I really like them, the RPG dialog thing is quite cool.

Something I could also do was to script a particle engine that I have, do you think something like that could take a lot of work ?? Suggestions about scripting a particle engine are also welcome 

It really depends on how much experience you have dealing with parsing strings. Do you think you can tell your program to take a line of text and find the keyword and any arguments, while throwing errors if anything in the script file is incorrectly done?

[MrGando]

The idea is I think to use yacc to generate code that my "Particle Engine" could interpret to build systems according to the "scripted" specifications.

The idea is not to parse my Particle Scripting by hand with the engine... I would have to define some kind of syntax to work with my particle emitters, etc.

[Pineapple]

So yacc can't deal with strings? What kind of language is it?

[MrGando]

I think this: http://en.wikipedia.org/wiki/Yacc will explain better 

[Overkill]

_Madk: A very short summary, Lex scans the raw input and matches character sequences with regular expressions. These become tokens for the parser, Yacc, which defines a grammar in pseudo-BNF notation. Lex groups together the input into meaningful chunks, and Yacc is responsible for accepting/rejecting the token sequences that appear. This deals with most of the concrete syntax validation. Both Lex and Yacc can perform actions on matching rules, which would give you a way to examine the string data -- but often you won't care (and instead just keep the string around for later), since lexical scanning can categorize keywords, identifiers, numbers and operators for you.

Often it's a good idea to build an abstract syntax tree out of the concrete syntax you just parsed, discarding details you no longer need (like parentheses in an expression, which were only necessary to fix precedence, or curly braces around a block) and replacing them with nodes that represent their meaning (expression, function call, if statement, variable declaration). This allows semantic validation to be deferred until it's certain that the input is syntactically valid. By making this sort of categorization, it's also very simple to do multiple-passes over the same input stream, which is required for a lot of compiled languages.

There also are other tools out there that do parsing in a similar manner: JavaCC, ANTLR, ParrotVM compiler tools, and many others.