ANTLR의 트리 파서란 무엇이며 강제로 작성해야 합니까?

StackOverflow https://stackoverflow.com/questions/697755

문제

저는 Java 환경에서 실행될 ANTLR의 C의 작은 하위 집합에 대한 어휘 분석기/파서를 작성하고 있습니다.저는 언어 문법의 세계를 처음 접했고 많은 ANTLR 튜토리얼에서 AST(추상 구문 트리)를 만듭니다. 강제로 만들어야 하나요? 그 이유는 무엇입니까?

도움이 되었습니까?

해결책 2

나는 찾았다 이 답변 ANTLR을 만든 Terence Parr가 작성한 jGuru에 대한 질문에 대한 답변입니다.이 설명은 링크된 사이트에서 복사했습니다 여기:

구문 분석기 내의 작업으로는 간단한 소위 구문 지정 번역만 수행할 수 있습니다.이러한 종류의 번역은 구문 분석의 해당 시점에 이미 표시된 정보의 기능인 구성만 뱉어낼 수 있습니다.트리 파서를 사용하면 중간 형식을 탐색하고 해당 트리를 조작하여 여러 번역 단계를 거쳐 점차적으로 새 번역으로 다시 쉽게 인쇄할 수 있는 최종 형식으로 변형할 수 있습니다.

제목이 "n개의 항목이 있습니다"인 HTML 페이지를 인쇄하려는 간단한 번역 문제를 상상해 보십시오. 여기서 n은 입력 스트림에서 찾은 식별자의 수입니다.ID는 다음과 같이 제목 뒤에 인쇄되어야 합니다.

<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>

입력에서

Dog
Cat
Velociraptor

그렇다면 문법의 간단한 동작을 사용하여 제목을 어떻게 계산할 수 있습니까?전체 입력을 읽지 않고는 할 수 없습니다.자, 이제 중간 양식이 필요하다는 것을 알았습니다.가장 좋은 것은 일반적으로 입력 구조를 기록하기 때문에 제가 찾은 AST입니다.이 경우에는 단지 목록일 뿐이지만 내 요점을 보여줍니다.

좋아, 이제 당신은 트리가 단순한 번역 이외의 어떤 것에도 좋은 것이라는 것을 알았습니다.AST가 주어지면 출력을 어떻게 얻나요?간단한 표현식 트리를 상상해 보세요.한 가지 방법은 PlusNode, IntegerNode 등과 같은 트리 특정 클래스의 노드를 만드는 것입니다.그런 다음 각 노드에 자체적으로 인쇄하도록 요청하면 됩니다.입력의 경우 3+4 트리가 생성됩니다.

+ | 3 -- 4

그리고 수업

class PlusNode extends CommonAST {
  public String toString() {
    AST left = getFirstChild();
    AST right = left.getNextSibling();
    return left + " + " + right;
  }
}

class IntNode extends CommonAST {
  public String toString() {
    return getText();
  }
}

표현식 트리가 주어지면 t.toString()을 사용하여 이를 다시 텍스트로 변환할 수 있습니다.그래서, 이게 뭐가 문제야?정말 잘 되는 것 같죠?이 경우에는 간단하기 때문에 잘 작동하는 것처럼 보이지만, 이 간단한 예에서도 트리 문법은 더 읽기 쉽고 PlusNode.toString()에서 코딩한 내용에 대한 형식화된 설명이라고 주장합니다.

expr returns [String r]
{
    String left=null, right=null;
}

: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT                       {r=i.getText();}
;

특정 클래스("이기종 AST") 접근 방식은 실제로 toString()에서 #(+ INT INT)에 대한 완전한 재귀 하강 파서를 직접 인코딩합니다.파서 생성기 사용자로서 이것이 당신을 움츠러들게 만들 것입니다.;)

이기종 AST 접근 방식의 주요 약점은 컨텍스트 정보에 편리하게 액세스할 수 없다는 것입니다.재귀 하향식 파서에서는 컨텍스트를 매개변수로 전달할 수 있으므로 컨텍스트에 쉽게 액세스할 수 있습니다.또한 문법을 ​​살펴보면 어떤 규칙이 다른 규칙을 호출할 수 있는지(예: 이 표현식이 WHILE 조건인지 IF 조건인지) 정확하게 알 수 있습니다.위의 PlusNode 클래스는 누가 toString() 메서드를 호출할지 전혀 알 수 없는 분리되고 고립된 세계에 존재합니다.더 나쁜 것은 프로그래머가 그것을 읽어서 어떤 컨텍스트에서 호출되는지 알 수 없다는 것입니다.

요약하면, 입력 파서에 작업을 추가하면 다음과 같은 매우 간단한 번역이 가능합니다.

  1. 출력 구성의 순서는 입력 순서와 동일합니다.
  2. 모든 구성은 사용자가 뱉어내야 하는 시점까지 구문 분석된 정보에서 생성될 수 있습니다.

이 외에도 중간 형식이 필요합니다. 일반적으로 AST가 가장 좋은 형식입니다.문법을 사용하여 AST의 구조를 설명하는 것은 문법을 사용하여 입력 텍스트를 구문 분석하는 것과 유사합니다.ANTLR과 같은 도메인별 고급 언어로 형식화된 설명이 직접 코딩된 파서보다 낫습니다.트리 문법 내의 작업은 매우 명확한 컨텍스트를 가지며 rlues 호출에서 전달된 정보에 편리하게 액세스할 수 있습니다.멀티패스 번역을 위해 트리를 조작하는 번역도 트리 문법을 사용하면 훨씬 쉽습니다.

다른 팁

Antlr을 사용하여 AST를 만드는 것은 문법에 통합됩니다. 이 작업을 수행 할 필요는 없지만보다 복잡한 요구 사항에 대한 좋은 도구입니다. 이것은 지도 시간 나무 구조에서 사용할 수 있습니다.

기본적으로 소스가 구문 분석되면 Antlr을 사용하면 몇 가지 옵션이 있습니다. 문법에서 다시 쓰기 규칙을 사용하여 코드 또는 AST를 생성 할 수 있습니다. an ast 기본적으로 소스의 메모리 표현입니다. 거기에서 당신이 할 수있는 일이 많이 있습니다.

Antlr에는 많은 것이 있습니다. 당신이 아직하지 않았다면, 나는 얻는 것이 좋습니다 그 책.

나는 창조를 생각한다 ast 선택 사항입니다. 그만큼 초록 구문 트리 구문 분석 프로그램의 시맨틱 분석과 같은 후속 처리에 유용합니다.

당신만이 만들어야하는지 결정할 수 있습니다. 유일한 목표가 구문 검증이라면 하나를 생성 할 필요가 없습니다. ~ 안에 Javacc (antlr과 유사) a 공익사업 ~라고 불리는 jjtree 그것은 AST의 생성을 허용합니다. 그래서 나는 이것이 ANTLR에서도 선택 사항이라고 생각합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top