ID:51625
 
Keywords: idea

Poll: FSM / Context-Free Grammar lib?

Go for it! 71% (5)
No way. 28% (2)

Login to vote.

Now that I can finally say goodbye to formally learning language processing, I figure that I might as well put the knowledge to some practical use.
Two of the things I learned during my Uni course this year were finite state machines and context-free grammars, and how the first can be used for controlling basic systems and the second to parse simple text sentences ina similar manner to regular expressions (the two are computationally equivalent, so anything you can do with FSMs you can do with Regex).

For example, an AI could be based on a state machine where certain inputs will move it from one state to another, or the game could be based on states, i.e. a state for the menu, a state for a lobby etc.

Context free grammars are slightly more complex but can be used to parse strings using a fairly simple format of rules, e.g.

S -> NP VP
NP -> N | Det N
VP -> V NP

N -> Fred | Dog
Det -> the
V -> saw | ate

This grammar would allow you to parse (or produce, if you work in the other direction) a sentence such as 'Fred saw the Dog' or 'The Dog ate Fred'. Attaching semantics means that you can attach meaning to these sentences using Lambda-calculus (which is a little more complex, but basically boils down to passing meaning upwards through the structure of the sentence). Semantics would probably come in a second installment of the library since I might not have enough time to implement it before I go home for Christmas and leave my PC behind.

Anyway, the library would include:
- FSM control, allowing basic system control and sentence parsing
- FSM combination, allowing machines to be built up from smaller machines.
- Perhaps FSM to Regex conversion, and maybe the other way around.
- Context Free Grammar controls
- A CYK parsing algorithm implementation to allow parsing of sentences
- Maybe semantic attachments to allow direct meaning to be attached to a sentence in a way your game or whatever can understand (even to the point of being able to directly call procs using call()(), e.g. the example sentences would be able to call, depending on implementation, Fred.saw(Dog) or Ate(Dog, Fred)).