Interpret Assembleru
Program dostane kod v "assembleru" (netusim, nakolik se podoba skutecnemu assembleru, protoze jsem v nem nikdy nepsal) a ma ho provest. Kazdy radek kodu obsahuje jeden prikaz (a jeho parametry) navzajem oddelene libovolnym poctem mezer. Jako parametry dostane program nazev vstupniho souboru, pocet registru a velikost pameti. Tezistem ulohy je nacteni kodu do rozumne struktury a jeho spravne provadeni, ne nacitani vstupu a podobnych prkotin, takze je mozne vlozit vstupni argumenty, pripadne vstup, primo do kodu. Registry a pamet jsou proste misto na kupu integeru, "velikost pameti" je pocet cisel v ni, stejne jako u poctu registru.
Prikazy:
MOV kam co/odkud -- presune co/odkud kam
ADD kcemu co -- pricte co kcemu a da do kcemu
SUB odceho co -- odecte co odceho a da do odceho
DIV co cim -- celociselne vydeli co cim a da do co
MOD co cim -- da do co zbytek po deleni co cim
MUL co cim -- vynasobi co cim a da do co
NEG co -- da do co nulu, pokud je co rovne nule, jinak jednicku
PRINT co -- vytiskne co na konzoli
SEQ ridici_registr az_po -- sekvence (viz nize)
ENDSEQ -- konec sekvence
PAR ridici_registr az_po -- paralelni sekvence (viz nize)
ENDPAR -- konec paralelni sekvence
Promenne:
kam, co, odkud, cim, az_po mohou byt celociselne konstanty, adresy registru, adresy v pameti
kam, co mohou byt adresy registru, adresy v pameti
Typy promennych (format):
celociselna konstanta: 0, 42, -4
adresa registru: r0, r13
adresa v pameti: [0], [r0]
Sekvence:
0. i := 0, vysledek := 0
1. ridici_registr := i
2. provede sekvenci prikazu az do odpovidajiciho konce sekvence (vcetne vnorenych sekvenci atd.)
3. if (ridici_registr != 0) { vysledek := 1 }
4. i++
5. if (i > az_po) { goto 6. } else { goto 1. }
6. ridici_registr := vysledek, KONEC
Paralelni sekvence:
Podobna sekvenci, ale sekvence prikazu se provadi paralelne pro vsechny hodnoty ridici promenne (pro i od 0 do az_po vcetne se spusti samostatna vlakna). Kazdy paralelni beh ma vlastni kopii registru (tzn. po dobehnuti vsech paralelnich behu bude hodnota vsech registru krome ridiciho stejna jako pred probehnutim).
----------------------
Reseni:
Kód: Vybrat vše
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;
namespace AssemblerParser
{
class MyException : ApplicationException
{
protected string message;
public new string Message { get { return this.message; } }
public MyException(string s) : base()
{
this.message = s;
}
}
enum AssemblerKeyword { END, MOV, ADD, SUB, DIV, MOD, MUL, NEG, PRINT, SEQ, PAR };
class AssemblerCommand
{
public readonly AssemblerKeyword keyword;
public AssemblerCommand(string keyword)
{
if (keyword == "MOV")
{
this.keyword = AssemblerKeyword.MOV;
}
else if (keyword == "ADD")
{
this.keyword = AssemblerKeyword.ADD;
}
else if (keyword == "SUB")
{
this.keyword = AssemblerKeyword.SUB;
}
else if (keyword == "DIV")
{
this.keyword = AssemblerKeyword.DIV;
}
else if (keyword == "MOD")
{
this.keyword = AssemblerKeyword.MOD;
}
else if (keyword == "MUL")
{
this.keyword = AssemblerKeyword.MUL;
}
else if (keyword == "NEG")
{
this.keyword = AssemblerKeyword.NEG;
}
else if (keyword == "PRINT")
{
this.keyword = AssemblerKeyword.PRINT;
}
else if (keyword == "SEQ")
{
this.keyword = AssemblerKeyword.SEQ;
}
else if (keyword == "ENDSEQ")
{
this.keyword = AssemblerKeyword.END;
}
else if (keyword == "PAR")
{
this.keyword = AssemblerKeyword.PAR;
}
else if (keyword == "ENDPAR")
{
this.keyword = AssemblerKeyword.END;
}
}
}
enum ParamType { Constant, Register, Index, RegisterIndex };
class Param
{
public readonly ParamType type;
public readonly int value;
public Param(string s)
{
bool typeAssigned = false;
if (s[0] == '[')
{
this.type = ParamType.Index;
typeAssigned = true;
s = s.Substring(1, s.Length - 2);
}
if (s[0] == 'r')
{
this.type = typeAssigned ? ParamType.RegisterIndex : ParamType.Register;
s = s.Substring(1);
}
this.value = Int32.Parse(s);
}
public override string ToString()
{
switch (this.type)
{
case ParamType.RegisterIndex:
return "[r" + this.value + "]";
case ParamType.Index:
return "[" + this.value + "]";
case ParamType.Register:
return "r" + this.value;
default:
return this.value.ToString();
}
}
}
class AssemblerLine
{
public readonly AssemblerCommand command;
public AssemblerKeyword Keyword { get { return this.command.keyword; } }
public readonly Param param1;
public readonly Param param2;
public AssemblerCode code;
public bool IsSequence { get { return (this.Keyword == AssemblerKeyword.SEQ) || (this.Keyword == AssemblerKeyword.PAR); } }
public AssemblerLine(string line)
{
string[] words = line.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
this.command = new AssemblerCommand(words[0]);
switch (this.Keyword)
{
case AssemblerKeyword.MOV:
case AssemblerKeyword.ADD:
case AssemblerKeyword.SUB:
case AssemblerKeyword.DIV:
case AssemblerKeyword.MOD:
case AssemblerKeyword.MUL:
case AssemblerKeyword.SEQ:
case AssemblerKeyword.PAR:
this.param1 = new Param(words[1]);
this.param2 = new Param(words[2]);
break;
case AssemblerKeyword.NEG:
case AssemblerKeyword.PRINT:
this.param1 = new Param(words[1]);
break;
default:
break;
}
}
public override string ToString()
{
switch (this.Keyword)
{
case AssemblerKeyword.MOV:
case AssemblerKeyword.ADD:
case AssemblerKeyword.SUB:
case AssemblerKeyword.DIV:
case AssemblerKeyword.MOD:
case AssemblerKeyword.MUL:
case AssemblerKeyword.SEQ:
case AssemblerKeyword.PAR:
return this.Keyword.ToString() + " " + this.param1.ToString() + " " + this.param2.ToString();
case AssemblerKeyword.NEG:
case AssemblerKeyword.PRINT:
return this.Keyword.ToString() + " " + this.param1.ToString();
default:
return "";
}
}
}
class AssemblerCode
{
public readonly List<AssemblerLine> code;
protected AssemblerCode()
{
this.code = new List<AssemblerLine>();
}
public static AssemblerCode FromReader(TextReader r)
{
AssemblerCode ret = new AssemblerCode();
string line;
while ((line = r.ReadLine()) != null)
{
AssemblerLine codeLine = new AssemblerLine(line);
if (codeLine.IsSequence)
{
codeLine.code = AssemblerCode.FromReader(r);
}
if (codeLine.Keyword == AssemblerKeyword.END)
{
break;
}
ret.code.Add(codeLine);
}
return ret;
}
public override string ToString()
{
StringBuilder builder = new StringBuilder();
foreach (AssemblerLine line in this.code)
{
builder.AppendLine(line.ToString());
if (line.IsSequence)
{
builder.Append(line.code.ToString());
builder.AppendLine("END");
}
}
return builder.ToString();
}
}
enum LocationType { Register, MemorySlot };
class Location
{
public readonly LocationType type;
public readonly int index;
public Location(LocationType type, int index)
{
this.type = type;
this.index = index;
}
}
class Assembler
{
protected int[] registers;
protected int[] memory;
public Assembler(int registerCount, int[] memory)
{
this.registers = new int[registerCount];
this.memory = memory;
}
public Assembler(Assembler parent)
{
this.registers = new int[parent.registers.Length];
this.memory = parent.memory;
Array.Copy(parent.registers, this.registers, this.registers.Length);
}
protected int GetValue(Param param)
{
if (param.type == ParamType.Constant)
{
return param.value;
}
return this.GetValue(this.GetLocation(param));
/*
switch (param.type)
{
case ParamType.RegisterIndex:
return this.memory[this.registers[param.value]];
case ParamType.Register:
return this.registers[param.value];
case ParamType.Index:
return this.memory[param.value];
default:
return param.value;
}
*/
}
protected int GetValue(Location location)
{
switch (location.type)
{
case LocationType.Register:
return this.registers[location.index];
default:
return this.memory[location.index];
}
}
protected Location GetLocation(Param param)
{
switch (param.type)
{
case ParamType.RegisterIndex:
return new Location(LocationType.MemorySlot, this.registers[param.value]);
case ParamType.Register:
return new Location(LocationType.Register, param.value);
case ParamType.Index:
return new Location(LocationType.MemorySlot, param.value);
default:
return null;
}
}
protected void Set(Location location, int value)
{
switch (location.type)
{
case LocationType.MemorySlot:
this.SetMemory(location.index, value);
break;
case LocationType.Register:
this.SetRegister(location.index, value);
break;
}
}
protected void SetRegister(int index, int value)
{
if (index >= this.registers.Length)
{
throw new MyException("Index out of bounds (registers). Try adding more registers.");
}
this.registers[index] = value;
}
protected void SetMemory(int index, int value)
{
if (index >= this.memory.Length)
{
throw new MyException("Index out of bounds (memory). Try adding more memory.");
}
this.memory[index] = value;
}
public bool Eval(AssemblerCode code)
{
return this.Eval(code, null);
}
public bool Eval(AssemblerCode code, Location watchedIndex)
{
foreach (AssemblerLine line in code.code)
{
switch (line.Keyword)
{
case AssemblerKeyword.MOV:
this.Set(this.GetLocation(line.param1), this.GetValue(line.param2));
break;
case AssemblerKeyword.ADD:
this.Set(this.GetLocation(line.param1), this.GetValue(line.param1) + this.GetValue(line.param2));
break;
case AssemblerKeyword.SUB:
this.Set(this.GetLocation(line.param1), this.GetValue(line.param1) - this.GetValue(line.param2));
break;
case AssemblerKeyword.DIV:
this.Set(this.GetLocation(line.param1), this.GetValue(line.param1) / this.GetValue(line.param2));
break;
case AssemblerKeyword.MOD:
this.Set(this.GetLocation(line.param1), this.GetValue(line.param1) % this.GetValue(line.param2));
break;
case AssemblerKeyword.MUL:
this.Set(this.GetLocation(line.param1), this.GetValue(line.param1) * this.GetValue(line.param2));
break;
case AssemblerKeyword.SEQ:
bool alwaysZero = true;
for (int i = 0; i <= this.GetValue(line.param2); ++i)
{
this.Set(this.GetLocation(line.param1), i);
this.Eval(line.code);
if (this.GetValue(line.param1) != 0)
{
alwaysZero = false;
}
}
this.Set(this.GetLocation(line.param1), alwaysZero ? 0 : 1);
break;
case AssemblerKeyword.PAR:
int param2 = this.GetValue(line.param2);
int retVal = 0;
if (param2 >= 0)
{
int iterations = param2 + 1;
Thread[] threads = new Thread[iterations];
AssemblerWorker[] workers = new AssemblerWorker[iterations];
for (int i = 0; i < iterations; ++i)
{
this.Set(this.GetLocation(line.param1), i);
Assembler assembler = new Assembler(this);
workers[i] = new AssemblerWorker(assembler, line.code, this.GetLocation(line.param1));
threads[i] = new Thread(workers[i].Start);
threads[i].Start();
}
foreach (Thread thread in threads)
{
thread.Join();
}
foreach (AssemblerWorker worker in workers)
{
if (worker.errorMessage != null)
{
throw new MyException(worker.errorMessage);
}
if (worker.result)
{
retVal = 1;
}
}
}
this.Set(this.GetLocation(line.param1), retVal);
break;
case AssemblerKeyword.NEG:
this.Set(this.GetLocation(line.param1), (this.GetValue(line.param1) == 0) ? 1 : 0);
break;
case AssemblerKeyword.PRINT:
Console.WriteLine(this.GetValue(line.param1));
break;
default:
break;
}
}
bool ret = false;
if (watchedIndex != null)
{
if (this.GetValue(watchedIndex) != 0)
{
ret = true;
}
}
return ret;
}
}
class AssemblerWorker
{
protected Assembler assembler;
protected AssemblerCode code;
protected Location watchedRegister;
public bool finished;
public string errorMessage;
public bool result;
public AssemblerWorker(Assembler assembler, AssemblerCode code, Location watchedRegister)
{
this.assembler = assembler;
this.code = code;
this.watchedRegister = watchedRegister;
this.finished = false;
this.errorMessage = null;
}
public void Start()
{
try
{
this.result = this.assembler.Eval(this.code, watchedRegister);
}
catch (MyException e)
{
this.errorMessage = e.Message;
}
this.finished = true;
}
}
class Program
{
static void Main(string[] args)
{
string inputFilePath = "in8.txt";
int registerCount = 20;
int memorySize = 1000;
TextReader r = new StreamReader(inputFilePath);
AssemblerCode code = AssemblerCode.FromReader(r);
r.Close();
int[] memory = new int[memorySize];
Assembler assembler = new Assembler(registerCount, memory);
try
{
assembler.Eval(code);
}
catch (MyException e)
{
Console.WriteLine(e.Message);
}
//Console.WriteLine(code.ToString());
Console.ReadLine();
}
}
}
-------------------------
Testovaci vstupy:
1) vystup: cisla od 0 do 100 a jednicka
Kód: Vybrat vše
SEQ r0 100
PRINT r0
ENDSEQ
PRINT r0
2) vystup: cisla od 0 do 100 a nula
Kód: Vybrat vše
SEQ r0 100
PRINT r0
MOV r0 0
ENDSEQ
PRINT r0
3) vystup: cisla od 0 do 100 v nahodnem poradi a jednicka
Kód: Vybrat vše
PAR r0 100
PRINT r0
ENDPAR
PRINT r0
4) vystup: cisla od 0 do 100 v nahodnem poradi a nula
Kód: Vybrat vše
PAR r0 100
PRINT r0
MOV r0 0
ENDPAR
PRINT r0
5) vystup: nasobky sedmi od 0 do 700
Kód: Vybrat vše
MOV r1 7
PAR r0 100
MOV [r0] r0
MUL [r0] r1
ENDPAR
SEQ r0 100
PRINT [r0]
ENDSEQ
6) vystup: 1
Kód: Vybrat vše
MOV r1 121
PAR r0 r1
MUL r0 r0
SUB r0 r1
NEG r0
ENDPAR
PRINT r0
7) vystup: 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55
Kód: Vybrat vše
PAR r0 10
MOV [r0] 0
SEQ r1 r0
ADD [r0] r1
ENDSEQ
ENDPAR
SEQ r0 10
PRINT [r0]
ENDSEQ
8) vystup: dvojice cisel (x
i, y
i) pro i od 0 do 20, kde x
i == i a y
i ma hodnotu 0 pokud x
i neni prvocislo a 1, pokud je
Kód: Vybrat vše
PAR r0 20
MOV r2 r0
SUB r2 3
PAR r1 r2
ADD r1 2
ADD r2 3
MOD r2 r1
MOV r1 r2
NEG r1
ENDPAR
MOV [r0] r1
NEG [r0]
ENDPAR
SEQ r0 20
PRINT r0
PRINT [r0]
ENDSEQ