Project Logs

Collapse

• Code Generation

  Reed Foster • 02/03/2018 at 02:58 • 0 comments

  I'm now almost done with the first revision of this project. I intend to continue to extend the language (I've already extended the specification; I just need to implement it) so that it actually achieves my goal of being more beginner friendly while still maintaining some amount of versatility and structure.

  Most of the code generation (the part I most recently finished, which takes a syntax tree and actually generates code in the target language: VHDL) was quite easy to implement; I simply traversed the parse tree and concatenated the strings in each node, adding some of VHDL's syntax in here and there. It was easy because a lot of my language is structured the same way as VHDL, so even though I'm doing the whole "parse it into a tree and generate a string from the tree" thing, I could just be doing string replacement. However, some aspects of my language (like direct connections between subcomponent ports), aren't directly translatable into VHDL. For this, I just compile a dictionary of all of the input and output ports that are used in signal assignments in the CDL program, and then create signal aliases for the ports, replacing (in the CDL source code's parse tree) the identifiers for the ports with their aliases. For the port mapping stage of VHDL component instantiation, I then just direct the port to its signal alias and voila, I'm done.

  Next, I need to deal with multi-file projects and dependencies. With CDL's specification, there is no subcomponent declaration, only instantiation. In order to generate VHDL with component declaration, I need to retrieve information from another source file that has the component's generic and port definitions. I may simplify things for the purposes of just getting the first revision done by requiring that all component definitions that are dependents are in the same file as their supercomponent.

  Finally, I need to handle the issue of types. I've dramatically reduced the number of types offered, and plan to change the way that arithmetic operations work on different types (e.g. addition of bit vectors is the same for signed and unsigned vectors --- in fact, I don't even have signed and unsigned bit vectors). Because of this, my type system is not directly translatable to VHDL. This will probably be the most difficult part of development of the code generator (I'm not really sure where I'm gonna start at this point), but I think once I figure out what to do, it shouldn't take very long.

• Parsing!

  Reed Foster • 01/30/2018 at 17:46 • 0 comments

  After a little bit of work and testing, my lexer was complete and I was ready to work on generating a syntax tree from the tokenized source code. This is where the language grammar really starts to come in. With the lexer, all I was doing was matching strings with ones that I knew were special and creating Token objects from each string. Each Token object contains the string from the source code as well as another string that specifies the type of token (identifier, operator, keyword, etc.). With the lexer, context didn't matter, whereas when parsing the token stream, the parser needs to follow a syntax rule. Using my definition of the grammar, I created a parsing method for each nonterminal which would "eat" tokens to parse terminals and call parsing methods on any nonterminals included in the definition of the original nonterminal. This process was methodical enough that I actually considered automating the process. I dismissed the idea, however, after I realized that it'd be somewhat involved, and at this point in my project, I don't want to waste time on an endeavor that could end up being rather complicated. (I realize that there are tools such as lex and yacc that I could use, but that's not the point; I feel as though I'll learn more by doing everything myself rather than using libraries). Anyhow, I eventually completed the parser (after a couple hours of bug-chasing). In order to actually verify that the parser output (the syntax tree), I had to write the framework for my code generator (the second stage of compilation) to traverse the syntax tree. For this, I copied the technique I found on this blog for recursive traversal of the tree.

  Here's a screenshot of a tree generated by my lexer and parser when given the following sample source code.

  component CompName
  {
      int genericint;
      bool genericbool;
      vec genericvec;
  
      port
      {
          input int inputint;
          input vec inputvec;
          output bool outputbool;
      }
  
      arch
      {
          signal vec foo;
          foo <= fox < banana;
          CompType compinst = new CompType(lol = 3, foo = 5, banana = x"4");
      }
  } 

• Implementation

  Reed Foster • 01/05/2018 at 04:52 • 0 comments

  Once I had a first revision of the language grammar formally specified, I broke out the Python. One of the differences I quickly noticed between lexical analysis of my language and of logical expressions is that there are a lot of symbols that need to be detected, many of them having varying lengths, and even some having the same start character. I (incorrectly/unnecessarily) decided that I needed to differentiate between two tokens that look identical but have different meanings depending on their context. The signal assignment and less than or equal to operators are both "<=" strings, but they don't mean the same thing. What I didn't really stop to think about was the fact that the semantics of the token don't matter in the lexical analysis phase of compilation, and that I could use a single token type to identify both signal assignment and less than or equal to operators. Oh well.

• Language Design

  Reed Foster • 01/05/2018 at 04:40 • 0 comments

  Once I got the lexer and parser working for my logical expression grammar, I decided to work on designing the grammar for my own language. Before I wrote a formal specification in Backus-Naur Form of my language, I sketched out some source code in the form of example design units in order to get a feel for what I wanted in terms of syntax and code structure. I then began to write the BNF grammar using the sample source code for reference.

• Early Stages

  Reed Foster • 01/05/2018 at 04:38 • 0 comments

  In order to design and implement my own programming language, I needed to understand some language theory as well as compiler theory. I decided to learn about compilers first. With the help of several StackExchange posts and online forums, I came across a blog on designing a Pascal interpreter. The series of blog posts about designing the different parts of the interpreter and the gradual additions to it which added functionality proved to be an invaluable resource to me. Ultimately, the front-end of my compiler is structured very similarly to the one presented, just with a different language specification.

  To test my knowledge, I wrote a language specification for logical expressions (a follow-on to a previous assignment in my computer science class), then programmed a lexer and parser that generated an abstract syntax tree from a logical expression string.

• Why a New HDL?

  Reed Foster • 01/05/2018 at 04:35 • 0 comments

  I’ve done a fairly significant amount of digital design with VHDL. Some of VHDL’s drawbacks include a type system that can be confusing for beginners, as well as verbose syntax and a lack of case-sensitivity. Some of my projects became difficult for me to manage because of the verbosity, so I decided to look for alternatives. I didn’t really find anything that looked like it would solve my problems without creating a lot of new ones. I decided that making a new hardware description language heavily based off of VHDL would be both a great learning experience as well as an opportunity to make a tool that would help me and potentially others.

View all 6 project logs