Skip to content

Instantly share code, notes, and snippets.

@anissen
Last active March 24, 2016 20:14
Show Gist options
  • Save anissen/cafce1517bb1994b8003 to your computer and use it in GitHub Desktop.
Save anissen/cafce1517bb1994b8003 to your computer and use it in GitHub Desktop.
Parser for simple generative grammar
enum Token {
TSymbol(s :String);
TTerminal(s :String);
TArrow;
TPlus;
TBracketOpen;
TBracketClose;
TNumber(v :Float);
TEof;
TEol;
}
enum Expr {
EGenerator(symbol :String, value :Null<Float>, results :Array<String>);
}
class Lexer extends hxparse.Lexer implements hxparse.RuleBuilder {
static public var tok = @:rule [
"=>" => TArrow,
"+" => TPlus,
"[" => TBracketOpen,
"]" => TBracketClose,
"[A-Z][a-zA-Z0-9_]*" => TSymbol(lexer.current), // symbol; uppercase starting letter
"[a-z][a-zA-Z0-9_]*" => TTerminal(lexer.current), // terminal; lowercase starting letter
"(([1-9][0-9]*)|0)(.[0-9]+)?" => TNumber(Std.parseFloat(lexer.current)),
"#[^\n\r]*" => lexer.token(tok), // comment
"[\t ]" => lexer.token(tok), // whitespace
"[\n\r]" => TEol, // line break
"" => TEof
];
}
class Parser extends hxparse.Parser<hxparse.LexerTokenSource<Token>, Token> implements hxparse.ParserBuilder {
public function parse() :Array<Expr> {
return parseStatements([]);
}
function parseStatements(stm :Array<Expr>) :Array<Expr> {
return switch stream {
case [TSymbol(s), v = parseValue(), TArrow, first = parseString(), rest = parseGenerators()]:
stm.push(EGenerator(s, v, [first].concat(rest)));
parseStatements(stm);
case [TEol]: parseStatements(stm);
case [TEof]: stm;
}
}
function parseValue() :Null<Float> {
return switch stream {
case [TBracketOpen, TNumber(v), TBracketClose]: v;
case _: null;
}
}
function parseGenerators() :Array<String> {
return switch stream {
case [TPlus, s = parseString(), e = parseGenerators()]: [s].concat(e);
case [TEol]: [];
case [TEof]: [];
}
}
function parseString() :String {
return switch stream {
case [TSymbol(s)]: s;
case [TTerminal(s)]: s;
}
}
}
class StringEvaluator {
static public function eval(e :Expr) :String {
return switch(e) {
case EGenerator(s, v, r): '$s becomes $r' + (v != null ? ' with probability $v' : '');
}
}
}
class TypeEvaluator {
static public function eval(e :Expr) :Dynamic {
return switch(e) {
case EGenerator(s, v, r): { symbol: s, value: v, results: r };
}
}
}
class Test {
static public function main() {
function get_parser(s :String) {
var lexer = new GeneratorParser.Lexer(byte.ByteData.ofString(s));
var ts = new hxparse.LexerTokenSource(lexer, GeneratorParser.Lexer.tok);
return new GeneratorParser.Parser(ts);
}
function validate(s :String) {
var parser = get_parser(s);
try {
var parsed :Array<GeneratorParser.Expr> = parser.parse();
for (p in parsed) {
var actual = GeneratorParser.StringEvaluator.eval(p);
//trace(actual);
}
} catch (e :hxparse.ParserError) {
trace('Parse error', e);
trace('==> Validate failure: $s');
}
}
function invalidate(s :String) {
var parser = get_parser(s);
try {
var parsed :Array<GeneratorParser.Expr> = parser.parse();
trace('==> Invalidate failure: "$s":');
for (p in parsed) {
var actual = GeneratorParser.StringEvaluator.eval(p);
trace('----> $actual');
}
} catch (e :hxparse.ParserError) {
// ok
}
}
// Symbol => Symbol | Terminal
validate('Symbol => Symbol + terminal');
validate('Symbol => terminal1');
validate('Symbol => terminal_blah1 + terminal2 + terminal3');
trace('------------');
validate('# blah');
validate("Symbol => Symbol1 + Symbol2\nSymbol1 => terminal");
validate('# this is a comment\n\rSymbol => Symbol1 + Symbol2\nSymbol1 => terminal');
trace('------------');
validate('Symbol [20]=> terminal1');
validate('Symbol [12.3]=> terminal1');
validate('Symbol [3.4567989]=> terminal1');
trace('------------');
invalidate('Symbol => Symbol terminal');
invalidate('Symbol => Symbol ++ terminal');
invalidate('Symbol =>=> term');
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment