March թեսթի իրականացումը Java լեզվով

Այս գրառումը կիսատ է թողնված հավես չունենալու
պատճառով։ Ցանկացողները կարող են շարունակել այն։
Կարծում եմ, որ, զարգացնելու դեպքում, կարող է լավ
կուրսային աշխատանք լինել։

Հիշող սարքերի ներդրված թեսթավորման տարածված եղանակներից մեկը March թեսթերի կիրառումն է։ Այս գրառման մեջ ես ուզում եմ պատմել հիշող սարքի մոդելի, անսարքության մոդելի, ինչպես նաև March թեսթի մոդելի իրականացման մասին։

Ընդհանուր առմամբ գաղափարը հետևյալն է․ a) սահմանել տրված չափերով հիշող սարք, b) նրանում ներմուծել որոշ տիպի անսարքություններ, c) կազմել March թեսթեր, d) գործարկել թեսթերը հիշող սարքի մոդելի վրա և գրանցել արդյունքները։

Նշված տիպի մոդելավորումն օգտագործվում է March թեսթերի մշակման համար։ Մոդելավորման օգնությամբ ստեղծվում են թեսթեր, որոնք պետք է հիշող սարքի վրա հայտնաբերեն թեսթավորողին հայտնի անսարքությունները։

Հիշող սարքը

Սովորական և անսարք բջջի մոդելը

Հիշող սարքը մեկ բիթ ինֆորմացիա պահող հիշող տարրերի՝ բջիջների մատրից է։ Այդ բջջի մոդելը ես իրականացրել եմ Cell դասով։ Այս Cell-ը սարքին բջջի մոդելն է։

package memory;

/**
 * Հիշող բջջի մոդելը
 */
class Cell {
    // տվյալ բջիջը պարունակող մատրիցը
    private Memory parent = null;
    // տողը և սյունը
    private int row = 0, column = 0;
    // բջջի արժեքը
    private char value = 'x';

    // կոնստրուկտորը
    public Cell(Memory p, int r, int c)
    {
        parent = p;
        row = r;
        column = c;
    }

    // վերադարձնում է արժեքը
    public char read()
    {
        return value;
    }

    // փոխում է արժեքը
    public void write(char v)
    {
        value = v;
    }
}

Այս դասի parent անդամը այն հիշող սարքի մոդելի հղում է, որը պարունակում է տվյալ բջիջը։ row և column ինդեքսները ցույց են տալիս, թե հիշող սարքի մատրիցի որ տողում և սյունում է տեղադրված բջիջը։ Այս երեք հատկությունները հնարավորություն են տալիս մոդելավորել այնպիսի անսարքություններ, որտեղ մի բջջի ոչ սարքին լինելը ազդում է մեկ այլ սարքին բջջի պարունակության վրա։

Հիշող բջջի հետ կապված անսարքությունները մոդելավորելու համար պետք է ընդլայնել Cell դասը։ Օրինակ, հաճախ են հանդիպում այնպիսի բջջիջներ, որոնց կարդալու գործողությունը վերադարձնում է հաստատուն 0 կամ 1 արժեքը։ Հաստատուն զրո վերադարձնող բջիջը կարելի է մոդելավորել, օրինակ, ConstZero դասով։

package memory;

/**
 * Մշտական '0' վերադարձնող անսարք բջիջ
 */
public class ConstZero extends Cell {
    public ConstZero(Memory p, int r, int c)
    {
        super(p, r, c);
    }

    @Override
    public char read()
    {
        return '0';
    }
}

Բջիջների մատրիցը

Հիշող սարքը, որը հիշող բջիջների մատրից է մոդելավորված է Memory դասով։ Այն պարունակում է տողերի ու սյուների քանակները ցույց տվող rows և columns անդամները, և Cell օբյեկտների matrix մատրիցը։

package memory;

/**
 * Հիշողղ սարքի մոդելը
 */
public class Memory {
    // տողերի քանակը
    public int rows = 0;
    // սյուների քանակը
    public int columns = 0;
    // բջիջների մատրիցը
    private Cell[][] matrix = null;

    // կոնստրուկտորը
    public Memory(int r, int c)
    {
        rows = r;
        columns = c;
        matrix = new Cell[rows][columns];

        for( int i = 0; i < rows; ++i )
            for( int j = 0; j < columns; ++j )
                matrix[i][j] = new Cell(this, i, j);
    }

    // անսարքություն մոդելավորելու համար
    // տրված դիրքում տեղադրել տրված բջիջը
    public void replaceCell(int r, int c, cell cl)
    {
        matrix[r][c] = cl;
    }

