ANTLR 규칙이 중첩 트리로 다시 작성됩니다.

중첩 트리로 다시 작성하는 규칙을 작성하려고합니다 (이진 트리와 유사). 예를 들어ANTLR 규칙이 중첩 트리로 다시 작성됩니다.

a + b + c + d;

는 (((a + b) + c) + d) 같은 트리에 구문 분석. 기본적으로 각 루트 노드에는 LHS가 더 중첩 된 노드가 될 수있는 세 개의 자식 (LHS '+'RHS)이 있습니다.

내가 좋아하는 몇 가지를 시도 : (일부 나무 재 작성 포함)

rule: lhs '+' ID; 
lhs: ID | rule;

및

rule 
    : rule '+' ID 
    | ID '+' ID;

하지만 그들은 모두가 왼쪽 재귀 것에 대해 나에게 오류를했다. 어떤 유형의 재귀없이이 문제를 해결하는 방법을 모르겠습니다.

편집 : 내가 원하는의 반대 제공 오른쪽에 내 최신 시도 재귀 :

rule: ID (op='+' rule)? -> {op == null}? ID -> ^(BinaryExpression<node=MyBinaryExpression> ID $op rule)

이 (a + (b + (c + d)))를 제공을

출처

2012-06-26 Nic Wolfe

. [이 질문] (http://stackoverflow.com/questions/1452729/antlr-grammar-for-expressions?rq=1)을 참조하십시오. 또는 트리 구문 분석기에서 문법에 따라 더 쉽고 빠를 수도 있습니다. –

'a + b'가 모두 자식 노드라면, 루트는 무엇입니까? 왜 당신은 운영자를 root로 원하십니까? –

루트 노드는 가상 노드입니다. 트리 구조는 내가 작업하고있는 요구 사항의 일부입니다. –

추시 문법 다음과 같이

grammar T; 

options { 
    output=AST; 
} 

tokens { 
    BinaryExpression; 
} 

parse 
: expr ';' EOF -> expr 
; 

expr 
: (atom -> atom) (ADD a=atom -> ^(BinaryExpression $expr ADD $a))* 
; 

atom 
: ID 
| NUM 
| '(' expr ')' 
; 

ADD : '+'; 
NUM : '0'..'9'+; 
ID : 'a'..'z'+; 
SPACE : (' ' | '\t' | '\r' | '\n')+ {skip();};

이 입력 "a + b + c + d;"을 구문 분석 : 당신은 ANTLR은 LL (*)가 있기 때문에 중첩 된 표현을 사용할 필요가

enter image description here

출처

2012-06-27 21:21:25

감사합니다. –

@NicWolfe. –

당신이

rule: ID '+' rule | ID;

을 시도 했습니까?

출처

2012-06-27 02:46:36 stryba

네, 그 나무는 제가 원하는대로 거꾸로 있습니다. '(a + (b + (c + d)))' –

ANTLR 규칙이 중첩 트리로 다시 작성됩니다.

답변

관련 문제