Implementing a Parser and Simple Compiler for the Java Virtual Machine

1. Overview


  This document covers the implementation of a simple recursive-descent parser for an infix adder language with a lexer, parser, and compiler.  The language is implemented with Java and compiles to Java Virtual Machine (JVM) bytecode.  The first implementation of the compiler is different from other implementations because it is fully implemented in one class without third party parser generator libraries.  The implementation of the language only uses the Java standard libraries.  The code for the parser does not use a parser generator so it only contains pure Java standard libraries and no references to third-party libraries.

I wanted to discuss this particular example it helps for you to understand the nature of programming languages and their implementation.  Don't be scared about the parsing input token routines in them.  They help as a tool to the developer.  This a basic implementation but at least I provided a JVM compiler.  Actually code generator from the AST to JVM byte code.


Figure 1 : Mini adder language input (6 tokens are visible)
  The language program in the snippet above consists of a SYMBOL name token, an assignment token, NUMBER value the PLUS token and another NUMBER token.  The result of the add operation is stored in  global memory.  


2. Lexical Analysis


  The lexical analysis consists of reading the character tokens from the input stream and then converting those   ASCII characters into tokens that are used by our language.
Figure 2: Source code for lexer method, convert input ASCII characters into our language token types

  If you look at the code snippet above, the lexer method mostly consists of a large case statement that checks for a particular character and then creates a wrapper token object for that character. Once the token object is created, we add start to add the token node to the abstract syntax tree.

3. Lexer and Simple Parser with ANTLR


The parser example code uses only the Java standard libraries.   Most developers that write domain specific languages or other programming languages may use a parser generator.  ANTLR is a parser generator system written in Java that can output parser code in Java programming language or Python.  You provide a grammar and ANTLR generates the code that you can use for the lexer and parser.  In our case, are going to create a simple grammar and then two classes are created, the lexer and parser.

When then feed the input tokens to our ANTLR code generated code.





4. Parser Implementation and Abstract Syntax Tree (AST)


  The parser implementation converts and analyzes the tokens and coverts the tokens to an abstract syntax tree.  Once we build the AST, then we can traverse the tree and perform operations at each node.

Figure 3.1 : Lookahead parsing (LL(2)) and look for match errors

  We used look ahead two parsing.   Match method.

Figure 3.2 : Output from Abstract Syntax Tree
Figure 3:  Building the AST



4.1 Mini Language Functionality: Adding, Global Memory, Printing

Figure 4:  Visitor implementation, visit the AST expression nodes.  Perform 'add' operation

5. Java Bytecode


  The Java bytecode consists of  the magic number CAFEBABE.  After that comes the constant pool data.  After the constant pool data comes the data buffer which consists of the code block.


5.1 Java Tools : Javap

Figure 5 : Output from Javap Disassemble/Decompile on a Java Class

5.2 The Constant Pool


  The constant pool is a collection of constants that are referenced by ID in the data buffer or code section.


5.3 The Data Buffer and Code Section Attributes

The data buffer code section contains the code.

5.4 Analyzing the OpenJDK Java Source


Figure 6 : OpenJDK Java Source ClassWriter.java, writes Java bytecode to file/stream




6. Mini Compiler Implementation (writing to JVM bytecode)


  When thinking about the Java programming language, think of it as a wrapper for generating Java bytecode.  You don't necessarily need a mainstream programming language.  You do need to format the bytecode input into a class file and feed that into the Java virtual machine.


Figure 7 : Mini adder compiler, adding constants to constant pool. Matches Javap output (see comments)




7. Conclusion


This document covers the implementation of a compiler, a very basic compiler for the JVM.  We looked at the lexer, the parser, the AST, JVM bytecode and compiler.
A. Resources
B. Source Code
https://github.com/berlinbrown/ImperativeStaticCompiledLangOneFile - Github Source, see CompiledLangOneFile.java)

Also see:
http://math-services.appspot.com/lang2.jsp

C. Building the OpenJDK Java Compiler


D. Tools


http://www.antlr.org/


E. Disclaimer


For this document, I included snapshot images of the source instead of the actual source because I plan on converting this document to other formats.  I wanted to keep some of the syntax highlighting from my IDE.

-- Berlin Brown on 9/22/2011

Comments

Post a Comment

Popular posts from this blog

On Unit Testing, Java TDD for developers to write

It has been a while, let's kick off 2017 with a blog entry. I have read and I am reading about four or five posts a day about unit testing. It really has been a long time obsession for me. I have moved past the technical and practical considerations on unit testing frameworks and done with the debates with "should you use Junit or Mockito or Karma?" I am more interested in the psychology of unit testing, who does it, likes it, hates it? It really is one of those easy to learn, hard to master concepts. For example, many many may play chess when they are young and can end up being horribly chess players most of their life, I am part of that majority. Unfortunately, I have never played chess and sat down for hours and tried to master it. I never see the common patterns or have a developed end game. I mostly just play with a knowledge of the basic rules. Following good unit testing practices within your software development shop is a lot like playing chess. It is easy to le...
Read more

Is Java the new COBOL? Yes. What does that mean, exactly? (Part 1)

Image
"If you want to know the past, look at your present. If you want to know the future, look at your present." -- Gautama Buddha Java is the new COBOL, whaaaat?     If you are software developer that mainly writes applications for the web; even if you aren't a Java/J2EE developer, you have probably heard the new meme circulating the web and blogosphere. "Java is the new COBOL" . Most blogs and technical writers regurgitate that statement and follow-up by saying that EJBs suck, and some companies are considering Ruby on Rails. I didn't really think much of these posts. I get the impression that a lot of these "managers" don't write any Java or COBOL code. They are really not highlighting the seriousness of the problem. COBOL development has remained stagnant for decades. Java may see the same problem in the future. The Pentagon/DOD has a trillion dollar COBOL problem because it is so difficult to change their ancient infrastructure. Anyon...
Read more

JVM Notebook: Basic Clojure, Java and JVM Language performance

Image
"Measure, don't guess. The primary goal of all performance tuning exercises should be maximize the end user experience given the resource constraints." [1] "It isn't so much a "farewell to the J" as an expansion of the platform opportunities Java provides. Sun's investment to power ongoing development of JRuby and Jython broadens the range and reach of Java, as a whole." -- Rick Ross Overview and JVM Languages    One of the exciting trends to recently emerge from the Java community is the concept of the JVM language. These technologies are all that you would expect them to be. They are implementations of languages that run on the Java Virtual Machine. Some are newly created and some are based on existing, more mature languages. JRuby, Jython are two JVM languages based on CRuby and CPython. Groovy, Scala, Clojure are three completely new JVM languages that were created to add new language features that weren't supported by the core Ja...
Read more