Public
Edited
Oct 29, 2023
{
function matchAndRewrite(expr, rule) {
// If the expression is a symbol or a number, it can only match a placeholder
if (expr.symbol || expr.number) {
return { match: expr.placeholder === rule.placeholder, expr };
}
// Otherwise, try to match based on the operation
if (expr.operation && rule.operation && expr.operation === rule.operation) {
const leftResult = matchAndRewrite(expr.left, rule.left);
const rightResult = matchAndRewrite(expr.right, rule.right);
if (leftResult.match && rightResult.match) {
// Both sides match, so rewrite based on the rule
return {
match: true,
expr: {
operation: rule.right.operation,
left: rightResult.expr,
right: leftResult.expr
}
};
}
}
// If no match, return the original expression and indicate no match
return { match: false, expr };
}
// Example usage
const expression = {
operation: "+",
left: {
symbol: "a"
},
right: {
operation: "*",
left: {
symbol: "b"
},
right: {
symbol: "c"
}
}
};
const rule = {
operation: "+",
left: {
placeholder: "A"
},
right: {
placeholder: "B"
}
};
const { match, expr } = matchAndRewrite(expression, rule);
if (match) {
return [`Match found! Rewritten expression: }`, expr];
} else {
return [`No match found. Original expression: `, expr];
}
}
lel2 = {
// Function to check if an S-expression is a placeholder
function isPlaceholder(sexp) {
return typeof sexp === "string" && sexp.startsWith("_");
}
// Function to recursively match an expression against a rule
function match(expr, rule, mapping) {
//console.log( "Matching:", JSON.stringify(expr), "against", JSON.stringify(rule) );
if (isPlaceholder(rule)) {
mapping[rule] = expr;
return true;
}
if (Array.isArray(expr) && Array.isArray(rule)) {
if (expr[0] !== rule[0]) return false;
for (let i = 1; i < rule.length; i++) {
if (!match(expr[i], rule[i], mapping)) {
return false;
}
}
return true;
}
return expr === rule;
}
function replace(rule, mapping, strategy) {
if (isPlaceholder(rule)) {
return mapping[rule];
}
if (Array.isArray(rule)) {
const replaced = [rule[0]];
for (let i = 1; i < rule.length; i++) {
replaced.push(replace(rule[i], mapping, strategy));
}
return replaced;
}
return rule;
}
// Function to apply a rule to an expression
function applyRule(expr, rule, strategy = {}) {
let output = null;
let modifiedRule = [...rule]; // Clone the rule to avoid modifications
//console.log("Applying rule to expr:", JSON.stringify(expr));
if (strategy.direction === "backward") {
[modifiedRule[1], modifiedRule[2]] = [modifiedRule[2], modifiedRule[1]];
}
const mapping = {};
if (match(expr, modifiedRule[1], mapping)) {
//console.log("Match found:", JSON.stringify(mapping));
output = replace(modifiedRule[2], mapping, strategy);
}
if (strategy.count === "all" && Array.isArray(expr)) {
for (let i = 0; i < expr.length; i++) {
const subOutput = applyRule(expr[i], rule, strategy);
if (subOutput !== null) {
expr[i] = subOutput;
}
}
}
return output || expr;
}
return { applyRule, match }; // Should output ["+',['*', 'b', 'c'],'a']
}
applyRule = lel2.applyRule
{
const expr = ["^", ["+", "a", "b"], "2"];
const rule = ["=", ["^", "_A", "2"], ["*", "_A", "_A"]];
const strategy = { direction: "forward", count: "all" };
//const newExpr = applyRule(expr, rule, strategy);
//return JSON.stringify(newExpr);
}
lel = {
function parseExpression(tokens, index) {
let exprStack = [];
let previousToken = null;
// console.log(`--- Entering parseExpression ---`);
// console.log(`Initial index: ${index}`);
while (index < tokens.length) {
let token = tokens[index];
index++;
// console.log(`Processing token: ${token}`);
// console.log(`Current index after increment: ${index}`);
if (token === "(") {
// console.log(`Detected open parenthesis. Recursing...`);
const result = parseExpression(tokens, index);
exprStack.push(result.expression);
index = result.newIndex;
// console.log(`Returning from recursion. Updated index: ${index}`);
} else if (token === ")") {
// console.log(`Detected close parenthesis. Breaking loop.`);
break;
} else if (infixOperators.includes(token)) {
// console.log(`Detected infix operator: ${token}`);
exprStack.push(token);
} else if (
prefixOperators.includes(token) &&
(!previousToken || infixOperators.includes(previousToken))
) {
// console.log(`Detected prefix operator: ${token}`);
const operand = tokens[index];
index++;
exprStack.push([token, operand]);
} else {
// console.log(`Detected operand or unknown token: ${token}`);
exprStack.push(token);
}
// console.log(
// `Expression stack after processing ${token}: ${JSON.stringify(
// exprStack
// )}`
// );
previousToken = token;
}
// console.log(`--- Exiting parseExpression ---`);
let currentExpr = exprStack.pop();
while (exprStack.length > 0) {
const operator = exprStack.pop();
let leftOperand;
if (exprStack.length > 0) {
leftOperand = exprStack.pop();
currentExpr = [operator, leftOperand, currentExpr];
} else {
currentExpr = [operator, currentExpr];
}
}
return { expression: currentExpr, newIndex: index };
}
/**
* Parses a string expression and returns it in S-expression format.
*
* @func
* @sig String -> Array
* @param {TemplateStringsArray} strings - The string literals.
* @param {...*} values - The string values.
* @return {Array} The parsed expression in S-expression format.
* @throws {Error} Throws an error if the expression cannot be parsed.
* @example
*
* sExp`(a + b)^2`; //=> ["^", ["+", "a", "b"], "2"]
* sExp`a + b`; //=> ["+", "a", "b"]
* sExp`!a`; //=> ["!", "a"]
*/
function sExp(strings, ...values) {
const input = String.raw(strings, ...values);
//console.log(`Starting to process input: ${input}`);
let tokens = input
.split(/\s+/)
.join("")
.split(/(>>>?|&&|\|\||>=?|<=?|[+\-*/()^><=|&!])/)
.filter((t) => t.length > 0);
//console.log(`Initial tokens: ${JSON.stringify(tokens)}`);
let index = 0;
try {
const result = parseExpression(tokens, index);
return result.expression;
} catch (error) {
throw new Error(`Error parsing expression: ${error.message}`);
}
}
var infixOperators = [
"+",
"-",
"*",
"/",
"^",
"=>",
"=<",
">>",
">>>",
":>",
"<",
"|",
"&",
"||",
"&&",
">="
];
var prefixOperators = ["!", "-"];
return { sExp };
}
sExp = lel.sExp
applyRule(
applyRule(sExp`(a+b)^2`, sExp`(_A^2)=(_A*_A)`, {
direction: "forward",
count: 1
}),
sExp`(_A^2)=(_A*_A)`,
{
direction: "backward",
count: 1
}
)
JSON.stringify(sExp`(a + b)^2`)
{
function runTests() {
const testCases = [
{ input: "(a + b)^2", output: ["^", ["+", "a", "b"], "2"] },
{ input: "a + b", output: ["+", "a", "b"] },
{ input: "!a", output: ["!", "a"] },
{ input: "-a", output: ["-", "a"] },
{ input: "+a", output: ["+", "a"] },
{ input: "a >= b", output: [">=", "a", "b"] },
{ input: "a >> b", output: [">>", "a", "b"] },
{ input: "a & b | c", output: ["|", ["&", "a", "b"], "c"] },
{ input: "a < b", output: ["<", "a", "b"] }
];
let markdownResults = "# Test Results\n\n";
for (const { input, output } of testCases) {
const parsedOutput = sExp`${input}`;
if (deepEqual(parsedOutput, output)) {
markdownResults += `- **Test for '${input}'**: Passed\n`;
} else {
markdownResults += `- **Test for '${input}'**: Failed. Expected ${JSON.stringify(
output
)}, got ${JSON.stringify(parsedOutput)}.\n`;
}
}
return markdownResults;
}
const mdResults = runTests();
return md`${mdResults}`;
}
{
function runMatchTests() {
let testResults = "# Match Function Tests\n\n";
const testCases = [
{ expr: ["+", "a", "b"], rule: ["+", "_x", "_y"], expected: true },
{ expr: ["+", "a", "b"], rule: ["*", "_x", "_y"], expected: false },
{
expr: ["+", "a", ["*", "b", "c"]],
rule: ["+", "_x", ["*", "_y", "_z"]],
expected: true
},
{ expr: "a", rule: "_x", expected: true },
{ expr: "a", rule: "a", expected: true },
{ expr: "a", rule: "b", expected: false },
{ expr: "a", rule: "_x", expected: true }
];
for (const { expr, rule, expected } of testCases) {
const mapping = {};
const result = lel2.match(expr, rule, mapping);
if (result === expected) {
testResults += `- **Test for expr '${JSON.stringify(
expr
)}' and rule '${JSON.stringify(rule)}'**: Passed\n`;
} else {
testResults += `- **Test for expr '${JSON.stringify(
expr
)}' and rule '${JSON.stringify(
rule
)}'**: Failed. Expected ${expected}, got ${result}\n`;
}
if (result) {
testResults += ` - Mapping: ${JSON.stringify(mapping)}\n`;
}
}
return testResults;
}
const matchTestResults = runMatchTests();
return md`${matchTestResults}`;
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
