Antlr4正则表达式文法，NFA转换的数据结构table

Question

对于超长的解释，我深表歉意，但我现在被困了一个月，我真的不知道如何解决这个问题。作为一个项目，我必须派生一个带有 antlr4 的编译器，用于生成一个程序 (JAVA) 的正则表达式语法，该程序能够区分属于由用作 antlr4 编译器输入的正则表达式生成的语言的单词。我们必须使用的语法是这个：

RE ::= union | simpleRE
union ::= simpleRE + RE
simpleRE ::= concatenation | basicRE
concatenation ::= basicRE simpleRE
basicRE ::= group | any | char
group ::= (RE) | (RE)∗ | (RE)+
any ::= ?
char ::= a | b | c | ··· | z | A | B | C | ··· | Z | 0 | 1 | 2 | ··· | 9 | . | − | _

然后，我把这个语法给了 antrl4

Regexp.g4

grammar Regxp;

start_rule              
    : re                            # start
    ;

re
    :    union                      
    | simpleRE                      
    ;

union 
    :    simpleRE '+' re            # unionOfREs
    ;

simpleRE
    :    concatenation                      
    | basicRE                               
    ;

concatenation
    :    basicRE simpleRE                   #concatOfREs
    ;

basicRE
    :    group                      
    | any                               
    | cHAR                              
    ;


group
    :  LPAREN re RPAREN '*'             # star
    |  LPAREN re RPAREN '+'             # plus
    |  LPAREN re RPAREN                 # singleWithParenthesis
    ;


any
    :   '?'                             
    ;


cHAR
    : CHAR              #singleChar
    ;

WS : [ \t\r\n]+ -> skip ;
LPAREN : '(' ;
RPAREN : ')' ;
CHAR : LETTER | DIGIT | DOT | D | UNDERSCORE
    ;
/* tokens */
fragment LETTER:    [a-zA-Z]
    ;
fragment DIGIT: [0-9]
    ;
fragment DOT:  '.'
    ;
fragment D:  '-'
    ;
fragment UNDERSCORE: '_'
    ;

然后我从 antlr4 生成了 java 文件给访问者。据我了解项目的逻辑，当访问者遍历解析树时，它必须生成代码行来填充 NFA 的转换 table，因为在输入正则表达式上应用汤普森规则。然后将这些代码行保存为 .java 文本文件，并编译为接受输入字符串（单词）并判断该单词是否属于正则表达式生成的语言的程序。结果应该是这样的：

RE      word    Result
a+b       a       OK
          b       OK
         ac       KO

a∗b     aab       OK
         b        OK
       aaaab      OK
        abb       KO

所以我在问，我怎样才能以某种方式表示转换 table，以便它可以在访问解析树期间被填充，然后导出以便被简单的 java 实现 NFA 接受算法的程序？（我正在考虑这个伪代码）：

S = ε−closure(s0);
c = nextChar();
while (c ≠ eof) do
S = ε−closure(move(S,c));
c = nextChar();
end while
if (S ∩ F ≠ ∅) then return “yes”;
else return “no”;
end if

到目前为止，我设法做到了，例如，当访问者在 unionOfREs 规则中时，它将执行如下操作：

MyVisitor.java

private List<String> generatedCode = new ArrayList<String>();

/* ... */
@Override 
public String visitUnionOfREs(RegxpParser.UnionOfREsContext ctx) { 
    System.out.println("unionOfRExps");
    String char1 = visit(ctx.simpleRE());
    String char2 = visit(ctx.re());
    generatedCode.add("tTable.addUnion("+char1+","+char2+");");
    //then this line of code will populate the transition table
    return char1+"+"+char2;
}
/* ... */

addUnion 位于 java 文件中，该文件将包含填充转换 table 的所有方法。我为 union 写了代码，但我不喜欢它，因为它就像写 NFA 的转换 table，就像你在纸上写的那样：example。当我注意到通过迭代构建 table，您可以在 table、currentBeginning 和 currentEnd 上定义 2 "pointers" 时，我得到了这个，它告诉您在哪里再次展开写在table，以及访问者将在解析树上找到的下一条规则。因为这个角色可以是另一个作品，也可以只是一个角色。在 link 上，它代表了说服我使用这种方法的书面示例。

