教程文档示例工程【免费下载链接】website-archiveArchive of the Coding Train website (first version)项目地址https://gitcode.com/gh_mirrors/we/website-archive点击查看免费下载本文以 Coding Train网站归档仓库 website-archive第 43 号编码挑战Context-Free Grammar为蓝本完整讲解如何不依赖任何框架、仅用 p5.js 与递归从零编写一个上下文无关语法Context-Free Grammar文本生成器。文章将以 sketch.js 的实际源码为主线剖析规则集rules的数据结构、递归展开expand算法与按钮交互流程并结合仓库附带的 tracery.js 说明如何向 Tracery 这类成熟语法引擎迁移。读完本文后你将掌握一套可复用的规则 递归替换文本生成模式并能够据此扩展出自己的生成式文本应用。挑战背景它属于哪一堂课本挑战在归档站点中的元信息如下见 _CodingChallenges/043-contextfreegrammar.md视频编号43video_number: 43发布日期2016-10-31关联仓库目录CC_043_ContextFreeGrammar所属课程ITP 课程Programming from A to Z的 Session 7需要说明的是Session 7 在课程侧被拆分为四讲见 _learning/programming-with-text 目录课程小节标题核心内容7.1-introduction.mdIntro to Session 7引入上下文无关语法概念一组递归的替换规则介绍 Tracery 与 RiTa.js 两个库7.2-context-free-grammar-with-tracery.mdContext-Free Grammar with Tracery演示用 Kate Compton 的 Tracery 从一组语法规则生成故事7.3-context-free-grammar-with-ritajs.mdContext-Free Grammar with RiTa.js演示用 Daniel C. Howe 的 RiTa.js 生成文本7.4-homework-assignment-session-7.mdHomework Assignment Session 7布置围绕上下文无关语法的练习而第 43 号挑战正是这一系列中最硬核的一环不借助任何语法库从零手写一个最小可用的生成器其核心概念就是递归recursion。这与课程 7.1 的描述A Context-Free Grammar is a set of recursive replacement rules to generate text完全对应。上下文无关语法的最小模型在动手前先建立直觉模型。一个上下文无关语法由产生式规则构成每条规则形如非终结符 - 若干符号序列终结符或非终结符生成过程就是从起始符号本挑战中为S出发反复把非终结符替换成它的某一条候选产生式直到序列中只剩下终结符真实单词为止。由于非终结符可以被替换为仍包含非终结符的序列递归便自然地产生了一个非终结符甚至可以直接或间接地引用自身从而让生成的文本长度与结构不断嵌套。第 43 号挑战的代码恰好呈现了这一模型最简形态下一节直接看源码。规则集rules的数据结构打开 sketch.js核心是一张名为rules的普通 JavaScript 对象L6-L37var rules { S: [ [NP, VP], [Interj, NP, VP] ], NP: [ [Det, N], [Det, N, that, VP], [Det, Adj, N] ], VP: [[Vtrans, NP], [Vintr]], Interj: [[oh], [my], [wow], [darn]], Det: [[this], [that], [the]], N: [ [amoeba], [dichotomy], [seagull], [trombone], [overstaffed], [corsage] ], Adj: [ [bald], [smug], [important], [tame], [overstaffed], [corsage] ], Vtrans: [[computes], [examines], [foregrounds]], Vintr: [[coughs], [daydreams], [whines]] };理解这张表的关键约定键是非终结符全部大写S、NP、VP、Interj、Det、N、Adj、Vtrans、Vintr。值是候选产生式组成的数组每个候选又是一个数组元素序列。序列中每个元素若是另一个键名如NP则为非终结符需要继续展开否则就是终结符真实单词如that、this直接输出。一个非终结符可以有多个候选生成时随机挑选其一这就是语法多样性的来源。这些符号命名借用了语言学里的短语结构NP名词短语 Noun Phrase、VP动词短语 Verb Phrase、Det限定词 Determiner、Adj形容词 Adjective、Vtrans及物动词、Vintr不及物动词、Interj感叹词。也就是说这套规则本质上是一个极简的英文句子模板库以S为根随机组合出诸如 this seagull computes that bald amoeba 一类虽不合常理、却句法完整的句子。源码中还保留了一段被注释的最小示例L38-L50只含S、N、V三条规则非常适合作为入门理解与自测的起点// var rules { // S: [ // [The, N, V] // ], // N: [ // [cat], // [dog] // ], // V: [ // [meows], // [barks] // ] // };递归展开算法核心中的核心整个生成器只有两个函数其中展开逻辑全部浓缩在expandL52-L63function expand(start, expansion) { if (rules[start]) { var pick random(rules[start]); console.log(pick); for (var i 0; i pick.length; i) { expand(pick[i], expansion); } } else { expansion.push(start); } return expansion.join( ); }逐行拆解其递归语义判断是否为非终结符if (rules[start])检查当前符号在规则表中是否存在。存在即非终结符。随机选择候选var pick random(rules[start])从该符号的所有候选中随机取一条产生式random来自 p5.js等价于按均匀分布随机取数组元素。递归遍历候选序列对选中候选里的每个元素再次调用expand——元素可能是别的非终结符继续递归也可能是终结符。终结符落盘当rules[start]不存在时说明start是真实单词直接expansion.push(start)追加到结果数组。拼接返回每次递归调用都返回expansion.join( )用空格把已收集的单词连接成句。递归在这里的两重作用结构上的递归NP的候选中含有VPVP的候选又可能含有NPVtrans - NP形成互相引用的递归关系生成 Det N that VP 这类嵌套子句。过程上的递归expand函数不断调用自身直到整条产生链全部落到终结符函数栈才逐层返回。需要留意一个实现细节expand的返回值和副作用expansion数组被持续 push是并存的最终结果以expansion数组内容为准。这种写法虽然简洁但递归分支之间共享同一个expansion数组意味着它属于深度优先的原地累积而不是纯函数式写法——这是理解该实现时最容易产生困惑的点。界面与交互一个按钮驱动生成setup与cfgL67-L78构成交互入口var button; function setup() { noCanvas(); button createButton(generate); button.mousePressed(cfg); } function cfg() { var start S; var expansion []; var result expand(start, expansion); console.log(result); createP(result); }要点如下noCanvas()本挑战不绘制任何图形只做文本输出因此显式关闭默认画布。createButton(generate)创建一个文字为generate的 HTML 按钮mousePressed(cfg)绑定点击回调。cfg()中start S固定以起始符号S为根每次生成都重新声明空数组expansion保证多次点击互不污染expand完成后结果既打印到控制台console.log(result)也通过createP(result)以段落形式渲染到页面。也就是说运行后页面呈现的是一个按钮 每次点击追加一行生成的句子。页面骨架见 index.html它按序引入了 jQuery、p5.js、Tracery 与 sketch.js正文body为空全部界面元素由 p5.js 动态创建。从零实现 vs Tracery仓库里的另一条路线值得特别指出该挑战目录中虽然以手写实现为主但 index.html 同时引入了 libraries/tracery.js即 Kate Compton 的 Tracery 库课程 7.2 的演示对象。这为对比从零实现与使用成熟引擎提供了现成素材。Tracery 的规则语法Tracery 将上述手写模型升级为符号 修饰符 动作的完整语法例如#hero# ate some #color# #animal.s#该示例出现在 tracery.js 内置自测tracery.test()中L1207。其规则解析由 parseRule 完成以#分隔普通文本与标签tag标签内以.分隔符号名与修饰符mods[ ]用于包裹动作actions。解析器还会对 Odd number of #、括号不配对等给出错误提示L159-L174。与手写实现的对应关系能力手写 sketch.jsTracery规则定义普通 JS 对象rules普通 JS 对象键为符号名随机展开random(rules[start])RuleSet.getIndex()加权随机tracery.js L395-L414递归替换expand自递归Grammar.prototype.expand构造展开树tracery.js L1131-L1139结果获取expansion.join( )Grammar.prototype.flatten返回纯文本tracery.js L1141-L1149文本修饰无内置universalModifiers如capitalize、capitalizeAll、comma、a、ed等tracery.js L550 起错误处理无缺失符号当作终结符直接输出缺失符号返回带error标记的占位规则tracery.js L1109-L1127使用 Tracery 的典型调用方式对应 tracery.createGrammarvar grammar tracery.createGrammar(rules); // rules 可直接复用上文对象 grammar.analyze(); // 预解析所有规则 var result grammar.flatten(#S#); // 以 #S# 为根展开并返回纯文本createGrammar内部调用Grammar.prototype.loadFromtracery.js L970-L993将传入对象按symbols字段若存在或对象本身解析为Symbol集合flatten则等价于建展开树 取childText。对比可见手写版把规则查找、随机选择、递归展开压缩在了一个 12 行的expand函数里直击上下文无关语法的本质而 Tracery 将同样的思想工程化为可扩展的语法引擎。前者适合教学与理解后者适合生产与复杂文本生成。运行方式该挑战为纯前端页面无需构建步骤克隆仓库后直接用浏览器打开CodingChallenges/CC_043_ContextFreeGrammar/P5/index.html。页面加载后会出现一个generate按钮依赖网络加载 p5.js 与 jQuery CDN。每次点击按钮页面追加一行随机生成的句子同时控制台输出该次选中的候选与最终结果。若要在本地离线运行可将 index.html 中的 CDN 地址替换为本地文件并保持libraries/tracery.js与sketch.js的相对引入路径不变。扩展思路与课后练习结合课程 7.4 的练习定位与本仓库实现可在不改动核心算法的前提下做如下扩展扩充词库向N、Adj、Vtrans等键的数组追加单词多样性随之提升。增加嵌套深度控制手写expand目前没有最大递归深度限制若引入可相互递归的规则如A - B、B - A理论上会无限递归直至栈溢出。可仿照 Tracery 的展开树思路为expand增加深度参数或候选使用次数限制。引入修饰器将规则值从字符串数组升级为带标记的字符串类似 Tracery 的#symbol.capitalize#扩展expand的终结符分支以支持大小写、复数等变换。迁移到 Tracery / RiTa.js正如课程 7.2 / 7.3 所示把rules对象直接喂给tracery.createGrammar(rules)即可立即获得加权随机、修饰符与动作系统而无须改动任何规则数据。小结第 43 号编码挑战用约 80 行代码完整呈现了上下文无关语法的两大支柱以非终结符 - 候选数组形式组织的规则表以及以递归替换为核心的展开算法。本文已结合 sketch.js 逐行拆解了规则数据结构、expand递归逻辑与按钮交互流程并对照仓库内 tracery.js 展示了从零实现到成熟引擎的迁移路径。这套规则表 递归生成器的模式可直接迁移到对话机器人语料、故事生成、随机命名器或游戏 NPC 台词等场景——递归正是让有限规则产出无限文本的那把钥匙。赞分享教程文档示例工程【免费下载链接】website-archiveArchive of the Coding Train website (first version)项目地址https://gitcode.com/gh_mirrors/we/website-archive点击查看免费下载相关推荐从零实现 L-System 分形树Coding Train 挑战 16Fractal Trees源码深度解析从零实现 L System 分形树Coding Train 挑战 16Fractal Trees源码深度解析 本篇围绕 Coding Train 网站归档教程文档示例工程从零绘制 Julia 集分形Processing 与 p5.js 双版本实现解析Coding Train 编码挑战 22从零绘制 Julia 集分形Processing 与 p5.js 双版本实现解析Coding Train 编码挑战 22 导读 本文围绕 Coding T教程文档示例工程The Coding Train 编程挑战 42.1基于 N-gram 的马尔可夫链文本生成实战解析The Coding Train 编程挑战 42.1基于 N gram 的马尔可夫链文本生成实战解析 本文围绕 The Coding TrainCoding教程文档示例工程上一篇革命性监控解决方案Falcon如何实现大规模集群实时监控下一篇7天掌握Flutter游戏开发Flame引擎完整教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考