All my projects are in the general area of designing and implementing computer languages. This includes creating software tools to help in these activities.
You are probably familiar with the idea of Graphical User Interfaces (GUIs) and the kinds of tools that can be used to create them (e.g. development environments). However, we often need to build a Textual User Interface (TUI) - for example, to recognise an expression to be drawn by a graph-plotting package, or to input a file of data into a statistical package - and although notations (grammars) and tools (e.g. lex and yacc) exist to help, they are not easy for non-experts to use.
One way of making grammars easier to use might be a tool with a GUI, that helps a user to build an informal picture of the structure of the text, which can then be automatically transformed into a grammar. The user should be able to "drag and drop" boxes corresponding to ideas like "a list of ..." or "a choice between ...", and to be able to nest them one inside the other as required. e.g.
|
| ||||||||||||||||
If time allows, the basic concept could be extended in various ways e.g.:
More information:
A common problem with grammars is that, for some reason, they are not in the
right form for the tools you want to use to process them (e.g. lex and yacc).
At its simplest, this can be a trivial notational problem, that the grammar is
not in exactly the right format (e.g. see BNF
and EBNF notations for grammars).
At its worst, a grammar can be ambiguous, and the problem is to track down
and resolve the ambiguity (e.g. see
ambiguous grammars).
However, the most common problem is that the grammar is too complicated for
the particular tool you are trying to use to process it (e.g. see
how to confuse parsers).
Unfortunately, there is no straighforward way to distinguish between the
previous two problems - all tools like yacc can do is report a problem and
leave it to the user to sort out (e.g. see
confusing yacc).
To solve the first problem, we just need a tool that can read and write
grammars, using simple dialogs to describe the exact formats of the input and
output.
We can then improve the usefulness of tool by making it manipulate the grammar
to remove ambiguities or otherwise simplify it. It will be necessary for the
user and the tool to cooperate, using a GUI to communicate - the tool
providing information about possible modifications, the user selecting
particular rules to be changed and the changes to make, and the tool
performing the transformations and reporting the results. One important
feature will be the ability to backtrack out of one or more unsuccessful
transformations and try another line of attack.
If time allows, the basic concept could be extended in various ways e.g.
More information:
Rainbow, LARD and Balsa are all languages used for designing asynchronous hardware in this department. To make the tools associated with each language available to all users, we would like to have translators that can convert between these languages. (Although these languages are used for hardware design, and Rainbow is designed for use with formal methods, neither of these aspects should significantly affect this project.) We would like the translator to be written in Java, using the available parser-generator tools (similar to lex and yacc).
The Rainbow language has several simple component sub-languages (Yellow, Green and Table), that can be used to describe different kinds of actions in different styles. It will be sensible to start by dealing with just one of these. Because of the intrinsic difficulties of translating between high-level languages, we really only expect a 95% translation, with the most difficult aspects being reported to the user for intelligent action.
There are several different possibilities, including:
We have a Rainbow compiler written in Java, that parses a Rainbow program to create parse-trees, checks them to deal with declarations and types, and then outputs "code" for the simulator. This project essentially consists of adding methods to each class used in the parse-trees, that will output the target HDL instead of simulator code. There are various possible target HDLs, including VHDL, Promela and Balsa.
A previous 3rd year project implemented a translator from Balsa to Rainbow, using JavaCC and Java. The output from this can then be used as the input to a Rainbow compiler (also written using JavaCC and Java) so we can run it on the Rainbow simulator. This project consists of integrating these two steps into one - i.e. modifying the Balsa translator to create the parse-trees that are currently created indirectly by the Rainbow compiler. It should then be possible to use the facilities of the Rainbow compiler to improve the translation of the Balsa.
The sub-languages of Rainbow (Yellow, Green and Table) can be used to describe different kinds of actions in different styles. It is expected that these different components will be used at different stages of the design. Typically, a design will start out in Yellow, which is similar to common programming languages. It will then be transformed into Green, which is closer to the real hardware, so that the user can modify any newly-visible details. For example, a variable in Yellow becomes a register in Green, and the user can then adjust the connections to the hardware devices that set or use its value.
Currently, a user has to convert Yellow to Green by hand. We want to provide automatic translations from Yellow to Green. We have a Rainbow compiler written in Java, that parses a Rainbow program to create parse-trees, checks them to deal with declarations and types, and then outputs "code" for the simulator. This project essentially consists of adding methods to each class used in the parse-trees for Yellow, that will output Green instead of simulator code.
More information: