句法谓词

句法谓词指定在形式语法中应用生产的句法有效性，类似于指定应用生产的语义有效性的语义谓词。它是一种简单而有效的手段，通过提供任意的前瞻，极大地提高LL分析器的识别强度。在其最初的实现中，句法谓词的形式是"（α）？"，并且只能出现在生产的左边缘。所需的句法条件α可以是任何有效的无语境语法片段。更正式地说，句法谓词是生产交集的一种形式，在分析器规范或形式化语法中使用。在这个意义上，谓词具有数学指标函数的含义。如果p1和p2，是生产规则，由p1和p2产生的语言就是它们的集合交集。按照通常的定义或实现，句法谓词隐含着对生产的排序，因此在同一决定中，较早指定的谓词生产比较晚指定的谓词生产具有更高的优先权。这传达了一种消除歧义产品的能力，因为程序员可以简单地指定哪个产品应该匹配。由BryanFord发明的解析表达式语法（PEG）通过允许非谓语和允许谓语出现在生产中的任何地方来扩展这些简单的谓语。此外，Ford发明了packrat解析法，通过采用记忆化的方式在线性时间内处理这些语法，但要付出堆空间的代价。有可能支持像PEGs所允许的那样一般的谓词的线性时间解析，但是通过避免回溯来减少与记忆化相关的内存成本，在这种情况下，一些更有效的lookahead的实现就足够了。这种方法由ANTLR第3版实现，它使用确定性有限自动机进行查找；这可能需要测试一个谓词，以便在DFA的转换中进行选择（称为pred-LL(*)解析）。

句法谓词是由Parr&Quong创造的，它将这种形式的谓词与语义谓词（也有讨论）区分开来。句法谓词在各种文献中被称为多步骤匹配、解析约束和简单谓词。(见下面的参考文献部分。)本文自始至终使用句法谓词这个术语，以保持一致性并将其与语义谓词区分开来。形式上的封闭属性Bar-Hillel等人表明，两种正则语言的交集也是一种正则语言，也就是说，正则语言在交集下是封闭的。正则语言和无语境语言的交集也是封闭的，至少从Hartmanis开始就知道，两种无语境语言的交集不一定是无语境语言（因此也不是封闭的）。这一点可以用典型的xxx类语言轻易地证明。

在大多数使用句法谓词的形式主义中，谓词的句法是非交换性的，也就是说，谓词的操作是有序的。例如，使用上面的例子，考虑下面的伪语法，其中X::=YPREDZ被理解为：。

在必须首先满足Z的情况下，ANBN将无法生成aaabbb，因此aaabbbccc不会由语法生成。此外，如果Y或Z（或两者）指定了还原时要采取的任何行动（如许多分析器中的情况），这些产物的匹配顺序决定了这些副作用的发生顺序。随时间变化的形式主义（如自适应语法）可能依赖于这些副作用。