자바에서 컵 파서와 같은 프로젝트 종속성이나 도구없이 처음부터 추상 구문 트리를 작성하여 정규 표현식에 대한 파서를 작성하려고합니다. 나는 정규식에 포함 된 모든 정보를 저장하고 싶지 않지만 대신 가능한 한 간단하게하고 싶다.정규식의 최적 AST를 작성하는 방법은 무엇입니까?
예를 들어, x::=y|z은 문자 클래스 x::=[yz]과 동일한 AST로 이어져야합니다. 그러나 정규 표현식은 매우 복잡 할 수 있기 때문에 구현할 동등성을 결정할 수는 없습니다. 예를 들어, 부정적인 선택을 저장하는 방법을 모르겠다. x::=a|c|d|e|...
어떤 추상화를 내겠습니까? 그러한 추상화 중 일부가 나중에 잘못된 AST로 이어질 수 있습니까?
AST는 특정 프로그램 (OP의 경우 "정규식") 구문을 구문 분석합니다. 일반적으로 AST는 입력 프로그램의 특정 분해를 기록하는 실제 구문 분석 트리에서 파생됩니다.
OP는 캐릭터 클래스와 똑같이 문자를 교대로 나타내는 AST를 원합니다. 그는 특정 구문 분석과 "동등한"또는 "표준"양식을 혼동하는 것으로 보입니다.
일반적으로 구문 분석 트리가 서로 다른 입력 문자열이 다를 수 있으며 분해가 표준화되면 동일한 AST가있을 수 있습니다. 항상 그렇게 쉬운 것은 아닙니다. 쉬운 부분 (OP의 예는 그 중 하나입니다)을 발견 할 수 있습니다.이 부분에서는 언어의 일부에 대해 표준 형식을 정의하고 해당 구문을 표준 형식으로 강제 할 수 있습니다. 일반적으로 임의의 동등한 것으로부터 표준을 생성 할 수 있다고 보장 할 수있는 것은 아닙니다.
또는 OP가 하나의 질문을 선택하려고 시도 했으므로 다음과 같이 생각할 수 있습니다. [^ x]을 127 ASCII 대안으로 명시하는 것이 더 좋습니다. [^ < 63 characters>]에서 무엇을 선택해야합니까? [^ < 64 자>]? [^ < 65 자]? 아마 유니 코드의 [^ x] 표현은 어쩌면 2^24 문자입니까?
실용적인 문제로서, 나는 그가 구문 분석 트리 및/또는 그 구문 분석 트리에 해당하는 모든 AST를 생성한다는 것을 OP에 제안합니다. 그런 다음 AST를 표준 형식으로 표준화하려고 시도 할 수는 있지만 이것이 별개의 단계로 유지되는 것이 가장 좋습니다.
문자 클래스를 별도로 유지해야합니다. 이것을 고려하십시오 : 유니 코드는 120k 이상의 문자를 정의합니다. 그래서'[^ b]'는 약 120,000 명의 멤버와 교대로 나타납니다. 그것은 AST에 좋지 않습니다. –