Brace expansion: Difference between revisions
Content added Content deleted
(remove draft status) |
|||
Line 1,211: | Line 1,211: | ||
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\} |
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\} |
||
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}</pre> |
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}</pre> |
||
=={{header|JavaScript}}== |
|||
===ES5 Functional=== |
|||
Without importing Node.js libraries, JavaScript doesn't immediately have access to anything like Haskell's Parsec, but using a functional idiom of JavaScript, and emphasising clarity more than optimisation, we can separate out the tokenizing from the parsing, and the parsing from the generation of strings, to build a function which: |
|||
:#returns the set of expansions for each brace expression, and |
|||
:#logs a pretty-printed abstract syntax tree for each expression to the console (in a JSON format). |
|||
Each node of the parse tree consists of one of two simple functions (AND: syntagmatic concatenation, OR: flattening of paradigms) with a set of arguments, each of which may be a plain string or an AND or OR subtree. The expansions are derived by evaluating the parse tree as an expression. |
|||
<lang JavaScript>(function () { |
|||
'use strict' |
|||
// 1. Return each test expression with an indented list of its expansions, while |
|||
// 2. logging each parse tree to the console.log() stream |
|||
function main() { |
|||
// Sample expressions, double-escaped for quotation in source code. |
|||
var lstTests = [ |
|||
'~/{Downloads,Pictures}/*.{jpg,gif,png}', |
|||
'It{{em,alic}iz,erat}e{d,}, please.', |
|||
'{,{,gotta have{ ,\\, again\\, }}more }cowbell!', |
|||
'{}} some }{,{\\\\{ edge, edge} \\,}{ cases, {here} \\\\\\\\\\}' |
|||
]; |
|||
return lstTests.map( |
|||
function (s) { |
|||
var dctParse = andTree( |
|||
null, |
|||
tokens(s) |
|||
)[0]; |
|||
console.log( |
|||
pp(dctParse) |
|||
); |
|||
return s + '\n\n' + evaluated( |
|||
dctParse |
|||
).map(function (x) { |
|||
return ' ' + x; |
|||
}).join('\n'); |
|||
} |
|||
).join('\n\n'); |
|||
} |
|||
// Index of any closing brace matching the opening brace at iPosn |
|||
// with the indices of any immediately-enclosed commas |
|||
function bracePair(tkns, iPosn, iNest, lstCommas) { |
|||
if (iPosn >= tkns.length || iPosn < 0) return null; |
|||
var t = tkns[iPosn], |
|||
n = (t === '{') ? iNest + 1 : ( |
|||
t === '}' ? iNest - 1 : iNest |
|||
), |
|||
lst = (t === ',' && iNest === 1) ? |
|||
lstCommas.concat(iPosn) : lstCommas; |
|||
return n ? bracePair(tkns, iPosn + 1, n, lst) : { |
|||
close: iPosn, |
|||
commas: lst |
|||
}; |
|||
} |
|||
// Parse of a SYNTAGM subtree |
|||
function andTree(dctSofar, tkns) { |
|||
if (!tkns.length) return [dctSofar, []]; |
|||
var dctParse = dctSofar ? dctSofar : { |
|||
fn: and, |
|||
args: [] |
|||
}, |
|||
head = tkns[0], |
|||
tail = head ? tkns.slice(1) : [], |
|||
dctBrace = head === '{' ? bracePair( |
|||
tkns, 0, 0, [] |
|||
) : null, |
|||
lstOR = dctBrace && dctBrace.close && dctBrace.commas.length ? ( |
|||
splitAt(dctBrace.close + 1, tkns) |
|||
) : null; |
|||
return andTree({ |
|||
fn: and, |
|||
args: dctParse.args.concat( |
|||
lstOR ? orTree(dctParse, lstOR[0], dctBrace.commas) : head |
|||
) |
|||
}, lstOR ? lstOR[1] : tail); |
|||
} |
|||
// Parse of a PARADIGM subtree |
|||
function orTree(dctSofar, tkns, lstCommas) { |
|||
if (!tkns.length) return [dctSofar, []]; |
|||
var iLast = lstCommas.length; |
|||
var dctOr = { |
|||
fn: or, |
|||
args: splitsAt( |
|||
lstCommas, tkns |
|||
).map(function (x, i) { |
|||
var ts = x.slice(1, i === iLast ? -1 : void 0); |
|||
return ts.length ? ts : ['']; |
|||
}).map(function (ts) { |
|||
return ts.length > 1 ? andTree(null, ts)[0] : ts[0]; |
|||
}) |
|||
}; |
|||
return dctOr; |
|||
} |
|||
// List of unescaped braces and commas, and remaining strings |
|||
function tokens(str) { |
|||
// Filter function excludes empty splitting artefacts |
|||
var toS = function (x) { |
|||
return x.toString(); |
|||
}; |
|||
return str.split(/(\\\\)/).filter(toS).reduce(function (a, s) { |
|||
return a.concat(s.charAt(0) === '\\' ? s : s.split( |
|||
/(\\*[{,}])/ |
|||
).filter(toS)); |
|||
}, []); |
|||
} |
|||
// PARSE TREE OPERATOR (1 of 2) |
|||
// Each possible head * each possible tail |
|||
function and(args) { |
|||
var lng = args.length, |
|||
head = lng ? args[0] : null, |
|||
lstHead = "string" === typeof head ? [head] : head; |
|||
return lng ? ( |
|||
1 < lng ? lstHead.reduce(function (a, h) { |
|||
return a.concat( |
|||
and(args.slice(1)).map(function (t) { |
|||
return h + t; |
|||
}) |
|||
); |
|||
}, []) : lstHead |
|||
) : []; |
|||
} |
|||
// PARSE TREE OPERATOR (2 of 2) |
|||
// Each option flattened |
|||
function or(args) { |
|||
return args.reduce(function (a, b) { |
|||
return a.concat(b); |
|||
}, []); |
|||
} |
|||
// One list split into two (first sublist length n) |
|||
function splitAt(n, lst) { |
|||
return n < lst.length + 1 ? ( |
|||
[lst.slice(0, n), lst.slice(n)] |
|||
) : [lst, []]; |
|||
} |
|||
// One list split into several (sublist lengths [n]) |
|||
function splitsAt(lstN, lst) { |
|||
return lstN.reduceRight(function (a, x) { |
|||
return splitAt(x, a[0]).concat(a.slice(1)); |
|||
}, [lst]); |
|||
} |
|||
// Value of the parse tree |
|||
function evaluated(e) { |
|||
return typeof e === 'string' ? e : e.fn( |
|||
e.args.map(evaluated) |
|||
); |
|||
} |
|||
// JSON prettyprint (for parse tree, token list etc) |
|||
function pp(e) { |
|||
return JSON.stringify(e, function (k, v) { |
|||
return typeof v === 'function' ? ( |
|||
'[function ' + v.name + ']' |
|||
) : v; |
|||
}, 2) |
|||
} |
|||
return main(); |
|||
})();</lang> |
|||
Value returned by function: |
|||
<pre>~/{Downloads,Pictures}/*.{jpg,gif,png} |
|||
~/Downloads/*.jpg |
|||
~/Downloads/*.gif |
|||
~/Downloads/*.png |
|||
~/Pictures/*.jpg |
|||
~/Pictures/*.gif |
|||
~/Pictures/*.png |
|||
It{{em,alic}iz,erat}e{d,}, please. |
|||
Itemized, please. |
|||
Itemize, please. |
|||
Italicized, please. |
|||
Italicize, please. |
|||
Iterated, please. |
|||
Iterate, please. |
|||
{,{,gotta have{ ,\, again\, }}more }cowbell! |
|||
cowbell! |
|||
more cowbell! |
|||
gotta have more cowbell! |
|||
gotta have\, again\, more cowbell! |
|||
{}} some }{,{\\{ edge, edge} \,}{ cases, {here} \\\\\} |
|||
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\} |
|||
{}} some }{,{\\ edge \,}{ cases, {here} \\\\\}</pre> |
|||
Sample of parse trees logged to the console: |
|||
<lang JavaScript>{ |
|||
"fn": "[function and]", |
|||
"args": [ |
|||
"It", |
|||
{ |
|||
"fn": "[function or]", |
|||
"args": [ |
|||
{ |
|||
"fn": "[function and]", |
|||
"args": [ |
|||
{ |
|||
"fn": "[function or]", |
|||
"args": [ |
|||
"em", |
|||
"alic" |
|||
] |
|||
}, |
|||
"iz" |
|||
] |
|||
}, |
|||
"erat" |
|||
] |
|||
}, |
|||
"e", |
|||
{ |
|||
"fn": "[function or]", |
|||
"args": [ |
|||
"d", |
|||
"" |
|||
] |
|||
}, |
|||
",", |
|||
" please." |
|||
] |
|||
}</lang> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |