PS3 · Memely

Memely：递归 ADT 与解析器

为 meme 表达式构建不可变递归 ADT，然后实现解析器和渲染器。从文法出发设计 AST，围绕结构等价性而非渲染细节构建。

基本信息

PS3递归 ADTParser不可变渲染

官方讲义：web.mit.edu/6.102/ps3 ↗

作业要求

构建不可变递归 ADT 表示 meme 表达式，然后实现 parser 和 renderer。公开讲义定义了完整的表达式语言和运算符行为。将文法放在 parser 旁边，围绕结构等价性而非渲染实现细节设计 AST。

此干净室支架故意将 AST 变体设计和 parser 设计留给你。这些设计工作是 PS3 的主要部分。

规格说明

表达式原语

图片文件名：字母/数字/句点，允许 - 和 _（不在开头）。解析文件名不要求文件存在。
标题：双引号单行字符串。渲染的标题必须适应文字且背景透明。

运算符（按优先级从高到低）

运算符	名称	行为
`@`	resize	指定 WxH，`?` 保持宽高比
`^`	顶部叠加	B 叠加在 A 顶部，水平居中
`_`	底部叠加	B 叠加在 A 底部，水平居中
`\|`	水平并置	宽度相加，高度取最大，垂直居中
`---`	垂直并置	高度相加，宽度取最大，水平居中

括号覆盖优先级。运算符周围空白不重要。由于 _ 和 - 也可能是文件名的一部分，用空白或括号分隔以避免歧义。

AST 要求

MemeExpression 不可变且递归。使用不同的变体表示表达式形式。不在 AST 中表示具体空白或括号。

interface MemeExpression {
  equalValue(that: MemeExpression): boolean;  // 结构等价
  toString(): string;                          // 可往返解析
}

equalValue 是结构等价：相同原始/运算符数据、相同顺序、相同 AST 分组
toString() 必须生成可解析的表达式，重建等价的 AST。必须递归实现，不得使用运行时变体检查

解析器

parse(input: string): MemeExpression

拒绝语法无效的输入。解析纯语法，允许未知/缺失的图片文件名。推荐迭代：先支持文件名、| 和数字 @；再添加标题、---、叠加和 ? 缩放。

Size 与渲染

size(expression, library): string   // "WxH"
image(expression, library): string   // data: URL

命令本身保持为薄胶层；组合/渲染属于 ADT 操作。

完成清单

文法笔记
immutable 递归 AST
结构等价性
parser
toString 往返
size 操作
渲染

源码骨架

expression.ts — MemeExpression 接口

export interface MemeExpression {
  equalValue(that: MemeExpression): boolean;
  toString(): string;
}

export function parse(input:string): MemeExpression { void input; throw new Error('TODO: parse'); }

expression-impls.ts — AST 变体（待设计）

import type { MemeExpression } from './expression.js';

// TODO: design immutable AST variant classes here.
// Every variant should document its AF / immutability argument,
// implement structural equalValue(), and produce a parsable toString().
export type AstPlaceholder = MemeExpression;

expressionparser.ts — 解析器机械

import type { MemeExpression } from './expression.js';

// Keep parsing mechanics separate from AST semantics.
export function parseExpression(input:string): MemeExpression { void input; throw new Error('TODO: parseExpression'); }

imagelibrary.ts — 图片/画布边界

export interface Image { readonly width:number; readonly height:number; readonly name:string; }
export interface Canvas { width:number; height:number; }
export interface TextMetrics { readonly width:number; }

export class ImageLibrary {
  private readonly images = new Map<string,Image>();
  public constructor(dirname:'img', ...filenames:string[]) {
    void dirname; for (const name of filenames) this.images.set(name,{name,width:1,height:1});
  }
  public getImage(name:string):Image { const img=this.images.get(name); if(!img) throw new Error(`image not loaded: ${name}`); return img; }
}
export function createCanvas(width:number,height:number):Canvas {
  if(width<=0||height<=0) throw new Error('positive dimensions required'); return {width,height};
}

commands.ts — 薄胶层命令

import type { MemeExpression } from './expression.js';
import type { ImageLibrary } from './imagelibrary.js';

export function size(expression:MemeExpression, library:ImageLibrary):string {
  void expression; void library; throw new Error('TODO: keep this as glue over your recursive MemeExpression size operation');
}
export function image(expression:MemeExpression, library:ImageLibrary):string {
  void expression; void library; throw new Error('TODO: keep this as glue over your recursive MemeExpression render operation');
}