Bison and Flex Assignments - Matrix Dimension Checker

readme.md

Bison and Flex Assignments - Matrix Dimension Checker

How to Compile (for bison and flex)

./compile_yacc.sh matrix_checker.l matrix_checker.y

matrix_checker.py is writttern in Lark. NOTE: The program cannot tell the position of semantic error.

Assignment Instruction

The following are supported operators in this compiler

• addition +
• subtraction -
• multiplication *
• transpose ^T
• parenthesis ( )

All matrix are 2-dimensional matrices which are represented as [column number , row number]. e.g. [2, 3] is a 2x3 matrix and [5,1] is a 5x1 matrix. Your output should show Syntax Error if the input expression does not follow the grammar. If it follows the grammar, then apply semantic check to see if the dimension on both side of each operator is correct. Print Semantic error on col XX followed by the location of the first operator which makes the semantic error occur in post order of AST. If no any syntax error or semantic error, print Accepted.

Sample 1

• Input

[2,1]^T*[2,1]

• Output

Accepted

Sample 2

• Input

([2,3]*[2, 3]^T)^T+[4,1]

• Output

Semantic error on col 19

Sample 3

• Input

([1,2]+[2,1]^T)*[1,3]*[1,3]^T*[3,3]

• Output

Semantic error on col 16

compile_yacc.sh

#!/bin/bash
if (("$#" < 2)) || (("$#" > 3)); then
    echo "Illegal number of arguments"
    exit 1
fi
bison -v -d -o "y.tab.c" $2
gcc -c -g -I.. "y.tab.c"
flex -o lex.yy.c $1
gcc -c -g -I.. lex.yy.c
if [ "$#" -eq 2 ]; then
    gcc -o a.out "y.tab.o" lex.yy.o -ll
elif [ "$#" -eq 3 ]; then
    gcc -o $3 "y.tab.o" lex.yy.o -ll
fi

matrix_checker.l

%{
    #include "y.tab.h"
    void yyerror(const char *);
    int position = 0;
%}

%%
[0-9]+ {
    position += yyleng;
    yylval.ival = atoi(yytext);
    return INTEGER;
}

"^T" {
    position += yyleng;
    return TRANSPOSE;
}

"+"|"-"|"*" {
    position += yyleng;
    yylval.ival = position;
    return yytext[0];
}

"("|")"|"["|"]"|"," {
    position += yyleng;
    return yytext[0];
}

[ \t]+ {
    position += yyleng;
}

\n {
    return yytext[0];
}

. {
    yyerror("invalid input");
}

%%

matrix_checker.py

from lark import Lark, Transformer

parser = Lark(r"""
    ?line : sum "\n"

    ?sum : product
        | sum "+" product   -> add
        | sum "-" product   -> sub

    ?product : item
        | product "*" item  -> mul

    ?item : matrix_dim
        | "(" sum ")"
        | item "^T"         -> transpose

    ?matrix_dim : "[" SIGNED_INT "," SIGNED_INT "]"

    %import common.SIGNED_INT
    %import common.WS
    %ignore WS
    """, start='line')

class MatrixDimDbg(Transformer):
    def matrix_dim(self, items):
        return [int(items[0]), int(items[1])]
    
    def transpose(self, items):
        return [items[0][1], items[0][0]]

    def add(self, items):
        if items[0][0] == items[1][0] and items[0][1] == items[1][1]:
            return [items[0][0], items[0][1]]
        else:
            print('syntax error')
            exit(1)

    def sub(self, items):
        if items[0][0] == items[1][0] and items[0][1] == items[1][1]:
            return [items[0][0], items[0][1]]
        else:
            print('syntax error')
            exit(1)

    def mul(self, items):
        if items[0][1] == items[1][0]:
            return [items[0][0], items[1][1]]
        else:
            print('syntax error')
            exit(1)


def main():
    text = "([1,2]+[2,1]^T)^T*[1,3]*[1,3]^T*[1,3]\n"

    tree = parser.parse(text)

    print(tree.pretty())

    res = MatrixDimDbg().transform(tree)
    print('result:\n', res)

if __name__ == '__main__':
    main()

matrix_checker.y

%{
    #include <stdio.h>
    
    void yyerror(const char *);
    int yylex(void);
    void semantic_err(const int);
%}

%code requires {
    typedef struct {
        int row;
        int col;
    } matrix_dim;
}

%union {
    int ival;
    matrix_dim md;
}

/* declarations */
%token <ival> INTEGER
%type <md> expr
%type <md> matrix

/* precedences */
%left <ival> '+' '-'
%left <ival> '*'
%right TRANSPOSE

%%
line    : expr '\n'             {printf("Accepted\n");}
        ;

expr    : expr '+' expr         {
                                    if ($1.row == $3.row && $1.col == $3.col)
                                        $$ = $1;
                                    else {
                                        semantic_err($2);
                                        return 0;
                                    }
                                }
        | expr '-' expr         {
                                    if ($1.row == $3.row && $1.col == $3.col)
                                        $$ = $1;
                                    else {
                                        semantic_err($2);
                                        return 0;
                                    }
                                }
        | expr '*' expr         {
                                    if ($1.col == $3.row) {
                                        $$.row = $1.row;
                                        $$.col = $3.col;
                                    }
                                    else {
                                        semantic_err($2);
                                        return 0;
                                    }
                                }
        | '(' expr ')'          {$$ = $2;}
        | expr TRANSPOSE        {
                                    $$.row = $1.col;
                                    $$.col = $1.row;
                                }
        | matrix
        ;

matrix  : '[' INTEGER ',' INTEGER ']' {
                                    $$.row = $2;
                                    $$.col = $4;
                                }
        ;

%%
void semantic_err(const int col_num) {
    printf("Semantic error on col %d\n", col_num);
}

void yyerror(const char *message) {
    fprintf(stderr, "%s\n", message);
}

int main(void) {
    yyparse();
    return 0;
}