How do I start creating a small compiler for a school project in java or c#

Question

for my final exam (to graduate from university) I’ve been asked to create a tiny compiler, with the following requirements:

The student must develop a basic compiler with all the design parts that conforms it (lexical analysis, syntaxis analysis, parsing, etc). This compiler will have an interface that shows 2 panels, a graphic representation (A) and code representation (B). The user will be able to draw a geometric shape in panel (A), and the program will show in panel B the code generated for that shape, and the if the user types code in (B) it will show the shape in (A).

This compiler must handle at least 7 primitives (I guess this means commands). The geometric shape must be created from the primitives. The student will have to include a primitive to rotate the shape.

So the thing is that we never studied compilers in depth, just the very basic theory, I only have 20 days to finish this!! and I’m pretty sure they want to make me flunk because I asked the professor to tell me what is a primitive and he said he wouldn’t answer that because that is part of the vocabulary of the course I want to pass.

So the question here is:

How should I start, how do I create this thing in .NET or how do I create my very small set of instructions to create geometric shapes?

Is there something out there similar to this requirement to take it as an example and modify it?

P.S.: I’m a .net C# developer (good skills). I know the basics of C and Java. I’m reading about parser generators (ANTLR, lex & YACC, Ray) but there’s no basic tutorial for that, there are a lot of new terms like BNF grammar (what is this, a language, a txt file?). It is so hard because there’s no easy way to start, or samples for C#. I don’t want to do this project in C or C++ because since it’s using graphics and my C knowledge is basic, I’m afraid I won’t be able to do it, I would like to use .Net

Answer 1

It sounds like the exercise is about generating and parsing something like SVG. It also sounds like the professor is not completely clear on what a compiler is. Translating from text to graphics might be within some academic definition of compiler, but it certainly doesn't reflect any real world meaning (in spite of work done on graphical programming languages).

Perhaps to fulfill the requirement of "compiler" you could translate a subset of SVG (which is textual) to JavaScript commands for generating the graphics. For the meaning of "primitive" you could just google it. Sort of, show some initiative.

Then you could do your user interface in HTML, which would fit the time frame better than anything else I can think of. Essentially this would be something like Google Documents Draw, except with display of the drawing's representation as SVG.

Answer 2

This isn't so much a compiler as an interpreter/designer. But I digress.

Basically what you are being asked to create is a "drawing command language", and a program that can interpret that command language. For an example of what a "drawing command language" is usually expected to do, take a look at LOGO.

What you are required to do is to define a simple set of instructions (primitives) that will, in the proper combination, cause a shape to be drawn. You will also have to include a primitive to rotate the shape. Here's the Wikipedia definition of "primitive" in the appropriate context. By doing this, you are creating a "language" and a "runtime"; theoretically you could save the commands in a file, then re-load them into the program and re-run them to generate the same shape.

There are three major ways you could go with this:

• Define primitives to draw different types of lines (straight, curved, solid, dashed, etc etc) and set the color with which to draw the next line(s). This would likely have you creating primitives just to create primitives; your main primitives will be "Set Color" and "Draw Line".

• Define primitives to draw various pre-defined shapes (line, circle, rectangle, pentagon, hexagon, etc etc). This is probably what your classmates will do, and it's going to both take a while and not be very functional.

• Implement "turtle drawing" much like LOGO. There would be a cursor (the "turtle") that is represented on-screen somehow, and its current location and where it goes is integral to the drawing of lines.

Personally I like the last idea; you'll need primitives to move the turtle, to mark the start and end positions of lines, set colors, rotate, clear, etc:

• MVUP x - Move turtle up by x pixels
• MVDN x - Move turtle down by x pixels
• MVLT x - Move turtle left by x pixels
• MVRT x - Move turtle right by x pixels
• SETC r g b - Set the line-drawing color to an RGB value
• STLN - Mark the start of a line at the turtle's position
• ENDL - Mark the end of a line at the turtle's position; causes the line to be drawn from start to end using the currently-set color.
• RTCL x - Rotate canvas x degrees clockwise (this requires some matrix math, and you will lose anything you've drawn that falls outside the canvas after rotation)
• RTCC x - Rotate canvas x degrees counter-clockwise (ditto)
• CNTR - Place turtle in the very center of the canvas. Useful when defining an initial position from which to begin, or to avoid reversing a number of complex movements to get back to the center and draw again.
• CLRS - Remove all drawn lines from the pad. This, along with CNTR, should probably be the first two commands in a "program" to draw any particular shape, but if you omit them, the program can build on itself iteratively by being run on top of its previous output to create fractal patterns.

I just gave you 11 primitive commands that could be used to move a cursor from place to place on a canvas, drawing lines as you go, and could draw any 2D shape the user wished. You could also use a forward-backward-turn left-turn right model, as if the turtle were a robot, but that would probably make this more complex than it has to be (remember YAGNI; it will serve you well in industry).

Once you have the language, you have to make it work 2 ways; first, the program has to know how to interpret the instructions entered in a textbox in order to draw/redraw the shape on a drawing pad, and second, the program has to accept mouse input on the drawing pad, interpret those commands as moving the turtle/marking start or end/setting colors, and enter the commands into the textbox. That's your project, and I leave its implementation to you.

Answer 3

I recommend you implement Context-Free Art.

It will be relatively ugly to convert drawing to code - you'll inevitably describe a set of fixed shapes at fixed locations. And all your classmates will do likewise.

But by implementing the context-free grammar, you'll be able to generate absolutely stunning pictures from code. This will be massively satisfy and will spur you to polish and pass and you'll be left with something to show off afterwards.