토큰 스트림을 구문 분석 트리로 바꾸는 방법 [폐쇄

Question

입력에서 토큰을 스트리밍하는 Lexer 빌드가 있지만 프로세스의 다음 단계 인 Parse Tree를 구축하는 방법을 잘 모르겠습니다. 누구든지 이것을 달성하는 방법에 대한 좋은 자원이나 사례가 있습니까?

Answer 1

정말 추천합니다 http://www.antlr.org/ 물론 클래식 드래곤 컴파일러 책.

JavaScript와 같은 쉬운 언어의 경우 재귀적인 하강 파서를 손으로 굴리는 것은 어렵지 않지만 YACC 또는 AntlR과 같은 도구를 사용하는 것은 거의 항상 쉽습니다.

나는 당신의 질문의 기본 사항을 뒤로 물러나고 있다고 생각합니다. 당신은 정말로 BNF-esque 문법 구문에 대해 공부하고 목표에 대한 구문을 선택하고 싶습니다. 당신이 그것을 가지고 있다면, 구문 분석 트리는 그 문법의 '인스턴스'표현이어야합니다.

또한, 구문 분석 트리의 생성을 최종 솔루션으로 바꾸려고하지 마십시오 (코드 생성 등). 가능하고 더 효과적인 것처럼 보일 수 있습니다. 그러나 항상 당신이 '주위에 누워있는 그 구문 분석'을 원했던 시간이 올 때가 올 것입니다.

Answer 2

플랫폼의 파서 생성기 도구를 조사해야합니다. 파서 생성기를 사용하면 언어에 대한 컨텍스트없는 문법을 지정할 수 있습니다. 언어는 일련의 기호를 새로운 기호로 "감소시키는"여러 규칙으로 구성됩니다. 일반적으로 언어의 모호성을 제거하기 위해 다른 규칙에 대한 우선 순위와 연관성을 지정할 수 있습니다. 예를 들어, 매우 간단한 계산기 언어는 다음과 같이 보일 수 있습니다.

%left PLUS, MINUS           # low precedence, evaluated left-to-right
%left TIMES, DIV            # high precedence, left-to-right

expr ::= INT
| expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIV expr
| LEFT_PAREN expr RIGHT_PAREN

일반적으로 각 규칙과 약간의 코드를 연결하여 해당 규칙의 다른 기호로부터 새 값 (이 경우 표현식)을 구성 할 수 있습니다. 파서 생성기는 문법을 가져 와서 토큰 스트림을 구문 분석 트리로 변환하는 언어로 코드를 생성합니다.

대부분의 파서 생성기는 언어에 따라 다릅니다. ANTLR은 잘 알려져 있으며 C, C ++, 목표 C, Java 및 Python을 지원합니다. 그래도 사용하기 어렵다고 들었습니다. 나는 C/C ++ 용 Bison, Java 용 Cup 및 Ocaml의 OcamlyAcc를 사용했으며 모두 꽤 좋습니다. Lexer 생성기를 이미 사용하고 있다면 구체적으로 호환되는 파서 생성기를 찾아야합니다.

Answer 3

나는 일반적인 접근 방식이 유한 상태 기계. 예를 들어 피연산자를 읽는 경우 다음에 연산자를 기대하는 상태로 이동하고 일반적으로 오퍼레이터를 피연산자 등의 루트 노드로 사용합니다.

Answer 4

BNF의 언어 규칙을 사용하여 토큰 목록을 구문 분석하는 주 머신 인 Marcos Marin이 위에서 설명한 것처럼 직접 수행하려면 트릭을 수행합니다. Paul Hollingsworth의 위의 논평에서 언급 한 바와 같이, 더 쉬운 방법은 푸시 다운 -automaton 간단한 FIFO 메모리 스택이 있습니다. 모든 클래스의 토큰에는 문법에 다음으로 예상되는 토큰이 있으며, 이는 주 머신에도 표시됩니다. 이 스택은 이전 토큰 클래스가 필요한 상태를 "기억"하는 데 사용됩니다 (필요한 상태를 줄이기 위해 (스택없이 수행 할 수 있지만, 모든 클래스에 새로운 상태가 필요하고 문법 트리의 서브 클래스 분할이 필요합니다). 수락 상태는 (자연 언어 및 대부분의 프로그래밍 언어로도), 특히 다른 상태 일 것입니다.

antlr 도구를 사용하려면 내 제안이 될 것입니다 (더 빠르고 덜 광범위한). 행운을 빕니다!