Kernel word recovery crack, Mobile themes website for samsung wave 525, Dekha ek khwab sony tv title song, Song zombies on your lawn, Bloody mary nerve endings mp3, Digittrade tv jukebox, Padosan songs mp3, Gold cup series 70 manual, Nieuwste versie van mozilla firefox en, Cant install spotify on mac, Web brute force password cracker, Belkin g peek driver windows 7

Dynamic parser engine for Qt

July 20th, 2009 by Martijn Leave a reply »

I’m still working on a long term project to write a music editor, something I will describe more in detail at another time. Suffice it to say that the vi editor was an important model for it, and that I want to be able to perform every operation using commands I can type on a command-line, and using keyboard shortcuts in a command-mode that generates sentences in the command language. I also want the language to be extensible by plugins and other commands. Using a command language as a base for the program’s operation also brings me the benefits of easy undo implementation, macros and save files with full history.

I could probably have used QtScript instead of defining my own command language, however I wanted the syntax to be close to vim’s, I wanted the syntax to be easy to use as a command language, not as a scripting language, and I needed a parser anyway to grok command-mode commands. I didn’t like any of the existing parser generators and parser engines I could find, so I spent some time writing a dynamic parser engine that is nearing completion now.

I tried hard to break free from the Yacc/Lexx tradition, and used some concepts borrowed from NLP. The idea was not to create the most efficient parser (computers are fast anyway), but one that is easy to use and reuse (and probably abuse). It allows for optional words and ambiguous sentences. It is not token based, ie. there is no separate tokenizer and it can be specified per terminal whether it requires whitespace at the end or not. Commands are parsed as soon as the user starts to type so feedback can be given whether the syntax is valid, and completions can be shown. This also makes for a powerful context help mechanism.

The following piece of code shows how to create a basic grammar. A “sentence” is a toplevel command. The “verb”, “object” and “complement” functions specify named groups. The “cut” functions here are borrowed from prolog, and are just optimizations: they tell the parser to commit to the current parse tree (no backtracking) up to the cut when one is encountered.

Grammar* g = new Grammar();
g->addSentence( "debug_cmd", 
    sentence( verb("debug"), object(r(GRAMMAR_TOP))) );
g->addSentence( "goto_cmd", 
    sentence( verb("goto"), cut(), complement("position", r("position_expr"))) );
g->addSentence( "move_cmd", 
    sentence( verb("move"), cut(), object(optional(r("object"))),
    complement("position", r("position_expr"))));
g->addSentence( "mark_cmd", 
    sentence( verb("mark"), cut(), object(r("mark"))) );
g->addSentence( "dm_cmd", 
    sentence( verb("dm"), cut(), object(oneormore(r("mark")))) );
g->addSentence( "quit_cmd", 
    sentence( verb("quit"), cut() ) );
 
g->addRule( "object", choice( w("cursor"), r("mark") ) );
g->addRule( "position_expr", 
    choice( r("time_expr"), r("metric_expr"), r("mark") ) );
g->addRule( "time_expr", 
    seq( complement("value", number()), complement("unit",r("time_unit")) ) );
g->addRule( "time_unit", wordchoice( "ms", "s", "m", "h" ) );
g->addRule( "metric_expr", seq( number(), r("metric_unit") ) );
g->addRule( "metric_unit", 
    wordchoice( "measure", "measures", "bar", "bars" ) );
g->addRule( "mark", choice( r("global_mark"), r("local_mark") ) );
g->addRule( "global_mark", rx( "\\b[A-Z]\\b" ) );
g->addRule( "local_mark", rx( "\\b[a-z]\\b" ) );

The next piece of code illustrates how to bind commands to the (transformed) parse trees. The ArgSpec provided in registerCommand define the mandatory named groups in a matched sentence. The command with the most specific matching ArgSpec will be executed. This allows commands to be overloaded.

Executer* x = new Executer();
x->setContext( new Context() );
executer->registerCommand( "debug_cmd", ArgsSpec(), &Context::debugCommand );
 
ArgsSpec goto_args;
goto_args.insert( "position", "position_expr" );
x->registerCommand( "goto_cmd", goto_args, &Context::gotoCommand );
 
ArgsSpec move_args;
move_args.insert( "object", "" );
move_args.insert( "position", "position_expr" );
x->registerCommand( "move_cmd", move_args, &Context::moveCommand );
 
ArgsSpec mark_args;
mark_args.insert( "object", "mark", ArgsSpec::ArrayType );
x->registerCommand( "mark_cmd", mark_args, &Context::markCommand );
 
ArgsSpec dm_args;
dm_args.insert( "object", "mark" );
x->registerCommand( "dm_cmd", dm_args, &Context::deleteMarksCommand );
 
x->registerCommand( "quit_cmd", ArgsSpec(), &Context::quitCommand );

And finally, a function that demonstrates how to implement a command function that can be called by the Executer.

void Context::gotoCommand( Args args ) {
    ConstituentNode* position = args[ "position" ];
    if ( position->isa( "time_expr" ) ) {
	log( "goto time " + position->value( "value" ) 
	      + " " + position->value( "unit" ) );
    }
    else if ( position->isa( "metric_expr" ) ) {
	log( "goto metric " + position->value( 0 ) + " "
	      + position->value( 1 ));
    }
    else if ( position->isa( "local_mark" ) ) {
	log( "goto local mark " + position->value() );
    }
    else if ( position->isa( "global_mark" ) ) {
	log( "goto global mark " + position->value() );
    }
}

Some random notes to finish this quick tour:

– This is unfinished work. The API will change. (ConstituentNode is a bad name, registerCommand
may take an extra instance argument, etc)
– A mechanism will be added to do automatic type conversion. For instance, convert a time_expr
(value + units) to a normalized time in second that is easier to use in a function, and easier to extend
(the move command doesn’t need to be modified if a time unit is added).
– Custom completers (for instance for filenames) are not shown here. (work in progress)
– The library includes a command-line widget with autocomplete functionality.
– A Context base class is provided with functions to access history and ease debugging.
– I don’t share the source at the moment, but it will be open source once it is in a more finished state.

Advertisement

1 comment

  1. Judith Maltz says:
    Hello Martin,
    Bernie's friend Judy here checking you out since Bernie sent me his new e-mail address with www.vdkwast.com.
    Working on a music editor eh? I have Sibelius 4 but haven't had time to use it for awhile. Worked well for me but is complicated to learn, of course.
    Regards to your pa, Joke, Doreen, Sebastien, Maghda and Frank.
    Hope the winter is kind to you all. We've been snowed under for months in Silverton.
    Cheers,
    Judy

Leave a Reply

Authorized tags:
[b]bold[/b] [u]underline[/u] [i]italic[/i] [url=http://link.url]link[/url] more