재귀 적 정규식을 사용하여 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 

모든 정규식을 단일 문자열 패턴으로 결합하여 한 번에 모두 일치 시키려고합니다. 내 문제는 Type1 및 Type2 행의 재귀 문법 요소를 사용하기 시작할 때입니다. 분명히 재귀 적 정의를 Java의 Pattern으로 공급할 수는 없습니다. 정규 표현식 기호가있는 문자열 일뿐입니다. 내가 좋아하는 것 무엇

내가 어떻게 든 말했다 논리적 스위치를 가질 수 있다는 것입니다 그 경우이 블록 :

(Type2 ((Var | Cons) | TypeParent) 

모든 패턴이, 나는 다른 모든 그룹을 캡처 할 수, 타입 2를 제외하고 일치하고 있지만, Type2 토큰이 있어야하는 문자열을 추출한 다음 재귀 적으로 regexer에 다시 입력하십시오. 결국 나는의 기본 케이스에 내려 것 : - (?)

(Var | Cons) | TypeParent) 

나는이 할 무엇을 의미하는지 정규식 아니라고 실현이 이제 문맥 자유 문법이 순환하기 때문에입니다. 그러나 슈퍼 영리한 파서에 대한 생각이 부족한이 방법은 해킹이 가능하다고 생각합니다.

생각하십니까?

Answer 1

정확합니다. 이것은 정규식이 의도 한 것이 아닙니다. 재귀를 도입하는 순간 정규 표현식, DFA 및 문맥이없는 언어, DPDA, 파서의 땅으로 빠져 나옵니다. 재귀를 처리하려면 스택이 필요합니다. 아니요, 해킹 할 수 없습니다.

이 문법에 대한 파서는 '초능력'이 아닙니다. 지금까지 해 온 것보다 훨씬 간단합니다.

Answer 2

작업에 적합한 도구를 사용하는 것이 훨씬 쉽습니다. CUP, ANTLR 또는 JavaCC을 사용해보십시오. 다음은 ANTLR example입니다.