Something went wrong. Try again.
Something went wrong. Try again.
10 kB · 246 lines
TypeScript
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247import type { Clause, Expr, LamClause, Module, Pat, TypeDecl } from './ast.ts';import { lex, SyntaxError_, type Tok } from './lexer.ts';
/** * Syntax summary: * f:x call f with x (`:` binds tightest, left-associative: map:f:xs = (map:f):xs) * f:(a, b) the argument is a tuple; f:[a, b] a list; f:{|a|} a bag; f:{{a}} a set; f:{w: 1} a record * name:pattern = e one clause; clauses are tried in order * (p => e) | (p => e) a function literal (its own partition) * Tag / Tag:payload constructors * extend pkg.f:p = e add cells to another package's function */export function parse(src: string, file?: string): Module { const toks = lex(src); let p = 0; const peek = (o = 0) => toks[p + o]; const err = (msg: string, t = peek()): never => { throw new SyntaxError_(`${msg} (found '${t.v || t.t}')`, t.line, t.col); }; const isSym = (v: string, o = 0) => peek(o).t === 'sym' && peek(o).v === v; const eatSym = (v: string) => { if (!isSym(v)) err(`expected '${v}'`); p++; }; const take = (t: Tok['t']): string => { if (peek().t !== t) err(`expected ${t === 'Up' ? 'a constructor' : t === 'id' ? 'a name' : t}`); return toks[p++].v; }; const sepBy = <T>(close: string, item: () => T): T[] => { const xs: T[] = []; if (isSym(close)) { p++; return xs; } for (;;) { xs.push(item()); if (isSym(',')) { p++; continue; } eatSym(close); return xs; } }; /** Items up to `close`, with an optional trailing `...rest`. */ const seq = <T>(close: string, item: () => T): { items: T[]; rest?: T } => { const items: T[] = []; let rest: T | undefined; if (isSym(close)) { p++; return { items }; } for (;;) { if (isSym('...')) { p++; rest = item(); eatSym(close); break; } items.push(item()); if (isSym(',')) { p++; continue; } eatSym(close); break; } return { items, rest }; }; const intLit = (): number => { let neg = false; if (isSym('-')) { p++; neg = true; } const v = Number(take('int')); return neg ? -v : v; }; const tupleE = (items: Expr[]): Expr => (items.length === 1 ? items[0] : { k: 'rec', tuple: true, fields: items.map((e, i) => ({ name: String(i), e })) }); const tupleP = (items: Pat[]): Pat => (items.length === 1 ? items[0] : { k: 'rec', closed: true, fields: items.map((pat, i) => ({ name: String(i), pat })) });
/** Is the `(` at the cursor the start of a function literal `(p => e)`? */ const isLambda = () => { let depth = 0; for (let i = p; i < toks.length; i++) { const t = toks[i]; if (t.t === 'sym' && ['(', '[', '{', '{|', '{{'].includes(t.v)) depth++; else if (t.t === 'sym' && [')', ']', '}', '|}', '}}'].includes(t.v)) { depth--; if (depth === 0) return false; } else if (t.t === 'sym' && t.v === '=>' && depth === 1) return true; else if (t.t === 'eof') return false; } return false; };
// ---- patterns ---- /** A full pattern: may be a guard like `n < 0` or `n in 0..9`. */ function pat(): Pat { const t = peek(); if (t.t === 'id' && t.v !== '_' && !isSym('.', 1)) { if (peek(1).t === 'id' && peek(1).v === 'in') { p += 2; const lo = intLit(); eatSym('..'); const hi = intLit(); if (lo > hi) err('empty range'); return { k: 'int', lo, hi, name: t.v }; } for (const op of ['<', '<=', '>', '>=']) { if (isSym(op, 1)) { p += 2; const n = intLit(); const [lo, hi] = op === '<' ? [-Infinity, n - 1] : op === '<=' ? [-Infinity, n] : op === '>' ? [n + 1, Infinity] : [n, Infinity]; return { k: 'int', lo, hi, name: t.v }; } } } return patAtom(); } /** A pattern that is a single term (what can follow `Tag:`). */ function patAtom(): Pat { const t = peek(); if (t.t === 'id' && t.v === '_') { p++; return { k: 'any' }; } if (t.t === 'id' && !isSym('.', 1)) { p++; return { k: 'any', name: t.v }; } if (t.t === 'int' || isSym('-')) { const lo = intLit(); if (isSym('..')) { p++; const hi = intLit(); return { k: 'int', lo, hi }; } return { k: 'int', lo, hi: lo }; } if (t.t === 'str') { p++; return { k: 'str', v: t.v }; } if (isSym('(')) { p++; return tupleP(sepBy(')', pat)); } if (isSym('[')) { p++; return { k: 'list', ...seq(']', pat) }; } if (isSym('{|')) { p++; const r = seq('|}', pat); if (r.items.length > 1) err('a bag pattern takes one element: {| x, ...rest |}'); return { k: 'bag', ...r }; } if (isSym('{{')) { p++; const r = seq('}}', pat); if (r.items.length > 1) err('a set pattern takes one element: {{ x, ...rest }}'); return { k: 'set', ...r }; } if (isSym('{')) { p++; return { k: 'rec', fields: sepBy('}', () => { if (peek().t === 'id' && isSym(':', 1)) { const name = take('id'); p++; return { name, pat: pat() }; } const fp = pat(); if ((fp.k !== 'any' && fp.k !== 'int') || !fp.name) err('record pattern fields look like `name`, `name > 0`, or `name: pattern`'); return { name: (fp as { name: string }).name, pat: fp }; }) }; } if (t.t === 'id') { p += 2; } // qualified constructor `pkg.Tag`: tags are structural const tag = take('Up'); if (isSym(':')) { p++; return { k: 'tag', tag, payload: patAtom() }; } return { k: 'tag', tag }; }
// ---- expressions ---- function expr(): Expr { const first = compare(); if (!isSym('|')) return first; const clauses: LamClause[] = []; const addLam = (e: Expr) => { if (e.k !== 'lam') err('only function literals can be joined with |'); clauses.push(...(e as Expr & { k: 'lam' }).clauses); }; addLam(first); while (isSym('|')) { p++; addLam(compare()); } return { k: 'lam', clauses }; } function compare(): Expr { const a = concat(); for (const op of ['<', '<=', '>', '>=', '==', '!=']) if (isSym(op)) { p++; return { k: 'bin', op, a, b: concat() }; } return a; } function concat(): Expr { let a = additive(); while (isSym('++')) { p++; a = { k: 'bin', op: '++', a, b: additive() }; } return a; } function additive(): Expr { let a = mult(); while (isSym('+') || isSym('-')) { const op = toks[p++].v; a = { k: 'bin', op, a, b: mult() }; } return a; } function mult(): Expr { let a = unary(); while (isSym('*') || isSym('/') || isSym('%')) { const op = toks[p++].v; a = { k: 'bin', op, a, b: unary() }; } return a; } function unary(): Expr { if (isSym('-')) { p++; return { k: 'neg', a: unary() }; } return application(); } /** `f:a:b` is `(f:a):b` */ function application(): Expr { let e = atom(); while (isSym(':')) { p++; e = { k: 'app', fn: e, arg: atom() }; } return e; } function atom(): Expr { const t = peek(); if (t.t === 'int') { p++; return { k: 'int', v: Number(t.v) }; } if (isSym('-') && peek(1).t === 'int') { p += 2; return { k: 'int', v: -Number(peek(-1).v) }; } if (t.t === 'str') { p++; return { k: 'str', v: t.v }; } if (isSym('(')) { if (isLambda()) { const line = peek().line; p++; const lp = pat(); eatSym('=>'); const body = expr(); eatSym(')'); return { k: 'lam', clauses: [{ pat: lp, body, line }] }; } p++; return tupleE(sepBy(')', expr)); } if (isSym('[')) { p++; return { k: 'list', ...seq(']', expr) }; } if (isSym('{|')) { p++; return { k: 'bag', ...seq('|}', expr) }; } if (isSym('{{')) { p++; return { k: 'set', ...seq('}}', expr) }; } if (isSym('{')) { p++; return { k: 'rec', fields: sepBy('}', () => { const name = take('id'); if (isSym(':')) { p++; return { name, e: expr() }; } return { name, e: { k: 'var', name } as Expr }; }) }; } let q: string | undefined; if (t.t === 'id' && isSym('.', 1)) { q = take('id'); p++; } if (peek().t === 'Up') return { k: 'tag', tag: take('Up') }; return { k: 'var', q, name: take('id') }; }
// ---- top level ---- const mod: Module = { pkg: '', version: '', uses: [], types: [], clauses: [], extensions: [], file };
function typeDecl(): TypeDecl { const line = peek().line; p++; // 'type' const name = take('Up'); eatSym('='); const cons: TypeDecl['cons'] = []; if (isSym('|')) p++; for (;;) { const tag = take('Up'); let payload: Pat | undefined; if (isSym(':')) { p++; payload = patAtom(); } cons.push({ tag, payload }); if (isSym('|')) { p++; continue; } break; } return { name, cons, line }; } function clause(): Clause { const line = peek().line; let q: string | undefined; if (peek().t === 'id' && isSym('.', 1)) { q = take('id'); p++; } const name = take('id'); eatSym(':'); const cp = pat(); eatSym('='); return { name, q, pat: cp, body: expr(), line }; }
while (peek().t !== 'eof') { const t = peek(); if (t.t === 'nl') { p++; continue; } if (t.t === 'id' && t.v === 'package') { p++; mod.pkg = take('id'); eatSym('@'); mod.version = take('ver'); } else if (t.t === 'id' && t.v === 'use') { p++; const pkg = take('id'); eatSym('@'); mod.uses.push({ pkg, version: take('ver') }); } else if (t.t === 'id' && t.v === 'type' && peek(1).t === 'Up') { mod.types.push(typeDecl()); } else if (t.t === 'id' && t.v === 'extend') { p++; mod.extensions.push(clause()); } else if (t.t === 'id' && (isSym(':', 1) || (isSym('.', 1) && false))) { const c = clause(); if (c.q) err(`to add clauses to ${c.q}.${c.name}, write 'extend ${c.q}.${c.name}:...'`); mod.clauses.push(c); } else err('expected a definition like `name:pattern = expression`'); if (peek().t !== 'eof') { if (peek().t !== 'nl') err('expected end of line (definitions are single-line)'); p++; } } if (!mod.pkg) { mod.pkg = 'main'; mod.version = '0.0.0'; } return mod;}