Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

A Simple Compiler for the Common Language Runtime

, 11 May 2003
An end-to-end example of a bottom up LALR(1) compiler for a fictitious language targeting the Common Language Runtime
compiler_demo.zip
Bubble Sort
Bubble Sort.shp
Config.dck
mike.exe
Sort.exe
Sort.pdb
Sort.sh
compiler_src.zip
Core
App.ico
bin
Core.csproj.user
Core.suo
Magic IDE
App.ico
bin
Debug
Config.dck
Images.bmp
Sharp.cgt
ICSharpCode.TextEditor.dll
Magic IDE.csproj.user
Magic IDE.suo
MagicLibrary.DLL
UtilityLibrary.dll
/*
Sharp Compiler
Copyright (C) 2003  Michael Bebenita

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/
using System;
using System.Collections;

namespace Core.Compilation
{
	public enum SymbolType
	{
		None,
		Function,
		Structure,
		Variable
	}

	public class Symbol
	{
		public string Name;
		public SymbolType Type = SymbolType.None;
		public object SyntaxObject;
		public object CodeObject;

		public Symbol(string name, SymbolType type, object syntaxObject, object codeObject)
		{
			Name = name;	Type = type;	SyntaxObject = syntaxObject;	CodeObject = codeObject;
		}
	}

	public class SymbolTable
	{
		private SymbolTable m_Parent = null;
		private Hashtable m_Hashtable = new Hashtable();

		public SymbolTable()
		{

		}

		public SymbolTable(SymbolTable parent)
		{
			m_Parent = parent;
		}

		public Symbol Add(Variable variable)
		{
			return Add(variable.Name,SymbolType.Variable,variable,null);
		}

		public Symbol Add(Function function)
		{
			return Add(function.Name,SymbolType.Function,function,null);
		}

		public Symbol Add(Structure structure)
		{
			return Add(structure.Name,SymbolType.Structure,structure,null);
		}

		public Symbol Add(string name,SymbolType type, object syntaxObject, object codeObject)
		{
			string prefix = PrefixFromType(type);

			if(m_Hashtable.Contains(prefix + name))
				throw new SymbolException("Symbol already exists in symbol table.");

			Symbol symbol = new Symbol(name,type,syntaxObject,codeObject);
			m_Hashtable.Add(prefix + name,symbol);

			return symbol;
		}

		public bool Contains(string name, SymbolType type)
		{
			return Find(name,type) != null;
		}

		public Symbol Find(string name, SymbolType type)
		{
			string prefix = PrefixFromType(type);

			if(m_Hashtable.Contains(prefix + name))
				return (Symbol)m_Hashtable[prefix + name];
			else if(m_Parent != null)
			{
				return m_Parent.Find(name,type);
			}
			else
				return null;
		}

		private string PrefixFromType(SymbolType type)
		{
			if(type == SymbolType.Function)
				return "f_";
			else if(type == SymbolType.Structure)
				return "s_";
			else if(type == SymbolType.Variable)
				return "v_";
			return "";
		}		
	}

	public delegate void VerifierEventHandler(string message);

	public class Verifier
	{
		public event VerifierEventHandler Error;

		private Module m_Module = null;

		public Verifier(Module module)
		{
			m_Module = module;

			//
			// Build symbol tables.
			//

			//m_Module.Body.SymbolTable = new SymbolTable();
			//BuildSymbolTable(m_Module.Body.SymbolTable,m_Module.Body);

		}

		private void BuildSymbolTable(SymbolTable parent, Body body)
		{
			if(body.Structures != null)
				foreach(Structure structure in body.Structures)
					parent.Add(structure).SyntaxObject = structure;

			if(body.Functions != null)
			{
				foreach(Function function in body.Functions)
				{
					parent.Add(function).SyntaxObject = function;
					function.Body.SymbolTable = new SymbolTable();
					BuildSymbolTable(function.Body.SymbolTable,function.Body);
				}
			}

			if(body.Statements != null)
			{
				foreach(Statement statement in body.Statements)
				{
					if(statement is Variable)
						parent.Add(statement as Variable).SyntaxObject = statement;
				}
			}
		}

		public bool VerifyExpression(SymbolTable symbolTable, Expression expression)
		{
			//
			// Verify expression.
			//

			try
			{
				GetExpressionType(symbolTable,expression);
				return true;
			}
			catch(VerifierException x)
			{
				System.Diagnostics.Debug.WriteLine(x.Message);
				return false;
			}
		}

		public Type GetExpressionType(SymbolTable symbolTable, Expression expression)
		{
			if(expression is UnaryExpression)
			{
				UnaryExpression unary = (UnaryExpression)expression;
				return FindType(GetExpressionType(symbolTable,unary.Value),unary.UnaryOperatorType);
			}
			else if(expression is BinaryExpression)
			{
				BinaryExpression binary = (BinaryExpression)expression;
				return FindType(GetExpressionType(symbolTable,binary.Left),GetExpressionType(symbolTable,binary.Right),binary.BinaryOperatorType);
			}
			else if(expression is Literal)
			{
				Literal literal = expression as Literal;

				if(literal.LiteralType == LiteralType.Boolean)
					return new Type(PrimitiveType.Boolean);
				if(literal.LiteralType == LiteralType.Character)
					return new Type(PrimitiveType.Character);
				if(literal.LiteralType == LiteralType.Integer)
					return new Type(PrimitiveType.Integer);
				if(literal.LiteralType == LiteralType.Real)
					return new Type(PrimitiveType.Real);
				if(literal.LiteralType == LiteralType.String)
					return new Type(PrimitiveType.Void);
			}
			else if(expression is Name)
			{
				return ((Variable)symbolTable.Find(((Name)expression).Value,SymbolType.Variable).SyntaxObject).Type;
			}
			else if(expression is Call)
			{
				return ((Call)expression).Type;
			}
			return null;
		}

		public Type FindType(Type leftType, Type rightType, BinaryOperatorType operatorType)
		{
			//
			// Binary operations can only be performed on primitive types.
			//

			if((leftType.VariableType != VariableType.Primitive) || (rightType.VariableType != VariableType.Primitive))
				throw new VerifierException("Binary operations can only be performed on primitive types.");

			//
			// Boolean operations.
			//

			if(leftType.PrimitiveType == PrimitiveType.Boolean && rightType.PrimitiveType == PrimitiveType.Boolean)
			{
				switch(operatorType)
				{
					case BinaryOperatorType.And:
					case BinaryOperatorType.Or:
					case BinaryOperatorType.NotEqual:
						return new Type(PrimitiveType.Boolean);
						break;
					default:
						throw new VerifierException("Specified operator cannot be applied to boolean types.");
						break;
				}
			}

			//
			// Integer operations.
			//

			else if(leftType.PrimitiveType == PrimitiveType.Integer && rightType.PrimitiveType == PrimitiveType.Integer)
			{
				switch(operatorType)
				{
					case BinaryOperatorType.And:
					case BinaryOperatorType.Or:
						throw new VerifierException("Specified operator cannot be applied to integer types.");
						break;
					case BinaryOperatorType.GraterOrEqualTo:
					case BinaryOperatorType.GreaterThen:
					case BinaryOperatorType.LessOrEqualTo:
					case BinaryOperatorType.LessThen:
					case BinaryOperatorType.Equal:
					case BinaryOperatorType.NotEqual:
						return new Type(PrimitiveType.Boolean);
						break;
					default:
						return new Type(PrimitiveType.Integer);
				}
			}

			//
			// Real operations.
			//

			else if(leftType.PrimitiveType == PrimitiveType.Real && rightType.PrimitiveType == PrimitiveType.Real)
			{
				switch(operatorType)
				{
					case BinaryOperatorType.And:
					case BinaryOperatorType.Or:
						throw new VerifierException("Specified operator cannot be applied to real types.");
						break;
					default:
						return new Type(PrimitiveType.Real);
				}
			}

			//
			// Character operations.
			//

			else if(leftType.PrimitiveType == PrimitiveType.Character && rightType.PrimitiveType == PrimitiveType.Character)
			{
				switch(operatorType)
				{
					case BinaryOperatorType.And:
					case BinaryOperatorType.Or:
						throw new VerifierException("Specified operator cannot be applied to character types.");
						break;
					default:
						return new Type(PrimitiveType.Character);
				}
			}

			throw new VerifierException("Incompatible types for specified operation.");
		}

		public Type FindType(Type type, UnaryOperatorType operatorType)
		{
			switch(operatorType)
			{
				case UnaryOperatorType.Indexer:
					if(type.VariableType == VariableType.PrimitiveArray)
						return new Type(type.PrimitiveType);
					else if(type.VariableType == VariableType.StructureArray)
						return new Type(type.Name);
					else
						throw new VerifierException("The indexer operator cannot be applied to the specified type.");
					break;
				case UnaryOperatorType.Not:
					if(type.PrimitiveType == PrimitiveType.Boolean)
						return new Type(type.PrimitiveType);
					else
						throw new VerifierException("The NOT operator cannot be applied to the specified type.");
					break;
				default:
					if(type.VariableType == VariableType.Primitive)
						return new Type(type.PrimitiveType);
					else
						throw new VerifierException("The +/- operators cannot be applied to the specified type.");
					break;
			}
		}


		public bool VerifyBody(Body body)
		{
			//
			// Check variable declarations.
			//

			foreach(Statement statement in body.Statements)
			{
				if(statement is Variable)
				{
					Variable variable = (Variable)statement;
					if(variable.Value is Expression)
					{
						if(VerifyExpression(body.SymbolTable,(Expression)variable.Value))
							System.Diagnostics.Debug.WriteLine("Fuck yah");
						else
							System.Diagnostics.Debug.WriteLine("Fuck nahh");
					}
				}
			}

			return false;
		}

		


	}
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Michael Bebenita
Web Developer
United States United States
Currently a graduate student at UCI.

| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 12 May 2003
Article Copyright 2003 by Michael Bebenita
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid