# ASP DSL Parser Design
**Version:** 1.0.0
**Architecture:** Lexer → AST → Validator → Generator
## Overview
The ASP DSL parser processes input at multiple levels:
1. **Direct Clingo** - Validate and execute
2. **Natural Language** - Detect problem type and generate
3. **Templates** - Fill parameters into pre-built patterns
4. **Default Logic** - Translate ADSL to ASP
## Architecture
```
┌─────────────────────────────────────────────────────────────┐
│ ASP DSL Parser │
├─────────────────────────────────────────────────────────────┤
│ │
│ Input Detection │
│ ┌──────────┐ ┌─────────────┐ ┌──────────┐ ┌─────────┐ │
│ │ Direct │ │ Natural │ │ Template │ │ Default │ │
│ │ Clingo │ │ Language │ │ Based │ │ Logic │ │
│ └────┬─────┘ └──────┬──────┘ └────┬─────┘ └────┬────┘ │
│ │ │ │ │ │
│ v v v v │
│ ┌──────────────────────────────────────────────────────┐ │
│ │ Clingo ASP │ │
│ └──────────────────────────────────────────────────────┘ │
│ │ │
│ v │
│ ┌──────────────────────────────────────────────────────┐ │
│ │ Validator & Safety Checker │ │
│ └──────────────────────────────────────────────────────┘ │
│ │ │
│ v │
│ ┌──────────────────────────────────────────────────────┐ │
│ │ Clingo Executor │ │
│ └──────────────────────────────────────────────────────┘ │
│ │ │
└──────────────────────────┼─────────────────────────────────┘
│
v
Answer Sets
```
## Module Breakdown
### 1. aspLexer.ts (~400 lines)
Tokenizes ASP syntax into lexical tokens.
**Token Types:**
- `ATOM` - Predicates and constants
- `VARIABLE` - Uppercase identifiers
- `NUMBER` - Numeric literals
- `LPAREN`, `RPAREN` - Parentheses
- `LBRACE`, `RBRACE` - Choice rules
- `DOT` - Statement terminator
- `COMMA` - Conjunction
- `SEMICOLON` - Disjunction
- `COLONDASH` - Rule implication (:-)
- `COLONWAVE` - Weak constraint (:~)
- `NOT` - Default negation
- `MINUS` - Classical negation
- `AGGREGATE` - #count, #sum, etc.
- `DIRECTIVE` - #show, #minimize, etc.
**Key Functions:**
```typescript
class ASPLexer {
tokenize(input: string): Token[]
private scanToken(): Token
private scanAtom(): Token
private scanNumber(): Token
private scanVariable(): Token
private skipWhitespace(): void
private skipComment(): void
}
```
### 2. aspAST.ts (~300 lines)
Abstract Syntax Tree node definitions.
**Node Types:**
```typescript
// Atoms
interface Atom {
type: 'atom';
predicate: string;
terms: Term[];
negation: 'none' | 'classical' | 'default';
}
// Rules
interface Rule {
type: 'rule';
head: Atom | Atom[];
body: Literal[];
}
// Choice Rules
interface ChoiceRule {
type: 'choice';
elements: ChoiceElement[];
lower?: number;
upper?: number;
body?: Literal[];
}
// Constraints
interface Constraint {
type: 'constraint';
body: Literal[];
}
// Weak Constraints
interface WeakConstraint {
type: 'weak_constraint';
body: Literal[];
weight: Term;
priority: Term;
terms: Term[];
}
// Aggregates
interface Aggregate {
type: 'aggregate';
function: 'count' | 'sum' | 'min' | 'max';
elements: AggregateElement[];
comparison?: Comparison;
}
// Complete Program
interface ASPProgram {
rules: Rule[];
constraints: Constraint[];
weakConstraints: WeakConstraint[];
choices: ChoiceRule[];
facts: Atom[];
directives: Directive[];
}
```
### 3. aspParser.ts (~600 lines)
Parses tokens into AST.
**Core Methods:**
```typescript
class ASPParser {
parse(tokens: Token[]): ASPProgram
private parseStatement(): Statement
private parseRule(): Rule
private parseChoice(): ChoiceRule
private parseConstraint(): Constraint
private parseWeakConstraint(): WeakConstraint
private parseHead(): Atom | Atom[]
private parseBody(): Literal[]
private parseLiteral(): Literal
private parseAtom(): Atom
private parseAggregate(): Aggregate
private parseTerms(): Term[]
private parseTerm(): Term
private parseComparison(): Comparison
}
```
**Grammar Implementation:**
Implements full ASP-Core-2 grammar with recursive descent parsing.
### 4. aspNaturalLanguage.ts (~500 lines)
Converts natural language to ASP programs.
**Problem Detection:**
```typescript
interface ProblemDetector {
detect(input: string): ProblemType;
}
type ProblemType =
| 'graph_coloring'
| 'hamiltonian_path'
| 'scheduling'
| 'n_queens'
| 'sudoku'
| 'knapsack'
| 'configuration'
| 'general';
```
**Pattern Matching:**
```typescript
const patterns = {
graph_coloring: [
/color.*graph/i,
/\d+.coloring/i,
/chromatic number/i,
],
hamiltonian: [
/hamiltonian (path|cycle)/i,
/visit.*once/i,
],
scheduling: [
/schedule/i,
/assign.*shift/i,
/timetable/i,
],
// ... more patterns
};
```
**Entity Extraction:**
```typescript
class EntityExtractor {
extractVertices(text: string): number[]
extractEdges(text: string): [number, number][]
extractNumbers(text: string): number[]
extractConstraints(text: string): string[]
}
```
**Generation:**
```typescript
class ASPGenerator {
generateFromProblemType(
type: ProblemType,
entities: Entities
): string
}
```
### 5. aspTemplates.ts (~400 lines)
Template library for common problems.
**Template Interface:**
```typescript
interface ProblemTemplate {
name: string;
description: string;
parameters: TemplateParameter[];
generate(params: Record<string, any>): string;
example: string;
}
interface TemplateParameter {
name: string;
type: 'number' | 'number[]' | 'edge[]' | 'string';
required: boolean;
default?: any;
description: string;
}
```
**Built-in Templates:**
1. **Graph Coloring**
```typescript
{
name: 'graph_coloring',
parameters: [
{ name: 'vertices', type: 'number[]', required: true },
{ name: 'edges', type: 'edge[]', required: true },
{ name: 'numColors', type: 'number', required: true }
],
generate: (params) => `
vertex(${params.vertices.join('; ')}).
${params.edges.map(([u,v]) => `edge(${u}, ${v}).`).join('\n ')}
color(1..${params.numColors}).
1 {assign(X, C) : color(C)} 1 :- vertex(X).
:- assign(X, C), assign(Y, C), edge(X, Y).
#show assign/2.
`
}
```
2. **N-Queens**
```typescript
{
name: 'n_queens',
parameters: [
{ name: 'n', type: 'number', required: true }
],
generate: (params) => `
row(1..${params.n}). col(1..${params.n}).
1 {queen(R, C) : col(C)} 1 :- row(R).
:- queen(R1, C), queen(R2, C), R1 != R2.
:- queen(R1, C1), queen(R2, C2), R1 != R2, |C1 - R1| = |C2 - R2|.
:- queen(R1, C1), queen(R2, C2), R1 != R2, C1 + R1 = C2 + R2.
#show queen/2.
`
}
```
3. **Scheduling**
4. **Hamiltonian Path**
5. **Sudoku**
6. **Knapsack**
7. **Configuration**
### 6. aspDefaultLogic.ts (~300 lines)
Translates default logic (ADSL) to ASP.
**ADSL Syntax:**
```
typically <conclusion> if <prerequisite> unless <exception>.
```
**Translation:**
```typescript
class DefaultLogicTranslator {
translate(adsl: string): string {
// Parse ADSL rule
const rule = parseADSL(adsl);
// Generate ASP rules
return `
${rule.conclusion} :- ${rule.prerequisite}, not ab_${rule.conclusion}.
ab_${rule.conclusion} :- ${rule.exception}.
`;
}
}
```
**Examples:**
```
ADSL: typically flies(X) if bird(X) unless penguin(X).
ASP:
flies(X) :- bird(X), not ab_flies(X).
ab_flies(X) :- penguin(X).
---
ADSL: typically available(R) if resource(R) unless reserved(R) | broken(R).
ASP:
available(R) :- resource(R), not ab_available(R).
ab_available(R) :- reserved(R).
ab_available(R) :- broken(R).
```
**Priority Handling:**
```
ADSL: typically flies(X) if bird(X) unless penguin(X) priority 1.
ADSL: typically flies(X) if bird(X), rescued(X) unless false priority 2.
ASP:
flies(X) :- bird(X), not ab_flies_1(X).
ab_flies_1(X) :- penguin(X).
ab_flies_1(X) :- ab_flies_2(X).
flies(X) :- bird(X), rescued(X), not ab_flies_2(X).
```
### 7. aspParser.test.ts (~800 lines)
Comprehensive test suite.
**Test Categories:**
1. Lexer tests (50+ cases)
2. Parser tests (80+ cases)
3. Natural language tests (30+ cases)
4. Template tests (20+ cases)
5. Default logic tests (15+ cases)
6. Integration tests (20+ cases)
## Validation System
### Safety Checker
```typescript
class SafetyChecker {
checkRule(rule: Rule): ValidationResult {
// Check head variables appear in positive body literals
const headVars = extractVariables(rule.head);
const bodyVars = extractPositiveVariables(rule.body);
const unsafe = headVars.filter(v => !bodyVars.has(v));
if (unsafe.length > 0) {
return {
valid: false,
error: `Unsafe variables: ${unsafe.join(', ')}`,
suggestion: 'Add positive body literals containing these variables'
};
}
return { valid: true };
}
checkAggregate(agg: Aggregate): ValidationResult {
// Check aggregate variables are safe
// ... similar logic
}
}
```
### Arity Checker
```typescript
class ArityChecker {
private predicateArities = new Map<string, number>();
checkProgram(program: ASPProgram): ValidationResult {
for (const atom of extractAllAtoms(program)) {
const arity = atom.terms.length;
const existing = this.predicateArities.get(atom.predicate);
if (existing !== undefined && existing !== arity) {
return {
valid: false,
error: `Arity mismatch for ${atom.predicate}`,
details: `Expected ${existing} arguments, got ${arity}`
};
}
this.predicateArities.set(atom.predicate, arity);
}
return { valid: true };
}
}
```
### Grounding Size Estimator
```typescript
class GroundingEstimator {
estimate(program: ASPProgram): EstimateResult {
let totalGroundings = 0;
for (const rule of program.rules) {
const ruleGroundings = estimateRuleGroundings(rule);
totalGroundings += ruleGroundings;
if (ruleGroundings > 100000) {
return {
estimated: ruleGroundings,
warning: 'Large grounding detected',
suggestion: 'Consider using conditional literals or domain restrictions'
};
}
}
return { estimated: totalGroundings };
}
}
```
## Clingo Integration
### Executor
```typescript
class ClingoExecutor {
async execute(
program: string,
options: ClingoOptions = {}
): Promise<ClingoResult> {
// Write program to temp file
const tempFile = await writeTempFile(program);
// Build clingo command
const args = [
tempFile,
'--outf=2', // JSON output
`${options.models || 0}`,
...this.buildOptimizationArgs(options)
];
// Execute clingo
const result = await execClingo(args);
// Parse JSON output
return this.parseOutput(result.stdout);
}
private parseOutput(json: string): ClingoResult {
const data = JSON.parse(json);
return {
satisfiable: data.Result === 'SATISFIABLE',
answerSets: data.Call[0].Witnesses.map(w => ({
atoms: parseAtoms(w.Value)
})),
time: data.Time.Total,
optimization: data.Models?.Costs
};
}
}
```
## Performance Optimizations
### 1. Caching
```typescript
class ASPCache {
private cache = new Map<string, ClingoResult>();
async get(program: string): Promise<ClingoResult | null> {
const key = hash(program);
return this.cache.get(key) || null;
}
set(program: string, result: ClingoResult): void {
const key = hash(program);
this.cache.set(key, result);
}
}
```
### 2. Incremental Grounding
For large programs, support incremental grounding:
```typescript
class IncrementalSolver {
async solveIncremental(
base: string,
steps: string[]
): Promise<ClingoResult[]> {
// Use clingo's multi-shot solving
// ...
}
}
```
## Error Messages
### Error Formatter
```typescript
class ErrorFormatter {
format(error: ValidationError): string {
return `
Error: ${error.type}
Line ${error.line}: ${error.code}
${' '.repeat(error.column)}^
${error.message}
${error.suggestion ? `Suggestion: ${error.suggestion}` : ''}
${error.example ? `Example: ${error.example}` : ''}
`.trim();
}
}
```
## Usage Examples
### Direct Usage
```typescript
import { ASPParser, ClingoExecutor } from './parsers/asp';
const parser = new ASPParser();
const executor = new ClingoExecutor();
// Parse program
const program = `
vertex(1..5).
edge(1,2). edge(2,3).
color(red; blue; green).
1 {assign(X, C) : color(C)} 1 :- vertex(X).
:- assign(X, C), assign(Y, C), edge(X, Y).
#show assign/2.
`;
const ast = parser.parse(program);
const validation = validator.validate(ast);
if (validation.valid) {
const result = await executor.execute(program);
console.log(result.answerSets);
}
```
### Natural Language
```typescript
import { NaturalLanguageProcessor } from './parsers/aspNaturalLanguage';
const nlp = new NaturalLanguageProcessor();
const input = "Color a cycle graph with 5 vertices using 3 colors";
const program = nlp.generate(input);
const result = await executor.execute(program);
```
### Template-Based
```typescript
import { TemplateLibrary } from './parsers/aspTemplates';
const templates = new TemplateLibrary();
const program = templates.apply('graph_coloring', {
vertices: [1, 2, 3, 4, 5],
edges: [[1,2], [2,3], [3,4], [4,5], [5,1]],
numColors: 3
});
const result = await executor.execute(program);
```
## Testing Strategy
### Unit Tests
- Lexer: Token generation
- Parser: AST construction
- Validator: Safety and semantic checks
- Generator: Code generation
### Integration Tests
- End-to-end parsing and execution
- Natural language understanding
- Template application
- Default logic translation
### Performance Tests
- Grounding size estimation
- Solving time benchmarks
- Cache effectiveness
---
**Total Implementation: ~2800 lines of TypeScript**
