BNF Support Package for DS

A bidirectional conversion library for the DS deductive system, providing seamless translation between two syntax formats:

• Ds: The S-expression (lisp-like) syntax used internally by DS
• Dsp: A traditional, human-readable syntax with infix operators

This package enables you to write logical rules in a more natural, mathematical notation and convert them to the DS internal format, or vice versa.

Features

• Bidirectional Conversion: Convert between Ds and Dsp syntax formats
• Multi-Language Support: Available for both Python and JavaScript/TypeScript
• Parse: Convert from readable Dsp syntax to DS internal format
• Unparse: Convert from DS internal format to readable Dsp syntax
• Comprehensive Operator Support: Functions, subscripts, unary and binary operators
• ANTLR-Based: Built on ANTLR 4.13.2 for robust parsing

Installation

Python (pip)

pip install apyds-bnf

Requires Python 3.11-3.14.

JavaScript/TypeScript (npm)

npm install atsds-bnf

Quick Start

Python Example

from apyds_bnf import parse, unparse

# Parse: Convert from readable Dsp to DS format
dsp_input = "a, b => c"
ds_output = parse(dsp_input)
print(ds_output)
# Output:
# a
# b
# ----
# c

# Unparse: Convert from DS format to readable Dsp
ds_input = "a\nb\n----\nc\n"
dsp_output = unparse(ds_input)
print(dsp_output)
# Output: a, b => c

JavaScript Example

import { parse, unparse } from "atsds-bnf";

// Parse: Convert from readable Dsp to DS format
const dsp_input = "a, b => c";
const ds_output = parse(dsp_input);
console.log(ds_output);
// Output:
// a
// b
// ----
// c

// Unparse: Convert from DS format to readable Dsp
const ds_input = "a\nb\n----\nc\n";
const dsp_output = unparse(ds_input);
console.log(dsp_output);
// Output: a, b => c

Syntax Formats

Ds Format (Internal)

The Ds format uses S-expressions (lisp-like syntax) for representing logical rules:

premise1
premise2
----------
conclusion

For structured terms:

• Functions: (function f a b)
• Subscripts: (subscript a i j)
• Binary operators: (binary + a b)
• Unary operators: (unary ~ a)

Dsp Format (Human-Readable)

The Dsp format uses traditional mathematical notation:

premise1, premise2 => conclusion

For structured terms:

• Functions: f(a, b)
• Subscripts: a[i, j]
• Binary operators: (a + b) (parenthesized)
• Unary operators: (~ a) (parenthesized)

Syntax Comparison Table

| Description | Dsp Format (parse input / unparse output) | Ds Format | |-------------|-------------------|-------------------| | Simple rule | a, b => c | a\nb\n----\nc\n | | Axiom | a | ----\na\n | | Function call | f(a, b) => c | (function f a b)\n----------------\nc\n | | Subscript | a[i, j] => b | (subscript a i j)\n-----------------\nb\n | | Binary operator | (a + b) => c | (binary + a b)\n--------------\nc\n | | Unary operator | ~ a => b | (unary ~ a)\n-----------\nb\n | | Complex expression | ((a + b) * c), d[i] => f(g, h) | (binary * (binary + a b) c)\n(subscript d i)\n---------------------------\n(function f g h)\n |

Building from Source

Prerequisites

• Python 3.11-3.14 (for Python package)
• Node.js (for JavaScript package)
• Java (for ANTLR parser generation)
• ANTLR 4.13.2

Python Package

cd bnf

# Install dependencies
uv sync --extra dev

# Build package
uv build

# Run tests
uv run pytest

# Run with coverage
uv run pytest --cov

JavaScript Package

cd bnf

# Install dependencies
npm install

# Build package
npm run build

# Run tests
npm test

Grammar Files

The conversion is based on ANTLR grammars:

• Ds.g4: Grammar for the Ds format (S-expression syntax)
• Dsp.g4: Grammar for the Dsp format (human-readable syntax)

These grammars are used to generate parsers for both Python and JavaScript.

License

This project is licensed under the GNU Affero General Public License v3.0 or later (AGPL-3.0-or-later).

Repository

• GitHub: USTC-KnowledgeComputingLab/ds (in /bnf directory)
• Python Package: apyds-bnf
• npm Package: atsds-bnf

Author

Hao Zhang [email protected]

Related

This package is a support library for the DS (Deductive System) project. For the main DS library with C++ core and bindings, see the main repository.