This is the seventh part of the YAUL series. For your convenience you can find other parts in the table of contents in Part 1 — Introduction

Last time we implemented conditional expression. Today we are going to implement another basic imperative concept — loop.

Table of Contents

Introduction

We are going to handle while loop. We will also handle common keywords allowing to control execution: break, continue, and goto.

Parser

As usual, we start with parser. First, loop:

def p_while(p):
    """while : WHILE '(' cond_expr ')' block_or_statement"""
    p[0] = Compiler.WhileLoop()
    p[0].Condition = p[3]
    p[0].Body = p[5]

def p_while(p):

"""while : WHILE '(' cond_expr ')' block_or_statement"""

p[0] = Compiler.WhileLoop()

p[0].Condition = p[3]

p[0].Body = p[5]

Looks almost the same as if code. We simply check condition and execute block of code. Let’s see what is exactly the block_or_statement:

def p_block_or_statement_block(p):
    """block_or_statement : block"""
    p[0] = p[1]

def p_block_or_statement_statement(p):
    """block_or_statement : statement"""
    p[0] = p[1]

def p_block_empty(p):
    """block : '{' '}' """
    p[0] = Compiler.StatementBlock()
    p[0].Statements = System.Collections.Generic.List[Compiler.IStatement]([])

def p_block_not_empty(p):
    """block : '{' list_statement '}' """
    p[0] = Compiler.StatementBlock()
    p[0].Statements = System.Collections.Generic.List[Compiler.IStatement](p[2])

def p_list_statement_first(p):
    """list_statement : statement"""
    p[0] = [p[1]]
    

def p_list_statement_next(p):
    """list_statement : list_statement statement"""
    p[0] = p[1]
    p[0].append(p[2])
    

def p_statement(p):
    """statement : setvar
                 | setarrayelem
                 | if_else
                 | while
                 | proc_call
                 | return
                 | break
                 | continue
                 | print 
                 | jump
                 | label """
    p[0] = p[1]

def p_block_or_statement_block(p):

"""block_or_statement : block"""

p[0] = p[1]

def p_block_or_statement_statement(p):

"""block_or_statement : statement"""

p[0] = p[1]

def p_block_empty(p):

"""block : '{' '}' """

p[0] = Compiler.StatementBlock()

p[0].Statements = System.Collections.Generic.List[Compiler.IStatement]([])

def p_block_not_empty(p):

"""block : '{' list_statement '}' """

p[0] = Compiler.StatementBlock()

p[0].Statements = System.Collections.Generic.List[Compiler.IStatement](p[2])

def p_list_statement_first(p):

"""list_statement : statement"""

p[0] = [p[1]]

def p_list_statement_next(p):

"""list_statement : list_statement statement"""

p[0] = p[1]

p[0].append(p[2])

def p_statement(p):

"""statement : setvar

| setarrayelem

| if_else

| while

| proc_call

| return

| break

| continue

| print

| jump

| label """

p[0] = p[1]

The code should be obvious. We simply handle list of statements, where each statement is one of language’s instructions. Let’s now handle keywords for controlling loop:

def p_break(p):
    """break : BREAK ';' """
    p[0] = Compiler.Break()

def p_continue(p):
    """continue : CONTINUE ';' """
    p[0] = Compiler.Continue()

def p_break(p):

"""break : BREAK ';' """

p[0] = Compiler.Break()

def p_continue(p):

"""continue : CONTINUE ';' """

p[0] = Compiler.Continue()

Looks pretty easy, just a keyword with semicolon at the end. Let’s now see the labels and goto:

def t_LABEL(t):
    r'[a-zA-Z_][a-zA-Z0-9_]*!'
    t.value = t.value.strip('!')
    return t

def p_label(p):
    """ label : LABEL"""
    p[0] = Compiler.Label()
    p[0].Name = p[1]

def p_jump(p):
    """ jump : JUMP LABEL ';' """
    p[0] = Compiler.Jump()
    p[0].Target = Compiler.Label();
    p[0].Target.Name = p[2]

def t_LABEL(t):

r'[a-zA-Z_][a-zA-Z0-9_]*!'

t.value = t.value.strip('!')

return t

