MatrixSDD

SDD for a context-free grammar (CFG) that generates the set of all strings over the alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, #}. The grammar is defined in the file A2.g4 under the grammars directory. The start variable has an attribute check whose value is 1 if the generated string represents a matrix of decimal digits where the sum of the first row is equal to the sum of the first column. Otherwise, the value of check is 0.

A string over {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, #} represents a matrix of digits if it is of the form r1#r2#...#rn, where ri ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}+ and |ri| = |rj|, for every 1<i, j<n.

File Tree

• csen1003/
  • main/a2/A2Runner.java
  • tests/a2/A2Tests.java
• grammars/
  • A2.g4
• README.md

The file A2Runner.java provides a class to generate and test individual strings that are generated by the grammar. The file A2Tests.java contains unit tests for the implementation. The method sCheckValue uses the ANTLR grammar to get the value of s.check for a given input string.

Examples:

• The following matrix:

2 2 2
2 4 6
1 3 5
1 4 6

would be represented as 222#246#135#146 and s.check should return 1.

• While the matrix

2 4 6 8 0
1 3 5 7 9
1 3 5 7 9
1 3 5 7 9

would be represented as 24680#13579#13579#13579 and s.check should return 0.

• The matrix

2 2 2
2 4 6
1 3
1 4 6

would be represented as 222#246#13#146 and s.check should return 0 because the rows' lengths are not equal.

Dependencies

This project uses ANTLR4 (version 4.9.3) to generate the parser and lexer for the grammar. Junit V5.9 is used for testing.