ANTLR 4语义谓词

发表于 | 分类于 |

1 语义谓词

语义谓词是使用目标语言编写的布尔表达式，表示沿谓词“保护”路径继续进行语法分析的有效性。

可以像动作一样出现在任意位置，但是只有出现在选项左边缘的谓词才能影响预测（在选项间选择）。

2 解析决策

通常决策策略是选择最先匹配且预测为true的选项。

如下匹配C++中的数组引用的：

1
2
3
4
expr: ID '(' expr ')' // array reference (ANTLR picks this one)
 	| {istype()}? ID '(' expr ')' // ctor-style typecast
 	| ID '(' expr ')' // function call
 	;

对于输入x(i)，3个选项都会匹配。但是按照顺序，最终只取第一个。此外，对于不是类型名称的x，不会匹配第二个选项。

建议针对n个选项，配备n-1个谓词。

单一选项具有多个谓词时，会合并相关的语义。如：

1
2
3
4
5
stat: decl | expr ;
decl: ID ID ;
expr: {istype()}? ID '(' expr ')' // ctor-style typecast
 	| {isfunc()}? ID '(' expr ')' // function call
 	;

规则stat会合并expr的条件，生成istype()||isfunc()。

如果在一个序列中连续出现了多个谓词，则使用&&连接谓词。如以下示例将产生java5&&(istype()||isfunc())

1
stat: decl | {java5}? expr ;

当没有可选项时，将抛出异常。

如：

1
prog: {false}? 'return' INT ; // throws FailedPredicateException

在解析器中将增加条件：

1
if ( !false ) throw new FailedPredicateException(...);

3 查找可见谓词

到目前为止，使用的谓词都是可见且可用于谓词处理的，但是事实不止于此。

解析器不会评估出现在动作或记号引用后的谓词。

ANTLR必须在决定采用哪个规则选项后再执行动作。因为动作可能对谓词产生意外的影响，或者不可撤销的影响，如打印操作等。

如下示例不能在谓词前执行动作：

1
2
3
4
@members {boolean allowgoto=false;}
stat: {System.out.println("goto"); allowgoto=true;} {java5}? 'goto' ID ';'
 	| ...
 	;

同样，不能在谓词前使用记号引用，因为记号引用会导致匹配下标后移。

如下示例期望getCurrentToken返回记号ID，但谓词并不会

1
2
3
4
5
stat: '{' decl '}'
 	| '{' stat '}'
 	;
decl: {istype(getCurrentToken().getText())}? ID ID ';' ;
expr: {isvar(getCurrentToken().getText())}? ID ;

在stat中引用了记号{，导致了谓词不能测试。

可见谓词是指在动作或记号引用前出现的谓词。对于不可见谓词将直接忽略。

在少数场景中，即使可见谓词也不能使用。详见下方。

4 上下文依赖谓词

上下文依赖谓词是指依赖规则中的参数或本地变量的谓词。

ANTLR会忽略不在当前规则范围内的上下文依赖谓词。甚至有时即使在同一规则内也会被无法评估。检测发生在Adaptive LL(*) Prediction阶段。

如下：

1
2
3
4
5
6
prog: stat+ ; // stat can follow stat
stat
locals [int i=0]
 	: {$i==0}? 'if' expr 'then' stat {$i=5;} ('else' stat)?
 	| 'break' ';'
 	;

?The prediction process is trying to figure out what can follow an if statement other than an else clause. Since the input can have multiple stats in a row, the prediction for the optional branch of the else subrule reenters stat. This time, of course, it gets a new copy of $i with a value of 0, not 5. ANTLR ignores context-dependent predicate {$i==0}? because it knows that the parser isn’t in the original stat call. The predicate would test a different version of $i so the parser can’t evaluate it.

5 词法规则中的谓词

与解析器中谓词必须出现在选项左边不同，在词法器中倾向于出现在右边，因为可以在找到记号文本后选择规则。

词法器中的谓词理论上可以出现在任意位置。

词法器中的谓词即使在单一匹配中也可能被执行多次。

简单的说，词法器的目的是选择与输入字符最匹配的规则。对于每一个字符，词法器可以决定哪些规则可见。但最终只有一个可见的规则，词法器根据这个规则构建记号对象。

词法解析器匹配第一个适配的规则，因此需要将关键规则放置在识别规则之前。

1
2
ENUM : 'enum' ;
ID : [a-z]+ ;

由于词法规则适配可能受到动作影响，词法规则应该放置在动作之前。

1
2
3
4
ENUM: [a-z]+ {getText().equals("enum")}?
	   {System.out.println("enum!");}
    ;
ID  : [a-z]+ {System.out.println("ID "+getText());} ;

参考资料