    // կարդալ, տրված է գծային հասցեն
    public char read(int addr)
    {
        return read(addr / rows, addr % rows);
    }
    // կարդալ, տրված է ֆիզիկական հասցեն
    private char read(int r, int c)
    {
        return matrix[r][c].read();
    }

    // գրել, տրված է գծային հասցեն
    public void write(int addr, char d)
    {
        write(addr / rows, addr % rows, d);
    }
    // գրել, տրված է ֆիզիկական հասցեն
    private void write(int r, int c, char d)
    {
        matrix[r][c].write(d);
    }

    // արտածել մատրիցի պարունակությունը
    public void Print()
    {
        for( int r = 0; r < rows; ++r ) {
            System.out.printf("%x: ");
            for( int c = 0; c < columns; ++c )
                System.out.print(read(r,c));
            System.out.println();
        }
        System.out.println();
    }
}

Կոնստրուկտորում matrix մատրիցը արժեքավորվում է «սարքին» բջիջներով։ Իսկ replaceCell մեթոդը հնարավորություն է տալիս մատրիցի տրված դիրքի բջիջը փոխարինել նոր տրվածով։ replaceCell մեթոդին տրվում են բջջի ֆիզիկական հասցեները՝ տողը և սյունը, քանի որ հաճախ հիշող սարքերում կիրառվում է ավելի բարդ հասցեավորում քան գծայինն է, և հարմար է անսարք բջիջը տեղադրել ըստ ֆիզիկական դիրքի։

Հիմա, օրինակ, կարող եմ ստեղծել 8 տողեր և 4 սյուներ ունեցող հիշող սարք և դրա երկրորդ տողի առաջին բջջում տեղադրել մի անսարք բջիջ։

Memory mem = new Memory(8, 4);
mem.replaceCell(1, 0, new ConstZero(mem, 1, 0));

Կամ, քանի որ Java լեզուն հնարավորություն է տալիս օբյեկտի ստեղծման ժամանակ վերասահմանել նրա մեթոդները, կարող եմ ConsOne տիպի անսարքություն մոդելավորել այսպես․

mem.replaceCell(1, 1, new Cell(mem, 1, 1) {
    @Override
    public byte read() { return '1'; }
});

March թեսթը

March թեսթը March ալգորիթմների շարք է, որոնք հաջորդաբար գործարկվում են հիշող սարքի մոդելի վրա և ստեղծում են թեսթավորման արդյունքներ։ Ալգորիթմն իր հերթին March էլեմենտների շարք է, իսկ այս վերջինն էլ March գործողությունների շարք է։

Ես դիտարկում եմ միայն պարզագույն March թեսթերը, որոնցում հանդիպում են միայն գրելու և կարդալու գործողություններ։ Եվ որպեսզի March թեսթը նկարագրելիս ավելի անսխալ լինեմ, բերեմ դրա EBNF քերականությունը։

MarchTest = { Algorithm }.
Algorithm = IDENT '{' Element { ';' Element } '}'.
  Element = ('=>' | '<=') '(' Operation { ',' Operation } ')'.
Operation = ('W' | 'R') ('0' | '1').

March գործողություն

Տվյալ կոնտեքստում կան երկու March գործողություններ․ բջջում տրված արժեքը գրողW (write) գործողությունը, և բջջից տրված սպասվող արժեքը կարդացող R (read) գործողությունը։

Ես ուզում եմ նշված երկու գործողությունները մոդելավարել Operation դասով։ Վերջինիս code անդամը գործողության տեսակն է՝ R կամ W, իսկ data անդամը՝ այն արժեքը, որը պետք է գրել բջջում, կամ պետք է սպասել բջջից կարդալիս։

package march;

import memory.*;

public class Operation {
    // գործողությունը
    private char code = 'X';
    // գրելու կամ կարդալու տվյալը
    private char data = '?';

    public Operation(char c, byte d)
    {
        code = c;
        data = d;
    }

March գործողությունը Memory օբյեկտի վրա գործարկելու համար սահմանեմ runOn մեթոդը, որը ստանում է թեսթավորվող հիշող սարքի հղումը և այն գծային հասցեն, որում գտնվող բջջի նկատմամբ կիրառվում է գործողությունը։

