如何解决歧义

Question

我有一个语法：

grammar Test;

s      : ID OP (NUMBER | ID);

ID     : [a-z]+ ;
NUMBER : '.'? [0-9]+ ;

OP     : '/.' | '/' ;
WS     : [ \t\r\n]+ -> skip ;

像 x/.123 这样的表达式既可以解析为 (s x /. 123)，也可以解析为 (s x / .123)。通过上面的语法，我得到了第一个变体。

有没有办法得到两个解析树？有没有办法控制它的解析方式？比如说，如果 /. 之后有一个数字，那么我会发出 / 否则我会在树中发出 /.。

我是 ANTLR 新手。

Answer 1

An expression like x/.123 can either be parsed as (s x /. 123), or as (s x / .123)

我不确定。在 ReplaceAll 页面 (*)，可能的问题段落中，据说 "Periods bind to numbers more strongly than to slash"，因此 /.123 将始终被解释为数字 .123 的除法运算。接下来据说为了避免这个问题，如果你想让它被理解为替换，必须在 /. 运算符和数字之间的输入中插入 space。

所以只有一棵可能的解析树（否则 Wolfram 解析器如何决定如何解释语句？）。

ANTLR4 词法分析器和解析器是贪婪的。这意味着词法分析器（解析器）在匹配规则时会尝试读取尽可能多的输入字符（标记）。使用您的 OP 规则 OP : '/.' | '/' ;，词法分析器将始终将输入 /. 与 /. 替代项匹配（即使规则是 OP : '/' | '/.' ;）。这意味着没有歧义，您没有机会将输入解释为 OP=/ 和 NUMBER=.123.

鉴于我对 ANTLR 的一些经验，除了将 ReplaceAll 运算符拆分为两个标记之外，我没有找到其他解决方案。

语法题.g4 :

grammar Question;

/* Parse Wolfram ReplaceAll. */

question
@init {System.out.println("Question last update 0851");}
    :   s+ EOF
    ;

s   :   division
    |   replace_all
    ;

division
    :   expr '/' NUMBER
        {System.out.println("found division " + $expr.text + " by " + $NUMBER.text);}
    ;

replace_all
    :   expr '/' '.' replacement
        {System.out.println("found ReplaceAll " + $expr.text + " with " + $replacement.text);}
    ;

expr
    :   ID
    |   '"' ID '"'
    |   NUMBER
    |   '{' expr ( ',' expr )* '}'
    ;

replacement
    :   expr '->' expr    
    |   '{' replacement ( ',' replacement )* '}'
    ;

ID     : [a-z]+ ;
NUMBER : '.'? [0-9]+ ;
WS     : [ \t\r\n]+ -> skip ;

输入文件t.text:

x/.123
x/.x -> 1
{x, y}/.{x -> 1, y -> 2}
{0, 1}/.0 -> "zero"
{0, 1}/. 0 -> "zero"

执行：

$ export CLASSPATH=".:/usr/local/lib/antlr-4.6-complete.jar"
$ alias a4='java -jar /usr/local/lib/antlr-4.6-complete.jar'
$ alias grun='java org.antlr.v4.gui.TestRig'
$ a4 Question.g4 
$ javac Q*.java
$ grun Question question -tokens -diagnostics t.text 
[@0,0:0='x',<ID>,1:0]
[@1,1:1='/',<'/'>,1:1]
[@2,2:5='.123',<NUMBER>,1:2]
[@3,7:7='x',<ID>,2:0]
[@4,8:8='/',<'/'>,2:1]
[@5,9:9='.',<'.'>,2:2]
[@6,10:10='x',<ID>,2:3]
[@7,12:13='->',<'->'>,2:5]
[@8,15:15='1',<NUMBER>,2:8]
[@9,17:17='{',<'{'>,3:0]
...
[@29,47:47='}',<'}'>,4:5]
[@30,48:48='/',<'/'>,4:6]
[@31,49:50='.0',<NUMBER>,4:7]
...
[@40,67:67='}',<'}'>,5:5]
[@41,68:68='/',<'/'>,5:6]
[@42,69:69='.',<'.'>,5:7]
[@43,71:71='0',<NUMBER>,5:9]
...
[@48,83:82='<EOF>',<EOF>,6:0]
Question last update 0851
found division x by .123
found ReplaceAll x with x->1
found ReplaceAll {x,y} with {x->1,y->2}
found division {0,1} by .0
line 4:10 extraneous input '->' expecting {<EOF>, '"', '{', ID, NUMBER}
found ReplaceAll {0,1} with 0->"zero"

输入 x/.123 在斜线之前是不明确的。然后解析器有两个选择：除法规则中的 / NUMBER 或 replace_all 规则中的 / . expr。我认为 NUMBER 吸收了输入，因此不再有歧义。

(*) link 昨天在一条评论中消失了，即 Wolfram Language & System, ReplaceAll

如何解决歧义

how to resolve an ambiguity

antlr

antlr4