TransitionTable.java

/* ... */
public void addUnion(String char1, String char2) {
    if (transitionTable.isEmpty()) {
    List<List<Integer>> lc1 = Arrays.asList(Arrays.asList(null)
            ,Arrays.asList(currentBeginning+3)
            ,Arrays.asList(null)
            ,Arrays.asList(null)
            ,Arrays.asList(null)
            ,Arrays.asList(null));
    List<List<Integer>> lc2 = Arrays.asList(Arrays.asList(null)
            ,Arrays.asList(null)
            ,Arrays.asList(currentBeginning+4)
            ,Arrays.asList(null)
            ,Arrays.asList(null)
            ,Arrays.asList(null));
    List<List<Integer>> le = Arrays.asList(Arrays.asList(currentBeginning+1,currentBeginning+2)
            ,Arrays.asList(null)
            ,Arrays.asList(null)
            ,Arrays.asList(currentBeginning+5)
            ,Arrays.asList(currentBeginning+5)
            ,Arrays.asList(null));

        transitionTable.put(char1, lc1);
        transitionTable.put(char2, lc2);
        transitionTable.put("epsilon", le);
        //currentBeginning += 2;
        //currentEnd = transitionTable.get(char2).get(currentBeginning).get(0);
        currentEnd = transitionTable.get("epsilon").size()-1;//il 5
        } else { //not the first time it encounters this rule, beginning and end changed
            //needs to add 2 less states
        }
    }
/* ... */

目前我将转换 table 表示为 HashMap<String, List<List<Integer>>> 字符串用于 NFA 边缘的字符，而 List<List<Integer>> 因为它是非确定性的，所以它需要表示来自单个状态的更多转换。但是这样做，对于像 this 这样的解析树，我将为联合获得这行代码："tTable.addUnion("tTable.addConcat(a,b)","+char2+");"

我在这里被封锁了，我不知道如何解决这个问题，我真的想不出一种不同的方式来表示转换 table 或在访问解析树时填充它。

谢谢。

Answer 1

使用 Thompson 的构造，每个正则（子）表达式都会生成一个 NFA，并且每个正则表达式运算符（union、cat、*）都可以通过添加几个状态并将它们连接到已经存在的状态来实现。参见：

https://en.wikipedia.org/wiki/Thompson%27s_construction

因此，在解析正则表达式时，每个终端或 non-terminal 产生式都应将所需的状态和转换添加到 NFA，并且 return 将其开始和结束状态添加到包含产生式。 Non-terminal 产品将结合它们的 children 和 return 它们自己的开始+结束状态，以便您的 NFA 可以从正则表达式的叶子向上构建。

状态 table 的表示对于构建而言并不重要。 Thompson 的构建永远不会要求您修改之前构建的状态或转换，因此您只需要能够添加新的即可。您也永远不需要从同一角色的状态进行多次转换，甚至不需要一次以上的 non-epsilon 转换。事实上，如果你所有的运算符都是二进制的，你将永远不需要超过 2 个状态转换。通常，表示旨在使后续步骤变得容易，例如 DFA 生成或直接针对字符串执行 NFA。

比如像这样一个class就可以完全表示一个状态：

class State
{
    public char matchChar;
    public State matchState; //where to go if you match matchChar, or null
    public State epsilon1; //or null
    public State epsilon2; //or null
}

对于直接执行 NFA，这实际上是一个非常合理的表示。但是，如果您已经拥有直接执行 NFA 的代码，那么您可能应该只构建它使用的任何内容，这样您就不必进行其他转换。

Antlr4正则表达式文法，NFA转换的数据结构table

Antlr4 regular expression grammar, data structure for NFA transition table

java

antlr4