使用递归正则表达式在Java中进行Lexing

Question

我正在使用Java解析文本.我在下面定义了一个语法:

Start := "(\\<)"
Stop := "(\\>)"
Var = "(\\w*)";
Cons = "([0-9]*)";

Type1 := Start ((Var | Cons) | TypeParent) (Type1 ((Var | Cons) | TypeParent))* Stop
Type2 := Start ((Var | Cons) | TypeParent) (Type2 ((Var | Cons) | TypeParent))* Stop

TypeParent := Type1 | Type2

...
etc

我想将所有正则表达式组合成一个String模式并一次匹配.我的问题是当我开始在Type1和Type2行中使用递归语法元素时.我显然无法将递归定义提供给Java中的Pattern - 它只是一个带有正则表达式符号的String.

我想要的是,我可以以某种方式有一个逻辑开关,如果在这个块中:

(Type2 ((Var | Cons) | TypeParent)

所有模式都匹配,除了Type2,我可以捕获所有其他组,但然后提取Type2标记应该是的字符串,然后再次递归地将它提供给regexer.最后我会得到一个基本案例:

(Var | Cons) | TypeParent)

我意识到这不是正则表达式的意思 - 现在这是一个无上下文语法(？),因为它是递归的.但是,如果不考虑超级聪明的解析器,我认为这种方法是可以破解的.

思考？

Answer 1

你是对的.这不是正则表达式的意思.在你引入递归的那一刻,你就不在正则表达式,DFA之外,进入无上下文语言,DPDAs,解析器的领域.你需要一个堆栈来处理递归.不,它不是可以破解的.

对于这种语法,解析器没有什么"超级聪明".它比你到目前为止所做的要简单得多.