/**
* ASP Parser
* Parses Answer Set Programming programs from both natural language and symbolic syntax
*/
import {
ASPProgram,
ASPRule,
ASPAtom,
ASPLiteral,
ASPConstraint,
ChoiceRule
} from '../types.js';
export class ASPParser {
/**
* Parse ASP program from text (natural language or symbolic)
*/
parse(input: string, format: 'natural' | 'symbolic' | 'mixed' = 'mixed'): ASPProgram {
// Check if input is clearly symbolic ASP (contains :-, not, variables with uppercase)
if (this.looksLikeSymbolicASP(input)) {
return this.parseSymbolic(input);
}
if (format === 'natural' || (format === 'mixed' && this.looksLikeNaturalLanguage(input))) {
return this.parseNaturalLanguage(input);
} else {
return this.parseSymbolic(input);
}
}
/**
* Check if input looks like symbolic ASP syntax
*/
private looksLikeSymbolicASP(input: string): boolean {
const symbolicPatterns = [
/:-/, // Rule operator
/\bnot\s+\w+\(/, // Default negation with predicate
/[A-Z]\w*(?:\s*,\s*[A-Z]\w*)?\s*\)/, // Variables in predicates (e.g., X) or (X,Y))
/\{[^}]+\}/, // Choice rules
/:~/, // Weak constraints
/\.\s+\w+\(/ // Multiple statements separated by period
];
return symbolicPatterns.some(pattern => pattern.test(input));
}
/**
* Check if input looks like natural language
*/
private looksLikeNaturalLanguage(input: string): boolean {
const naturalPatterns = [
/\b(find|choose|select|assign|color|schedule)\b/i,
/\b(all|some|every|each)\b.*\b(must|should|cannot|can)\b/i,
/\b(typically|normally|usually|by default|unless)\b/i,
/\b(minimize|maximize|prefer)\b/i
];
return naturalPatterns.some(pattern => pattern.test(input));
}
/**
* Parse natural language to ASP program
*/
parseNaturalLanguage(input: string): ASPProgram {
const program: ASPProgram = {
rules: [],
facts: [],
constraints: [],
weakConstraints: [],
choices: []
};
// Extract facts (definite statements)
program.facts = this.extractFacts(input);
// Extract rules
program.rules = this.extractRules(input);
// Extract constraints
program.constraints = this.extractConstraints(input);
// Extract choice rules
program.choices = this.extractChoices(input);
// Extract weak constraints (preferences/optimization)
program.weakConstraints = this.extractWeakConstraints(input);
return program;
}
/**
* Extract facts from natural language
*/
private extractFacts(input: string): ASPAtom[] {
const facts: ASPAtom[] = [];
// Pattern: "X is/are Y"
const isPattern = /(\w+)\s+(?:is|are)\s+(\w+)/gi;
let match;
while ((match = isPattern.exec(input)) !== null) {
const [, subject, property] = match;
facts.push({
predicate: property.toLowerCase(),
terms: [subject.toLowerCase()],
negation: 'none'
});
}
// Pattern: "node(1..5)" or "node(1;2;3)"
const rangePattern = /(\w+)\((\d+)\.\.(\d+)\)/g;
while ((match = rangePattern.exec(input)) !== null) {
const [, predicate, start, end] = match;
for (let i = parseInt(start); i <= parseInt(end); i++) {
facts.push({
predicate: predicate.toLowerCase(),
terms: [i],
negation: 'none'
});
}
}
// Pattern: "edge 1-2" or "edge(1,2)"
const edgePattern = /edge\s*(?:\()?(\d+)[,-](\d+)(?:\))?/gi;
while ((match = edgePattern.exec(input)) !== null) {
const [, from, to] = match;
facts.push({
predicate: 'edge',
terms: [parseInt(from), parseInt(to)],
negation: 'none'
});
}
return facts;
}
/**
* Extract rules from natural language
*/
private extractRules(input: string): ASPRule[] {
const rules: ASPRule[] = [];
// Pattern: "X if Y" or "X :- Y"
const ifPattern = /(\w+(?:\([^)]*\))?\s+(?:if|when)\s+(.+?)(?:\.|$))/gi;
let match;
while ((match = ifPattern.exec(input)) !== null) {
const [, head, bodyText] = match;
const headAtom = this.parseAtom(head.trim());
const body = this.parseBody(bodyText);
if (headAtom) {
rules.push({
head: headAtom,
body,
type: 'normal'
});
}
}
// Pattern: "typically X unless Y" (default rule)
const defaultPattern = /(?:typically|normally|usually)\s+(\w+(?:\([^)]*\))?)\s+unless\s+(.+?)(?:\.|$)/gi;
while ((match = defaultPattern.exec(input)) !== null) {
const [, conclusion, exception] = match;
const headAtom = this.parseAtom(conclusion.trim());
const body = [
...this.parseBody('not ' + exception.trim())
];
if (headAtom) {
rules.push({
head: headAtom,
body,
type: 'normal'
});
}
}
return rules;
}
/**
* Extract constraints from natural language
*/
private extractConstraints(input: string): ASPConstraint[] {
const constraints: ASPConstraint[] = [];
// Pattern: "X and Y cannot both..."
const cannotBothPattern = /(\w+)\s+and\s+(\w+)\s+cannot\s+both\s+(\w+)/gi;
let match;
while ((match = cannotBothPattern.exec(input)) !== null) {
const [, x, y, property] = match;
const body: ASPLiteral[] = [
{
atom: { predicate: property.toLowerCase(), terms: [x.toLowerCase()], negation: 'none' },
negation: 'none'
},
{
atom: { predicate: property.toLowerCase(), terms: [y.toLowerCase()], negation: 'none' },
negation: 'none'
}
];
constraints.push({
type: 'integrity',
body
});
}
// Pattern: "adjacent nodes must have different colors"
const mustDifferPattern = /adjacent\s+(\w+)\s+must\s+have\s+different\s+(\w+)/gi;
while ((match = mustDifferPattern.exec(input)) !== null) {
const [, entity, property] = match;
// This is a template - actual constraint will be added with variables
constraints.push({
type: 'integrity',
body: [], // Will be filled in by the grounder
terms: [entity, property]
});
}
return constraints;
}
/**
* Extract choice rules from natural language
*/
private extractChoices(input: string): ChoiceRule[] {
const choices: ChoiceRule[] = [];
// Pattern: "choose N from X"
const choosePattern = /choose\s+(\d+)\s+(?:from|of)\s+(\w+)/gi;
let match;
while ((match = choosePattern.exec(input)) !== null) {
const [, count, set] = match;
choices.push({
head: [], // Will be filled with actual atoms
bounds: { lower: parseInt(count), upper: parseInt(count) },
body: []
});
}
// Pattern: "assign exactly one X per Y"
const exactlyOnePattern = /(?:assign|choose|select)\s+(?:exactly\s+)?one\s+(\w+)\s+(?:per|for)\s+(?:each\s+)?(\w+)/gi;
while ((match = exactlyOnePattern.exec(input)) !== null) {
const [, what, perWhat] = match;
choices.push({
head: [], // Template
bounds: { lower: 1, upper: 1 },
body: []
});
}
return choices;
}
/**
* Extract weak constraints (optimization preferences)
*/
private extractWeakConstraints(input: string): ASPConstraint[] {
const weakConstraints: ASPConstraint[] = [];
// Pattern: "minimize X" or "maximize Y"
const optimizePattern = /(minimize|maximize)\s+(.+?)(?:\.|$)/gi;
let match;
while ((match = optimizePattern.exec(input)) !== null) {
const [, direction, what] = match;
const weight = direction.toLowerCase() === 'minimize' ? 1 : -1;
weakConstraints.push({
type: 'weak',
body: this.parseBody(what.trim()),
weight,
priority: 1
});
}
// Pattern: "prefer X over Y"
const preferPattern = /prefer\s+(\w+)\s+over\s+(\w+)/gi;
while ((match = preferPattern.exec(input)) !== null) {
const [, preferred, dispreferred] = match;
weakConstraints.push({
type: 'weak',
body: this.parseBody(dispreferred),
weight: 1,
priority: 2
});
}
return weakConstraints;
}
/**
* Parse symbolic ASP syntax
*/
parseSymbolic(input: string): ASPProgram {
const program: ASPProgram = {
rules: [],
facts: [],
constraints: [],
weakConstraints: [],
choices: []
};
// Split into statements - handle both newlines and ". " separators
// First normalize: ensure statements end with period
const normalized = input.replace(/\.\s+/g, '.\n');
const lines = normalized.split(/\r?\n/).map(line => line.trim()).filter(line => line && !line.startsWith('%'));
for (const line of lines) {
// Check for different types of statements
if (line.includes(':-')) {
// Rule or constraint
if (line.startsWith(':-')) {
// Integrity constraint
const body = this.parseSymbolicBody(line.substring(2).replace(/\.$/, ''));
program.constraints.push({
type: 'integrity',
body
});
} else if (line.startsWith(':~')) {
// Weak constraint
const parts = line.substring(2).split(/\[|\]/);
const body = this.parseSymbolicBody(parts[0].trim());
const weight = parts[1] ? parseInt(parts[1].split('@')[0]) : 1;
const priority = parts[1] ? parseInt(parts[1].split('@')[1] || '1') : 1;
program.weakConstraints!.push({
type: 'weak',
body,
weight,
priority
});
} else {
// Normal rule
const [headPart, bodyPart] = line.split(':-').map(s => s.trim());
const head = this.parseAtom(headPart.replace(/\.$/, ''));
const body = this.parseSymbolicBody(bodyPart.replace(/\.$/, ''));
if (head) {
program.rules.push({
head,
body,
type: 'normal'
});
}
}
} else if (line.includes('{') && line.includes('}')) {
// Choice rule
const choiceMatch = line.match(/\{([^}]+)\}(?:\s*=\s*(\d+))?(?:\s*:-\s*(.+))?/);
if (choiceMatch) {
const [, headStr, bound, bodyStr] = choiceMatch;
const bounds = bound ? { lower: parseInt(bound), upper: parseInt(bound) } : { lower: 0, upper: Infinity };
const body = bodyStr ? this.parseSymbolicBody(bodyStr.replace(/\.$/, '')) : [];
program.choices!.push({
head: [], // Parse head atoms
bounds,
body
});
}
} else if (!line.includes(':-') && !line.includes('{')) {
// Fact
const atom = this.parseAtom(line.replace(/\.$/, ''));
if (atom) {
program.facts.push(atom);
}
}
}
return program;
}
/**
* Parse an atom from text
*/
private parseAtom(text: string): ASPAtom | null {
const trimmed = text.trim();
// Check for negation
let negation: 'classical' | 'default' | 'none' = 'none';
let atomText = trimmed;
if (trimmed.startsWith('not ')) {
negation = 'default';
atomText = trimmed.substring(4);
} else if (trimmed.startsWith('¬') || trimmed.startsWith('-')) {
negation = 'classical';
atomText = trimmed.substring(1);
}
// Parse predicate and terms
const match = atomText.match(/^(\w+)(?:\(([^)]*)\))?$/);
if (!match) return null;
const [, predicate, termsStr] = match;
const terms = termsStr
? termsStr.split(',').map(t => {
const trimmed = t.trim();
const num = parseInt(trimmed);
return isNaN(num) ? trimmed : num;
})
: [];
return {
predicate: predicate.toLowerCase(),
terms,
negation
};
}
/**
* Parse body literals
*/
private parseBody(text: string): ASPLiteral[] {
const literals: ASPLiteral[] = [];
// Split by comma (and/conjunction)
const parts = text.split(',').map(s => s.trim());
for (const part of parts) {
const atom = this.parseAtom(part);
if (atom) {
literals.push({
atom: { ...atom, negation: 'none' },
negation: atom.negation || 'none'
});
}
}
return literals;
}
/**
* Parse symbolic body
*/
private parseSymbolicBody(text: string): ASPLiteral[] {
return this.parseBody(text);
}
/**
* Convert ASP program to Clingo-compatible syntax
*/
toClingoSyntax(program: ASPProgram): string {
let result = '';
// Facts
for (const fact of program.facts) {
result += this.atomToString(fact) + '.\n';
}
// Rules
for (const rule of program.rules) {
if (Array.isArray(rule.head)) {
// Disjunctive rule
result += rule.head.map(h => this.atomToString(h)).join(' | ');
} else {
result += this.atomToString(rule.head);
}
if (rule.body.length > 0) {
result += ' :- ' + rule.body.map(lit => this.literalToString(lit)).join(', ');
}
result += '.\n';
}
// Constraints
for (const constraint of program.constraints) {
if (constraint.type === 'integrity') {
result += ':- ' + constraint.body.map(lit => this.literalToString(lit)).join(', ') + '.\n';
}
}
// Weak constraints
if (program.weakConstraints) {
for (const wc of program.weakConstraints) {
result += ':~ ' + wc.body.map(lit => this.literalToString(lit)).join(', ');
result += `. [${wc.weight}@${wc.priority}]\n`;
}
}
// Choice rules
if (program.choices) {
for (const choice of program.choices) {
result += `{${choice.head.map(h => this.atomToString(h)).join('; ')}}`;
if (choice.bounds.lower === choice.bounds.upper) {
result += ` = ${choice.bounds.lower}`;
}
if (choice.body.length > 0) {
result += ' :- ' + choice.body.map(lit => this.literalToString(lit)).join(', ');
}
result += '.\n';
}
}
return result;
}
/**
* Convert atom to string
*/
private atomToString(atom: ASPAtom): string {
let result = '';
if (atom.negation === 'default') {
result += 'not ';
} else if (atom.negation === 'classical') {
result += '-';
}
result += atom.predicate;
if (atom.terms.length > 0) {
result += '(' + atom.terms.join(',') + ')';
}
return result;
}
/**
* Convert literal to string
*/
private literalToString(literal: ASPLiteral): string {
let result = '';
if (literal.negation === 'default') {
result += 'not ';
} else if (literal.negation === 'classical') {
result += '-';
}
result += this.atomToString(literal.atom);
return result;
}
}
