3

I'm not saying I want to create a whole new compiler that's completely independent. I'm using C# Windows Forms and I want users to be able to write filtering syntax in a textbox withing my managed application in a basic query language, for example:

inCategory(Animals)
where(animal.age > 40)
take animal;

It's basically a simplifed version of LINQ. But I want this logic to be enclosed in some separate class, so I can say something like this:

var dataQuery = FilterCompiler.Compile(filterTextBox.Text);
dataQuery.Execute();

I'm not saying 'gimee the code', but some psuedocode / basic logic structure for this 'compiler' would be nice since I am kind of clueless about this subject. Like for example,

  • What sort of text analysis would this FilterCompiler need to do?
  • What would be the type of dataQuery?
  • Would this require any knowledge of compiler grammar?
  • Would I need to use any unmanaged code?
  • How can I keep the compiling as independent as possible so that it does not depend too much on what type of data I have? Currently I have a List, but things change, I might have a database with the information in it soon.
  • last point; reflection – ratchet freak Dec 3 '14 at 16:20
  • Reflection in what? Where? – naiveai Dec 3 '14 at 16:21
  • 3
    Might want to have a look at this book: manning.com/rahien – pdr Dec 3 '14 at 16:26
  • 3
    I was with you up to "don't gimme the code, just...gimme..eh..coOode... y'know?" If you edit this question to ask about whether work like this is a good idea, and if your approach is good, or if there are other known approaches to your problem (giving users queryability of your dataset is a very common problem many people have run into and probably have insights on how to solve). Then I'd remove my close vote. As it stands, it's not really asking an answerable question so much as for help writing code.. – Jimmy Hoffa Dec 3 '14 at 16:34
  • I defined some questions that I wanted to ask in essence and I just said the basic logic for the compiler would help greatly. – naiveai Dec 3 '14 at 16:41
4

Unfortunately its not really that simple, you have a few options...

Coco/R

If you aren't going to do a complex language and only support a few custom keywords, I would suggest something like Coco/R. I have used this several times in the past to create parsers for all kinds of projects.

The jist of it would be that you create a grammar file that describes your language and it allows you to plug in your own functions when certain tokens are found. This may be a little more difficult because it appears that your sample language understands the concepts of Objects and Coco/R actually creates classes that you compile. This means you are going to have to build these sort of things in to the parser and/or use interfaces. You are also doing arithmetic which means you are going to have to write an expression evaluator.

Compile with .NET classes

Another option is to not actually create your own syntax but use something like .NET's built in classes to compile code. This saves you a lot of work (read ton of work) but you lose the flexibility of creating your own simplistic language. More information can be found here.

Reflection.Emit

Another option which would probably be the most complex and not really worth it would be to write IL using reflection and then compile that code to a dynamic function and execute it. You would have a lot of trail and error making sure that you generate valid IL that doesn't just crash and throw up some strange errors that are nearly impossible to track down. There are a lot of benefits from this tho, the user could write complex code that could interact with your own objects (like a real scripting language) and would be easy to extend once the framework was built. More info can be found here


If I personally had to choose one it would come down to what I needed it for. If I was developing this for my company I would probably go with Reflection.Emit and if I just needed something to work right now and fast I would go with using the .NET libraries to just compile C# code to a app domain that I then would just execute. If the language only had a small subset of features I would probably go with Coco/R, but I have a lot of experience with it and there would be no learning curve there for me.

Sorry for the terrible formatting, I'm still rather new to MD.

15

What you are looking at creating is known as a standalone DSL (with a separate syntax and interpreter), as opposed to an embedded one (which shares syntax with a host language).

This will require the skills necessary to build a simple interpreter, at a minimum.

In its simplest form, this entails the following:

  1. Reading in the text.
  2. Performing lexical analysis, which breaks the input text into discrete language-specific entities known as tokens. This step is frequently referred to as lexing.
  3. Performing syntactic analysis, which builds expression trees from the stream of tokens. This step is frequently referred to as parsing.
  4. Interpretation, which accepts the expression trees (in your case, this would be some tree of objects) and then executes the actions indicated by the semantics of your language.

Steps #2-3 are not commonly done through hand-written code, except in the case of full-blown language interpreters. Frameworks or code generators, like lex and yacc for C, are by far the most common method of implementation.

Compilers: Principles, Tools and Techniques (affectionately known as The Dragon Book for the theme of its covers) is a highly regarded source on these sorts of steps.

As an aside, this all seems like a very large amount of work for what it is you really want to accomplish, especially since Microsoft has included a simple expression language on the DataTable structure used by ADO.NET (see here for more information: http://msdn.microsoft.com/en-us/library/system.data.datacolumn.expression(v=vs.110).aspx). Building a user-facing DSL for filtering seems like overkill. If you need complex grids and similar functionality, it would likely be more time efficient to look at a component vendor like DevExpress or Telerik.

3

What sort of text analysis would this FilterCompiler need to do?

It would need to be able to interpret the input and understand what is good/bad. I would recommend following the standard lexer/parser approach, as it is well known and robust in the face of uncertainty (read: user input).

What would be the type of dataQuery?

Func<T, T> (where T is whatever enumerable you're working against) probably.

Would I need to use any unmanaged code?

Not at all.

.NET has a very nice library to compile delegates on the fly for things specifically like this: Expression Trees. You can even use reflection to know what properties/fields are legal identifiers. Resolving the identifiers to reflection objects and then building the expression trees is about as straight-forward as these things get.

  • 1
    I like this approach. Building a supplementary lexer/parser is probably overkill when expression trees can likely accomplish what the OP wants. – Chris Cirefice Dec 3 '14 at 16:47
  • 2
    @ChrisCirefice - expression trees will only help building the actual operations into executable code. You still need to parse the input. – Telastyn Dec 3 '14 at 16:48
  • Hmm... Well it doesn't seem like the OP has a huge language to work on, so hopefully that won't be too hard. Then again, if he doesn't know about lexing/parsing at all it might be difficult to get to ETs in the first place – Chris Cirefice Dec 3 '14 at 16:56
  • 1
    Ya lexing and parsing is definitely on my agenda. – naiveai Dec 4 '14 at 1:25
  • 1
    @eshansingh1 - Original Poster. – Telastyn Dec 4 '14 at 2:34
2

A lot of the answers above recommend using parser generators (which are programs that you supply with a description of your language and which then produce code you can compile to parse it). I would actually recommend against this approach. It can often be tricky to understand what's going wrong when such parsers fail, and getting them to produce sensible error messages is an artform of its own.

For simple languages, it can actually be easier to hand-code your own recursive descent parser. Here's a simple example to get you started.

1

Sounds like what you want is a script interpreter in your code, to set up a domain-specific language. As one of the comments notes, there's a book out there about doing this for .NET code, using the Boo language, which can either be used as a compiled language in its own right or as a interpreter on top of an existing CLR program. Boo isn't really mainstream, but it's open-source and it's got a lot of useful features specifically for metaprogramming and DSL creations, and if you went that route you wouldn't need to build your own parser.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.