    public boolean runOn(Memory mem, int addr)
    {
        boolean status = true;

        if( opcode == 'W' )
            mem.write(addr, value);
        else if( opcode == 'R' )
            status = value == mem.read(addr);

        if( !status )
            System.out.printf("'%s' գործողությունը ձախողվեց %d հասցեի վրա։",
                              toString(), addr);

        return status;
    }

Եվ վերջապես, ToString մեթոդը, որը վերադարձնում է գործողության տեքստային տեսքը։

    @Override
    public String toString()
    {
        return Character.toString(opcode) + Character.toString(value);
    }
}

March էլեմենտ

March էլեմենտն ունի երկու բաղադրիչ․ a) հասցեների թվարկման ուղղությունը՝ որոշվող => և <= սիմվոլներով, և b) March գործողությունների շղթան։

package march;

import memory.*;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * March էլէմենտը
 */
public class Element {
    // հասցեները նվազում են
    public static final int DEC = -1;
    // հասցեներն աճում են
    public static final int INC = 1;

    // հասցեի թվարկման ուղղությունը
    private int direction = 0;
    // գործողությունների շարքը
    private List<Operation> operations = null;

    public Element(int dir, List<Operation> opers)
    {
        direction = dir;
        operations = new ArrayList<Operation>();
        operations.addAll(opers);
    }

March էլեմենտի գործարկումը հիշող սարքի մոդելի վրա կատարվում է runOn մեթոդով։ Քանի որ հասցեների թվարկման ուղղությունը կարող է լինել ինչպես աճող այնպես էլ նվազող, ապա begin և end փոփոխականներում հաշվում եմ առաջին ու վերջին հասցեն։ Հետո while ցիկլի մարմինը կատարվում է այնքան ժամանակ, քանի դեռ begin փոփոխվող հասցեն չի հասել end հասցեին։ Ցիլկի մարմնում մի ուրիշ for ցիկլ է, որը հիշող սարքի մոդելի վրա հերթականորեն աշխատեցնում է March գործողությունները և status բուլյան փոփոխականի մեջ է կուտակում հաջողությունների ու ձախողումների արդյունքը։

    public boolean runOn(Memory mem)
    {
        // ամենամեծ հասցեն
        final int maxaddr = mem.rows * mem.columns - 1;

        // առաջին հասցեն
        int begin = direction == INC ? 0 : maxaddr;
        // վերջին հասցեն
        int end = direction == INC ? maxaddr : 0;

        boolean status = true;
        while( begin != end + direction ) {
            for( Operation op : operations ) {
                boolean opok = op.runOn(mem, begin);
                status = status && opok;
            }
            begin += direction;
        }

        return status;
    }

Էլեմենտի տեքստային ներկայացումը ստանալու համար գրել եմ toString մեթոդը։

@Override
    public String toString()
    {
        String ops = operations.stream()
                               .map(Operation::toString)
                               .collect(Collectors.joining(","));
        String dr = (direction == INC ? "=>" : "<=");
        return String.format("%s(%s)", dr, ops);
    }
}

March ալգորիթմ

March ալգորիթմը March էլեմենտների հավաքածու է՝ խմբավորված ինչ-որ անունի տակ։ Algorithm դասով մոդելավորել եմ March ալգորիթմը։

package march;

import memory.*;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * March ալգորիթմի մոդելը
 */
public class Algorithm {
    // ալգորիթմի անունը
    private String name = "";
    // էլեմենտների ցուցակը
    private List<Element< elements = null;

    /**/
    public Algorithm(String nm, List<Element> elems)
    {
        name = nm;
        elements = new ArrayList<Element>();
        elements.addAll(elems);
    }

Ալգորիթմը հիշող սարքի մոդելի վրա գործարկվում է նորից runOn անունն ունեցող մեթոդի միջոցով։ for ցիկլը անցնում է բոլոր էլեմենտներով և դրանք գործարկում է՝ արգումենտում տալով հիշող սարքի հղումը։ Կատարման կումուլյատիվ արդյունքը ձևավորվում է status փոփոխականում։

    public boolean runOn(Memory mem)
    {
        boolean status = true;

        for( Element el : elements ) {
            boolean elok = el.runOn(mem);
            status = status && elok;
        }

        if( !status )
            System.out.printf("'%s' ալգորիթմի կատարումը ձախողվեց։\n",
                     toString());

        return status;
    }

Վերջապես toString մեթոդը վերադարձնում է ալգորիթմի տեքստային ներկայացումը։

 @Override
    public String toString()
    {
        String estr = elements.stream()
                              .map(Element::toString)
                              .collect(Collectors.joining(";"));
        return String.format("%s { %s }", name, estr);
    }
}

Ալգորիթմների կառուցումը

