Archive | April 2014

Rift – Syntactic Analysis

In which we define a big grammar to parse a program.

The parser for the Rift programming language compiler is done. It was developed using GNU Bison. The grammar file for the parser is in this file.

The rules of the grammar have two kinds of symbols. The terminals and the non-terminals. The non-terminals all have their own rules within the grammar and follow the conventions that all of it’s characters are lower case. The terminal symbols follow the convention of having uppercase characters and all start with T_. A rule from the grammar looks like the following:

var_decl: data_types T_ID T_SEMICOLON
| data_types T_ID T_EQUAL expr T_SEMICOLON

The terminal symbols in the grammar are called tokens and they came directly from the lexical analysis part of this compiler. This part, developed using Flex, defined a lot of rules that identified certain sequences of characters has a specific token. For example, the T_INT_B10_LIT token is used to expressed that a base 10 integer was found. Similarly, the T_EQUAL token is used when the = symbol is found.

Each grammar symbol has a type which is defined using the C, or in this case C++ types. Those type can be an integer, float, structure, class, etc. A special union is used in the grammar file to define the various types. Has of this version it looks like the following:

%union {
int token;
int ph;

It’s still very poor. It only defines two types, the token type which is an integer and a ph type, also an integer. The token type will be the type for every token returned by the scanner. Later that will also be changed, but for now it will be like this. The ph type stands for place holder and it will be the type for every non-terminal symbol. The non-terminal symbols will have a specific type later which will be defined using a class of the abstract tree. For now the placeholder is used because the tree was not developed yet.

The different rules should have an action associated with them that defines what the program should do when it recognizes that rule. For example, at same stage for parsing a rift file there would be a variable assign that would be recognized by this rule:

var_assign: postfix_expr T_EQUAL expr T_SEMICOLON { $$ = 10; };

The action of this rule is defined inside the curly braces. Inside the scope of the action there are variables that can be used and start with the dollar ($) symbol. This variables refer to the different symbols in the rule. In the example, $$ is the *var_assign* symbol, $1 is the postfix_expr symbol, $2 the T_EQUAL symbol, and so on. In the action the only thing that happens is that var_assign get the value 10 assign to it. Why?

Well, that happens because I just needed a placeholder action. Many of the rules don’t have any actions yet but some needed to have them to avoid some conflict. So I just left that in there. I’m sure that there might be a better wait for this temporary fix. But it works like this.

Prototype for the BinPy GUI project

This article defines an initial concept for the BinPy GUI. A prototype implementation is displayed as a bases for the GUI that is supposed to be developed. The article also defines a few new definitions that are very important to the development of the GUI.

Interface Mock-up

The interface, for both methods of usage, will look like the following screen.

BinPy Prototype Screen

The link for this prototype is here.

Of course there are a lot of things missing from the prototype, but to start, consider what there is now. There are a few menus in the menu bar, they are File, Edit and simulation. These menus are just a placeholder for now, but they have a few functionalities that are expected, like new file, save, save as….

The simulation menu will most definitely be in the final version because it will be the menu that will have all the actions to handle the circuit simulation. Things like starting and stopping the simulation, defining clock speed (if clock speed is not defined individually), or handle any other simulation definitions, will be placed there.

Some menus that will probably be implemented will be a settings menu and a help menu.

The tool bars that are showing don’t contain any icons, just text. In the final implementation they would off course contain icons relevant to their functionalities, the prototype has text only because there is no set of icons that fits this project. The functionalities implemented by the tool bar actions are just the same that are implemented by the menus. In the prototype every actions that shows in the menus is also in the tool bar, however, in the final project there will be a lot of functionalities in the menus and only the most used ones will be in the tool bars.

The tool bars should only contain the most used ones. A functionality can be implemented at a later time that allows the user to define which actions show up on the tool bar, or how many tool bars are there at any time.

The central area of the main visible window is divided into four sections. These sections are a combination of different splits of the area. To the left we see an area which refers to the digital elements catalog. This catalog contains every digital element that can be used, such as digital gates, flip-flops, clocks, etc. This widget needs to be costume made using the PyQt drawing capabilities, and because of that some further time needs to be expended on this area alone. This widget should display the different elements in different categories, for example, the gates categories containing every logical gate, the flip-flops category, the combinational category, etc. Each category work as a drop down menu which can either be open and displaying every element or closed.

In the center of the main window there is big area that display the circuit which is being worked on. This area needs a lot of development and it is going to be developed also using the PyQt drawing capabilities.

The right part of the central area contains two widgets. The top widget display which files are opened. Each entry on this list can contain sub entries. These sub entries are sub-circuits. The notion of sub circuits is discussed in section last section.

The bottom widget of the right part is the properties list. This list contains the set of properties for a given selected element. Suppose that some AND gate is selected. Then the properties list would display a few relevant properties for this gate, such as the given label of the gate, how many inputs it has, or it’s orientation (if it has it’s output turned to the right or up).

If there is no selected element the properties list would display properties of the circuit it self.

New Definitions

There are several new definitions that need to be discussed in the context of this project. These are things that are relevant to the GUI component of the BinPy project but not the BinPy project itself.

Input and Output

The first of those new definition is related to input and output. In the BinPy library we deal with inputs and outputs of gates and other digital element in a faily simple way. The input of an OR gate for example, can be defined directly in it’s constructor using the True and False reserved words. The input of a digital element can also be another digital element, such as an OR gate as the input of an AND gate.

What is important is that the notion of input is not a literal element like a gate or flip-flop, it is just a consequence of a connector or similar construction, or it is simply an hard coded value such has a True and False or a 1 and 0.

The same goes for output. There is never an explicit element that serves only for output, instead we have the output value of some digital element or simply the value of a connector.

In the graphical representation of a circuit input and output need to be explicitly defined using new digital elements. An input element would be represented using an element with a single output for a connector. The element would either have the value of 0 or 1, and that value would be displayed to the user, a like in the Logisim simulator. The user could then toggle this element for it to change from its value to the opposite. An output element would be similar, but its value would not assign by the user, it would be a consequence of what ever it is connecting to it.


The BinPy library has a Connector class which is used to connect the output of a digital element to the input of another. In the graphical representation of this circuit these connectors would be seen has a wire. To place a connector the user would have to click and hold on an input/output of a digital element, and release the mouse on another location, maybe another input/output of a digital element.

The graphical representation of a connector will of course be a wire. This wire will have different colors. These colors will be a light shade of green if it’s value is 1, a dark shade of green if the value is 0 and red if there is an error with the connector.

Circuits and Sub-Circuits

It very common to have the notion of sub circuit. Take the notion of an adder, for example. An adder takes two inputs and has two outputs. One output is the result of the addition, the other output is the carry of that operation. So if the inputs are 1 and 0, or vice-versa, the resulting bit will be 1, while the carry will be 0. If the inputs are both 1, then both the result and the carry will be 1.

Having an adder for two single bits isn’t very useful. But if we join many adder we get the opportunity to add numbers with many bits.

An adder, in this context, would be a sub-circuit. The user could build a four bit, or eight bit circuit using the single bit adder as a sub-circuit. The n bit adder could then be used as a sub-circuit in other bigger circuits like, for example, a processor implementation.

But how does this notion of circuit of sub-circuit translates to the implementation of a GUI? Well, to start we consider that each circuit is designed in the GUI and has a few inputs and outputs. That circuit is then saved in a file, which structure is yet to be defined. In another circuit design we can then import a previously saved circuit, which becomes a sub-circuit of this new one.

To clarify, we start a new project, which could be call 8 bit adder, and we then import the single bit adder which is now a sub-circuit.

The sub-circuits should be used like any other digital element. They look like a digital element that can be moves around and have their inputs and outputs.