31:T5fc,{ const height = width / aspectRatio; const padding = 20; const terminalPadding = fontSize * 1.5; const root = tree(sentenceParsed, width, height); // place word nodes just below their parent terminal node let bottomY = 0; root.each((d) => { if (!d.children) { d.y = d.parent.y + terminalPadding; bottomY = Math.max(bottomY, d.y); } }); const svg = d3 .create("svg") .attr("viewBox", [ -padding, -padding, width + padding * 2, bottomY + padding * 2 + 10 ]); const g = svg .append("g") .attr("font-family", fontFamily) .attr("font-size", fontSize); const link = g .append("g") .attr("fill", "none") .attr("stroke", lineColor) .attr("stroke-width", lineWidth) .selectAll("path") .data(root.links()) .join("path") .attr("d", (d) => d.target.children ? `M${d.source.x},${d.source.y}L${d.target.x},${d.target.y}` : "" ); const node = g .append("g") .attr("stroke-linejoin", "round") .attr("stroke-width", 12) .selectAll("g") .data(root.descendants()) .join("g") .attr("transform", (d) => `translate(${d.x},${d.y})`); // node.append("circle").attr("fill", "lightblue").attr("r", 15); node .append("text") .attr("dy", "0.4em") .attr("text-anchor", "middle") .attr("font-weight", (d) => (d.children ? "normal" : "bold")) .text((d) => d.data.unit) .clone(true) .lower() .attr("stroke", "white"); return svg.node(); }32:T582,parse = (sentence) => { validateBrackets(sentence); sentence = sentence.replaceAll(/\[\s*[A-Za-z0-9]*\s*\]/g, " "); const maxCallStack = 10; const maxChildren = 10; const parseHelper = (str, callStack = 0) => { if (callStack > maxCallStack) { throw "Max call stack exceeded."; } str = str.trim(); if (str[0] !== "[") { const word = str.substring(0, str.indexOf("]")).trim(); return [{ unit: word, callStack }, str.slice(word.length)]; } str = str.slice(1).trim(); const firstSpaceIndex = str.indexOf(" "); const firstStartIndex = str.indexOf("["); if (firstSpaceIndex < 0 && firstStartIndex < 0) { throw "Malformed input"; } const firstIndex = firstStartIndex >= 0 && firstStartIndex < firstSpaceIndex ? firstStartIndex : firstSpaceIndex; const unit = str.substring(0, firstIndex); let rest = str.substring(firstIndex).trim(); let children = []; while (rest[0] !== "]") { let x = parseHelper(rest, callStack + 1); children.push(x[0]); rest = x[1].trim(); if (children.length > maxChildren) { throw "Max children exceeded"; } } return [{ unit, children }, rest.slice(1)]; }; const [res, remaining] = parseHelper(sentence.replaceAll("\n", " ")); if (remaining) { return [`Parsing failed. Rest: ${remaining}`, res]; } return res; }33:T662,validateRules = (parsed, rules) => { function isUnitWord(p) { return !Boolean(p.children); } function validate(parsed) { const { unit, children } = parsed; const isWord = isUnitWord(parsed); if (isWord) { return []; } const numChildTerminals = children.filter(isUnitWord).length; if (numChildTerminals) { if (numChildTerminals < children.length) { return [`Terminal ${unit} can have exactly one word`]; } return []; } let errors = []; if (rules[unit]) { const rule = rules[unit]; let ruleIndex = 0; for (let child of children) { let childUnit = child.unit; let okay = undefined; while (okay === undefined) { if (ruleIndex >= rule.length) { okay = false; } else if (rule[ruleIndex].symbols.includes(childUnit)) { okay = true; if (!rule[ruleIndex].multiple) { // move on if not multiple ruleIndex++; } } else { if (rule[ruleIndex].optional) { // possibly okay, move on ruleIndex++; } else { // not good okay = false; } } } if (!okay) { errors.push( `Unit \`${unit}\` does not meet rule due to child \`${childUnit}\`` ); break; } } } else { errors.push(`Unit \`${unit}\` is not legal`); } errors = [...errors, ...(children?.flatMap((c) => validate(c)) || [])]; return errors; } return validate(parsed); }34:[] 2f:{"title":"Linguistics Syntax Tree","cells":[{"id":0,"value":"# Linguistics Syntax Tree","pinned":false,"hidden":false,"mode":"md"},{"id":357,"value":"Test sentence:\n- [TP [NP [D the] [N boy]][I [I' may] [VP [V eat] [NP [N apples]]]]]","pinned":false,"hidden":false,"mode":"md"},{"id":242,"value":"viewof sentenceRaw = Inputs.textarea({\n label: \"Sentence\",\n placeholder: \"Sentence in bracket notation\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":341,"value":"md`### Bracket notation\n${formatBracket(sentenceParsed)}\n### Errors\n

${x}
None!

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":369,"value":"sentenceParsed = parse(sentenceRaw)","pinned":false,"hidden":false,"mode":"ojs"},{"id":190,"value":"viewof rulesRaw = Inputs.textarea({\n label: \"Phrase structure rules\",\n placeholder:\n \"Add structure rules on each line, like: X: (XP) N (NP+) {VP/NP}\",\n value: englishRules,\n rows: 10\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":176,"value":"viewof layoutAlgorithm = Inputs.radio([\"tree\", \"cluster\"], {\n label: \"Layout Algorithm\",\n value: \"tree\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":216,"value":"viewof aspectRatio = Inputs.range([1, 8], {\n step: 0.1,\n value: 3,\n label: \"Aspect ratio (w/h)\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":542,"value":"viewof fontSize = Inputs.range([8, 30], {value: 20, step: 2, label: \"Font size\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":555,"value":"viewof lineWidth = Inputs.range([0, 11], {\n value: 2,\n step: 0.5,\n label: \"Line width\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":565,"value":"viewof lineColor = Inputs.color({ label: \"Line color\", value: \"#111\" })","pinned":false,"hidden":false,"mode":"ojs"},{"id":576,"value":"viewof fontFamily = Inputs.text({\n label: \"Font\",\n placeholder: \"sans-serif\",\n value: \"sans-serif\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":312,"value":"---\n## Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":7,"value":"d3 = require(\"d3@7\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":385,"value":"validateBrackets = (sentence) => {\n function context(index) {\n return `\\n${sentence.substring(\n Math.max(0, index - 3),\n Math.min(sentence.length - 1, index + 4)\n )}\\n ^ `;\n }\n\n let level = 0;\n for (let i = 0; i < sentence.length; i++) {\n const c = sentence.charAt(i);\n if (c !== \"[\" && c !== \"]\") {\n continue;\n }\n level += c === \"[\" ? 1 : -1;\n if (level < 0) {\n throw `Unmatched ${c} at index ${i} at ${context(i)}`;\n } else if (level === 0 && i < sentence.length - 1) {\n throw `Must have only one overall constituent. Failed at index ${i} at ${context(\n i\n )}`;\n }\n }\n if (level > 0) {\n throw \"Unmatched [\";\n }\n return \"Valid\";\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":247,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":340,"value":"formatBracket = (parsed) => {\n function unparse(parsed) {\n if (!parsed.children) {\n return parsed.unit;\n }\n return `[_{${parsed.unit}} ${parsed.children\n .map(unparse)\n .join(\" \")}]`;\n }\n return unparse(parsed);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":419,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"tree = (data, w = width, h = width) => {\n const root = d3.hierarchy(data);\n return d3[layoutAlgorithm]().size([w, h])(root);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":185,"value":"englishRules = `CP: (C) TP\nTP: {NP/CP} (T) VP\nVP: (AdvP+) V (NP) ({NP/CP}) (AdvP+) (PP+) (AdvP+)\nNP: (D) (AdjP+) N (PP+) (CP)\nPP: P (NP)\nAdjP: (AdvP) Adj\nAdvP: (AdvP) Adv\nXP: XP conj XP\nX: X conj X`","pinned":false,"hidden":false,"mode":"ojs"},{"id":187,"value":"rules = Object.fromEntries(\n rulesRaw\n .split(\"\\n\")\n .filter((x) => x)\n .map((x) => {\n let res = x\n .trim()\n .split(\":\")\n .map((y) => y.trim());\n res[1] = res[1].split(\" \").map((y) => {\n let optional = false;\n let multiple = false;\n if (y[0] === \"(\") {\n y = y.slice(1, -1);\n optional = true;\n }\n if (y[y.length - 1] === \"+\") {\n y = y.slice(0, -1);\n multiple = true;\n }\n if (y[0] === \"{\") {\n y = y.slice(1, -1);\n }\n return {\n optional,\n multiple,\n symbols: y.split(\"/\")\n };\n });\n\n return res;\n })\n)","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W34","stdlib":"1","titling":"auto"}