Ես արդեն պատմեցի Operation, Element և Algorithm դասերի մասին։ Դրանցով կարելի է կազմել թեսթավորման ալգորիթմներ և դրանք գործարկել անսարքությունների մոդելներ պարունակող հիշող սարքի մոդելի վրա։ Բայց միայն նշված դասերի կոնստրուկտորներն օգտագործելով անհարմար է կառուցել մեծ ալգորիթմներ։ Օրինակ, միայն A0 { =>(W0); =>(W1,R1) } ալգորիթմը կառուցելու համար պետք է գրել հետևյալ Java կոդը։

List<Operation> ops0 = new ArrayList<>();
ops0.add( new Operation('W', '0') );

List ops1 = new ArrayList<>();
ops1.add( new Operation('W', '1') );
ops1.add( new Operation('R', '1') );

Element el0 = new Element(Element.INC, ops0);
Element el1 = new Element(Element.INC, ops1);

List els0 = new ArrayList<>();
els0.add(el0);
els0.add(el1);

Algorijthm al0 = new Algorithm("A0", els0);

Շատ ավելի հարմար կլիներ, որ ալգորիթմը կառուցվեր մարդուն հարմար տեքստային ներկայացումից։ Դրա համար march փաթեթում ավելացրել եմ Parser դասը, որի parse մեթոդը ստանում է March ալգորիթմի տեքստային ներկայացումը և վերադարձնում է կառուցված Algorithm օբյեկտի հղումը։

package march;

import java.util.ArrayList;
import java.util.List;

public class Parser {
    private char[] source = null;
    private int position = 0;

    public Algorithm parse(String src) throws Exception
    {
        source = src.replaceAll("\\s+", "").toCharArray();
        position = 0;

        return parseAlgorithm();
    }

Parser դասը մի պարզագույն քերականական վերլուծիչ է, որը «ճանաչում» է March ալգորիթմի վերը բերված քերականությունը․

Algorithm = IDENT '{' Element { ';' Element } '}'.
  Element = ('=>' | '<=') '(' Operation { ',' Operation } ')'.
Operation = ('W' | 'R') ('0' | '1').

Քերականական երեք կանոններից յուրաքանչյուրի համար ստեղծված են համապատասխան մեթոդները՝ parseAlgorithm, parseElement և parseOperation։ Սրանցից ամեն մեկը վերլուծում է քերականությամբ իր համար որոշված հատվածը և վերադարձնում է Algorithm, Element կամ Operation օբյկտի հղում։

    private Algorithm parseAlgorithm() throws Exception
    {
        char[] name = {0, 0};
        if( !Character.isUpperCase(source[position]) )
            throw new Exception("Սպասվում է լատիներեն մեծատառ։");
        name[0] = source[position++];
        if( !Character.isDigit(source[position]) )
            throw new Exception("Սպասվում է թվանշան։");
        name[1] = source[position++];

        if( source[position++] != '{' )
            throw new Exception("Սպասվում է '{'։");

        List<Element> elements = new ArrayList<>();
        elements.add(parseElement());
        while( source[position] == ';' ) {
            ++position;
            elements.add(parseElement());
        }

        if( source[position++] != '}' )
            throw new Exception("Սպասվում է '}'։");

        return new Algorithm(new String(name), elements);
    }

    private Element parseElement() throws Exception
    {
        int direction = 0;
        if( source[position] == '=' && source[position+1] == '>' )
            direction = 1;
        else if( source[position] == '<' && source[position+1] == '=' )
            direction = -1;
        else
            throw new Exception("Սպասվում է '=>' կամ '<=։");

        position += 2;

        if( source[position++] != '(' )
            throw new Exception("Սպասվում է '('։");

        List<Operation> operations = new ArrayList<>();
        operations.add(parseOperation());
        while( source[position] == ',' ) {
            ++position;
            operations.add(parseOperation());
        }

        if( source[position++] != ')' )
            throw new Exception("Սպասվում է ')'։");

        return new Element(direction, operations);
    }

    private Operation parseOperation() throws Exception
    {
        char code = source[position++];
        if( code != 'W' && code != 'R' )
            throw new Exception("Անծանոթ գործողություն");
        char data = source[position++];
        if( data != '0' && data != '1' )
            throw new Exception("Գործողության սխալ արժեք");

        return new Operation(code, data);
    }

Իհարկե, հարմար կլիներ Parser դասին ավելացնել ևս մի parse մեթոդ, որը ստանա ալգորիթմների ցուցակ և վերադարձնի Algorithm օբյեկտների հղումների ցուցակ։