Gorn地址是一种用于标识和寻址树数据结构中任意节点的方法，由美国计算机科学家Saul Gorn于1967年提出。它是由零个或多个整数组成的序列，通常用点分隔，例如0或1.0.1。这种表示法常用于标识由短语结构规则定义的解析树中的节点，其中每个地址唯一地编码从根节点到特定节点的路径。
树的根节点，Gorn称之为*，被视为空序列。对于任何地址为i的节点，其第j个子节点（从0开始计数）的地址为i.j。例如，在一棵根节点有子节点0、1和2的树中，地址1.0指的是根节点第二个子节点的第一个子节点。这种递归定义允许地址随着树的加深而任意增长，序列中的每个整数表示对应层级上的子节点索引。
形式定义
形式上，Gorn地址是一个非负整数的有限序列，通常写作a1.a2....an，其中每个ai是整数。空序列，用*或空字符串表示，代表根节点。节点的地址是通过将其父节点的地址与子节点索引用点连接而构造的。这种方案是无歧义的：树中的每个节点恰好有一个Gorn地址，并且每个有效地址恰好对应一个节点，前提是树是有限的且每个节点具有明确数量的子节点。
这种表示法在形式语言理论和计算语言学中特别有用，其中解析树由短语结构文法生成。在这样的树中，每个内部节点对应一个非终结符，其子节点对应产生式规则中的符号。Gorn地址提供了一种紧凑的方式来引用特定的子树或叶节点，使算法无需显式指针即可遍历或操作树结构。
在计算机科学中的应用
Gorn地址的主要应用在于语法树的表示和处理，尤其是在自然语言处理和编译器设计中。在编译器中，抽象语法树（AST）通常用Gorn地址进行标注，以方便错误报告、调试和代码生成。例如，编译器可能在地址2.1.0处报告错误，指示AST中的特定叶节点。
Gorn地址也出现在人工智能和机器学习研究中，特别是在符号AI和知识表示中。它们用于索引决策树和文法中的节点，其中从根到叶的每条路径代表唯一的规则或分类。在深度学习中，树结构神经网络（如树LSTM）有时使用Gorn地址来对齐输出与树位置。
与其他树寻址方案的关系
Gorn地址是标识树中节点的几种方法之一。替代方案包括堆索引（用于二叉堆，其中根为1，节点i的子节点为2i和2i+1）、XPath路径（使用元素名称和谓词）以及Lisp S表达式（使用嵌套列表）。与堆索引不同，Gorn地址不依赖于固定的分支度；它们适用于节点具有不同数量子节点的树。与XPath不同，Gorn地址纯粹是位置性的，不依赖于节点标签，因此更简单但描述性较弱。
这种表示法也与Unix文件路径相关，因为两者都使用标识符的层次序列，但Gorn地址仅使用整数和点分隔符，而文件路径使用名称和斜杠。这种基于整数的方案在结构已知但标签未知或标签冗余时具有优势。
历史背景与影响
Saul Gorn在1967年的论文“Explicit definitions and linguistic dominoes”中引入了这种地址表示法，该论文发表于多伦多大学举办的系统和计算机科学研讨会的会议录中。Gorn是计算机科学教育和编程语言领域的先驱，他在树寻址方面的工作影响了后来数据结构与形式语言理论的发展。术语“Gorn地址”现在已成为编译器设计和解析教科书中的标准用语，尽管有时也简称为“树地址”或“路径字符串”。
尽管年代久远，这种表示法在现代系统中仍然具有相关性。例如，XML和JSON处理工具通常使用类似的位置寻址进行调试，一些数据库使用类Gorn地址来索引分层数据。在编程语言理论中，Gorn地址用于属性文法中指定属性的计算位置。
局限性与扩展
Gorn地址的一个局限性是它假设子节点具有固定的顺序，这对于解析树是自然的，但对于无序树可能不成立。在这种情况下，地址仍然有效，但在不同顺序下可能不稳定。另一个局限性是对于深层树，地址可能变得很长，但这在实践中很少成为问题。
对Gorn地址的扩展包括使用负整数来表示特殊节点（例如虚拟根节点），或使用不同的分隔符以提高可读性。某些系统使用根为0的变体而不是空序列，但这并非标准。该表示法有时也与标签结合使用，如NP.0.1，其中NP是节点标签，但这是一种非正式扩展。
总之，Gorn地址是计算机科学中的一个基础概念，提供了一种简单、无歧义的方式来引用树中的节点。它在解析树和编译器中的使用使其成为持久有效的工具，并且它继续出现在涉及分层数据的现代研究和应用中。