def p_label(p):

""" label : LABEL"""

p[0] = Compiler.Label()

p[0].Name = p[1]

def p_jump(p):

""" jump : JUMP LABEL ';' """

p[0] = Compiler.Jump()

p[0].Target = Compiler.Label();

p[0].Target.Name = p[2]

Once again, nothing special.

C#

Let’s dig into C# code. First, loop:

using System;
using System.Linq.Expressions;

namespace Compiler
{
    public class WhileLoop : IStatement
    {
        public IExpression Condition { get; set; }
        public StatementBlock Body { get; set; }

        public WhileLoop()
        {
            Body = new StatementBlock();
        }

        public Expression Accept(IVisitor visitor)
        {
            LabelTarget breakLabel = Expression.Label();
            LabelTarget continueLabel = Expression.Label();
            Expression breakExpression = Expression.Break(breakLabel);
            Expression continueExpression = Expression.Continue(continueLabel);

            visitor.BreakExpressions.Add(breakExpression);
            visitor.ContinueExpressions.Add(continueExpression);

            var result = Expression.Loop(
                Expression.IfThenElse(
                    Condition.Accept(visitor), 
                    Expression.Block(
                        Body.Accept(visitor),
                        continueExpression
                    ),
                    breakExpression
                ), 
                breakLabel, 
                continueLabel);


            visitor.BreakExpressions.Remove(breakExpression);
            visitor.ContinueExpressions.Remove(continueExpression);

            return result;
        }

        public void FindLabels(IVisitor visitor)
        {
            Body.FindLabels(visitor);
        }
    }
}

using System;

using System.Linq.Expressions;

namespace Compiler

