全局索引语法

全局索引语法（GIGs）是Castaño（2004）介绍的一类语法，目的是对一些现象进行建模，包括自然语言语法和基因组语法。对GIGs最简单的描述是通过与索引语法的比较。在索引式语法中，每个非终端符号都有一个索引堆栈，并且可以根据推导过程的不同而变化，而在GIG中，有一个单一的全局索引堆栈，在推导过程中被操作（对于任何将符号推到堆栈中的重写操作，它都是严格的最左边）。由于全局堆栈的存在，当没有非终端符号需要重写，并且堆栈为空时，GIG推导被认为是完整的。规则描述GIG规则基本上有四种形式：无条件做某事的规则，以堆栈最上面的符号为条件做某事的规则，向堆栈推送的规则，以及从堆栈弹出的规则。我们可以将这些规则依次记为其中f是任何索引符号，α是任何终端和/或非终端符号的字符串，x是一个终端是一个终端符号。因为偶尔重写规则可能需要以堆栈在某种意义上是空的为条件，所以符号#被用作最底层的堆栈符号，这意味着一个空的堆栈正好包含一个符号，#。

第三种规则形式，即推送规则，应该指出，因为它与弹出规则不同，要求所有的推送操作至少要给派生字符串引入一个新的终端符号。如果没有这个约束，这类语法将是Type-0，因此是图灵完全的。

在这个例子中，我们将通过把推导字符串放在一个堆栈上来表示推导的步骤，如{displaystyle{p(a{n}b{n}c{n}):ngeq1}}，其中p是字符串互换函数，它被猜测（但未被证明）为不可表示为索引语言。，其中p是字符串互换函数，据猜测（但没有证明），它不能作为一种索引语言来表示。目前还不知道是否所有的IG也是GIG。GIGs和IGs完全有可能描述CSLs的仅仅重叠的子集。trGIGsGIGs的一个子类是trGIGs，它通过要求pop规则在派生中至少引入一个终端符号，使pop和push规则统一。