S-expressions: Difference between revisions
→{{header|JavaScript}}: Added a functionally composed variant, generating a parse tree diagram.
(Added Wren) |
(→{{header|JavaScript}}: Added a functionally composed variant, generating a parse tree diagram.) |
||
Line 3,538:
=={{header|JavaScript}}==
===Procedural===
<lang JavaScript>String.prototype.parseSexpr = function() {
var t = this.match(/\s*("[^"]*"|\(|\)|"|[^\s()"]+)/g)
Line 3,576 ⟶ 3,577:
else
document.write('s-expr:<br>', sexpr, '<br><br>', sexpr.constructor != Array ? '' : 'pretty print:<br>' + sexpr.toPretty())</lang>
{{
<pre>text:
((data "quoted data" 123 4.5)
(data (!@# (4.5) "(more" "data)")))
Line 3,604:
)
)
)</pre>
===Functional===
Generating a diagram of the parse tree:
<lang JavaScript>(() => {
"use strict";
// -------------- S-EXPRESSION PARSING ---------------
// Expr = (Float | Int | String | Symbol)
// parseExpr [String] -> ([Tree Expr], [String])
const parseExpr = tokens => {
const p = ([, tkns]) =>
// Tokens depleted or closing bracket reached ?
0 === tkns.length || ")" === tkns[0];
const f = ([trees, tkns]) =>
0 < tkns.length ? (() => {
const [t, ...ts] = tkns;
return "(" === t ? (
// Opening brackets introduce subForests,
bimap(
xs => trees.concat(
Node(symbolName("List"))(xs)
)
)(
xs => xs.slice(1)
)(go(ts))
) : ")" === t ? (
// closing brackets conclude forests,
Tuple(trees)(ts)
) : Tuple(
// and other tokens are appended leaves.
trees.concat(
Node(atom(t))([])
)
)(ts);
})() : Tuple(trees)(tkns);
const go = ts => until(p)(f)(
Tuple([])(ts)
);
return go(tokens);
};
// atom :: String -> Expr
const atom = s =>
0 < s.length ? (
isNaN(s) ? (
"\"'".includes(s[0]) ? (
s.slice(1, -1)
) : symbolName(s)
) : parseFloat(s, 10)
) : "";
// symbolName :: String -> Symbol String
const symbolName = s => ({
"type": "symbol",
"name": s
});
// ------------------ TOKENIZATION -------------------
// tokenized :: String -> [String]
const tokenized = s =>
// Brackets and quoted or unquoted atomic strings.
quoteTokens("\"")(s).flatMap(
segment => "\"" !== segment[0] ? (
segment.replace(/([()])/gu, " $1 ")
.split(/\s+/u)
.filter(Boolean)
) : [segment]
);
// quoteTokens :: Char -> String -> [String]
const quoteTokens = q =>
// Preliminary segmentation before and after
// strings quoted by the supplied q character.
s => {
const go = ([bln, sofar, tkn], c) =>
q === c ? (
bln ? (
Tuple3(false)(
sofar.concat(
`${tkn.trim()}${q}`
)
)("")
) : Tuple3(true)(
sofar.concat(`${tkn.trim()}`)
)(q)
) : Tuple3(bln)(sofar)(`${tkn}${c}`);
return 0 < s.length ? (() => {
const [, tkns, residue] = [...s].reduce(
go, Tuple3(false)([])([])
);
return tkns.concat(residue.trim());
})() : [];
};
// ---------------------- TEST -----------------------
const main = () => {
const expr = [
"((data \"quoted data\" 123 4.5)",
" (data (!@# (4.5) \"(more\" \"data)\")))"
].join("\n");
return drawForest(
parseExpr(
tokenized(expr)
)[0].map(
fmapTree(showAtom)
)
);
};
const showAtom = x =>
x.type !== "symbol" ? (
JSON.stringify(x)
) : `<${x.name}>`;
// --------------------- GENERIC ---------------------
// Node :: a -> [Tree a] -> Tree a
const Node = v =>
// Constructor for a Tree node which connects a
// value of some kind to a list of zero or
// more child trees.
xs => ({
type: "Node",
root: v,
nest: xs || []
});
// Tuple (,) :: a -> b -> (a, b)
const Tuple = a =>
b => ({
type: "Tuple",
"0": a,
"1": b,
length: 2,
*[Symbol.iterator]() {
for (const k in this) {
if (!isNaN(k)) {
yield this[k];
}
}
}
});
// Tuple3 (,,) :: a -> b -> c -> (a, b, c)
const Tuple3 = a => b => c => ({
type: "Tuple3",
"0": a,
"1": b,
"2": c,
length: 3,
*[Symbol.iterator]() {
for (const k in this) {
if (!isNaN(k)) {
yield this[k];
}
}
}
});
// bimap :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)
const bimap = f =>
// Tuple instance of bimap.
// A tuple of the application of f and g to the
// first and second values respectively.
g => ([a, b]) => Tuple(f(a))(g(b));
// draw :: Tree String -> [String]
const draw = node => {
// shift :: String -> String -> [String] -> [String]
const shifted = (first, other, xs) => (
[first].concat(
Array.from({
length: xs.length - 1
}, () => other)
).map(
(y, i) => y.concat(xs[i])
)
);
// drawSubTrees :: [Tree String] -> [String]
const drawSubTrees = xs => {
const lng = xs.length;
return 0 < lng ? (
1 < lng ? (
["│"].concat(
shifted("├─ ", "│ ", draw(xs[0]))
)
).concat(
drawSubTrees(xs.slice(1))
) : ["│"].concat(
shifted("└─ ", " ", draw(xs[0]))
)
) : [];
};
return node.root.split("\n").concat(
drawSubTrees(node.nest)
);
};
// drawForest :: [Tree String] -> String
const drawForest = trees =>
trees.map(drawTree).join("\n");
// drawTree :: Tree String -> String
const drawTree = tree =>
draw(tree).join("\n");
// fmapTree :: (a -> b) -> Tree a -> Tree b
const fmapTree = f => {
// A new tree. The result of a
// structure-preserving application of f
// to each root in the existing tree.
const go = t => Node(
f(t.root)
)(
t.nest.map(go)
);
return go;
};
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until = p =>
// The value resulting from repeated applications
// of f to the seed value x, terminating when
// that result returns true for the predicate p.
f => x => {
let v = x;
while (!p(v)) {
v = f(v);
}
return v;
};
return main();
})();</lang>
{{Out}}
<pre><List>
│
├─ <List>
│ │
│ ├─ <data>
│ │
│ ├─ "quoted data"
│ │
│ ├─ 123
│ │
│ └─ 4.5
│
└─ <List>
│
├─ <data>
│
└─ <List>
│
├─ <!@#>
│
├─ <List>
│ │
│ └─ 4.5
│
├─ "(more"
│
└─ "data)"</pre>
=={{header|Julia}}==
| |||