{

public class WhileLoop : IStatement

{

public IExpression Condition { get; set; }

public StatementBlock Body { get; set; }

public WhileLoop()

{

Body = new StatementBlock();

}

public Expression Accept(IVisitor visitor)

{

LabelTarget breakLabel = Expression.Label();

LabelTarget continueLabel = Expression.Label();

Expression breakExpression = Expression.Break(breakLabel);

Expression continueExpression = Expression.Continue(continueLabel);

visitor.BreakExpressions.Add(breakExpression);

visitor.ContinueExpressions.Add(continueExpression);

var result = Expression.Loop(

Expression.IfThenElse(

Condition.Accept(visitor),

Expression.Block(

Body.Accept(visitor),

continueExpression

breakExpression

breakLabel,

continueLabel);

visitor.BreakExpressions.Remove(breakExpression);

visitor.ContinueExpressions.Remove(continueExpression);

return result;

}

public void FindLabels(IVisitor visitor)

{

Body.FindLabels(visitor);

}

First, before visiting the body we create instructions for break and continue instructions. We add them to visitor, so it knows which instructions use to control the loop. Next, we create a loop — it consists of expression for checking condition, expression for loop’s block, and expressions for controlling the loop. Check MSDN for more details. We also need to handle labels in loop’s body.

Let’s now see blocks of code:

using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;

namespace Compiler
{
    public class StatementBlock : ISemanticObject
    {
        public List< IStatement> Statements { get; set; }
        
        public Expression Accept(IVisitor visitor)
        {
            FindLabels(visitor);
            var generatedStatements = GenerateContent(visitor);
            
            if (generatedStatements.Count > 0)
            {
                return Expression.Block(generatedStatements);
            }

            return Expression.Empty();
        }

        private IList< Expression> GenerateContent(IVisitor visitor)
        {
            return Statements.Select(statement => statement.Accept(visitor)).Where(statement => statement != null).ToList();
        }

        public void FindLabels(IVisitor visitor)
        {
            foreach (var each in Statements)
            {
                each.FindLabels(visitor);
            }
        }
    }
}

using System.Collections.Generic;

using System.Linq;

using System.Linq.Expressions;

namespace Compiler

{

public class StatementBlock : ISemanticObject

{

public List< IStatement> Statements { get; set; }

public Expression Accept(IVisitor visitor)

{

FindLabels(visitor);

var generatedStatements = GenerateContent(visitor);

if (generatedStatements.Count > 0)

{

return Expression.Block(generatedStatements);

}

return Expression.Empty();

}

private IList< Expression> GenerateContent(IVisitor visitor)

{

return Statements.Select(statement => statement.Accept(visitor)).Where(statement => statement != null).ToList();

}

public void FindLabels(IVisitor visitor)

{

foreach (var each in Statements)

{

each.FindLabels(visitor);

}

No magic here. We simply iterate over statements and collect them into one block. Statement is:

namespace Compiler
{
    public interface IStatement : ISemanticObject
    {
        
    }
}

namespace Compiler

{

public interface IStatement : ISemanticObject

{

}

Well, it is very simple. Statements are just particular instructions and they are handled somewhere else, in implementations.

OK, let’s now see control keywords:

using System;
using System.Linq;
using System.Linq.Expressions;

namespace Compiler
{
    public class Break : IStatement
    {
        public Expression Accept(IVisitor visitor)
        {
            if (visitor.BreakExpressions.Count == 0)
            {
                throw new InvalidOperationException("Cannot break - must be inside loop");
            }

            return visitor.BreakExpressions.Last();
        }

        public void FindLabels(IVisitor visitor)
        {
        }
    }
}

using System;

using System.Linq;

using System.Linq.Expressions;

namespace Compiler

{

public class Break : IStatement

{

public Expression Accept(IVisitor visitor)

{

if (visitor.BreakExpressions.Count == 0)

{

throw new InvalidOperationException("Cannot break - must be inside loop");

}

return visitor.BreakExpressions.Last();

}

public void FindLabels(IVisitor visitor)

{

}

using System;
using System.Linq;
using System.Linq.Expressions;

namespace Compiler
{
    public class Continue : IStatement
    {
        public Expression Accept(IVisitor visitor)
        {
            if (visitor.ContinueExpressions.Count == 0)
            {
                throw new InvalidOperationException("Cannot continue - must be inside loop");
            }

            return visitor.ContinueExpressions.Last();
        }

        public void FindLabels(IVisitor visitor)
        {
        }
    }
}

using System;

using System.Linq;

using System.Linq.Expressions;

namespace Compiler

{

public class Continue : IStatement

{

public Expression Accept(IVisitor visitor)

{

if (visitor.ContinueExpressions.Count == 0)

{

throw new InvalidOperationException("Cannot continue - must be inside loop");

}

return visitor.ContinueExpressions.Last();

}

public void FindLabels(IVisitor visitor)

{

}

We simply extract most recent instructions from visitor or throw exceptions if they do not exist.

And now the last part, gotos:

using System.Linq.Expressions;

namespace Compiler
{
    public class Label : IStatement
    {
        public string Name { get; set; }
        public LabelTarget Target { get; set; }

        public Expression Accept(IVisitor visitor)
        {
            return Expression.Label(Target);
        }

        public void FindLabels(IVisitor visitor)
        {
            Target = Expression.Label(Name);
            visitor.Labels.Add(Target);
        }
    }
}

using System.Linq.Expressions;

namespace Compiler

{

public class Label : IStatement

{

public string Name { get; set; }

public LabelTarget Target { get; set; }

public Expression Accept(IVisitor visitor)

{

return Expression.Label(Target);

}

public void FindLabels(IVisitor visitor)

{

Target = Expression.Label(Name);

visitor.Labels.Add(Target);

}

using System.Linq;
using System.Linq.Expressions;

namespace Compiler
{
    public class Jump : IStatement
    {
        public Label Target { get; set; }

        public Expression Accept(IVisitor visitor)
        {
            return Expression.Goto(visitor.Labels.First(label => label.Name == Target.Name));
        }

        public void FindLabels(IVisitor visitor)
        {
        }
    }
}

using System.Linq;

using System.Linq.Expressions;

namespace Compiler

{

public class Jump : IStatement

{

public Label Target { get; set; }

public Expression Accept(IVisitor visitor)

{

return Expression.Goto(visitor.Labels.First(label => label.Name == Target.Name));

}

public void FindLabels(IVisitor visitor)

{

}

Since LINQ handles labels and jumps, this is pretty straightforward. We simply create label, store it in visitor, and jump to it.

Summary

We are now able to handle loops. Next time we will handle another big thing: functions.