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