ANTLR4에서 상호 왼쪽 재귀를 수정하는 방법

Nov 13 2020

상호 재귀 적으로 남겨진 두 가지 규칙이 있습니다.

frag : ID
   | NUMBER
   | TRUE
   | FALSE
   | expr
;

expr: frag (PLUS | MINUS) frag
   | LBR expr RBR
   | frag
;

그리고 문제는 다음과 같습니다. The following sets of rules are mutually left-recursive [frag, expr]

나는 ANTLR4를 처음 사용 하며이 상호 왼쪽 재귀를 제거하는 데 어려움을 겪고 있습니다.

왼쪽 재귀는 다음과 같이 제거 될 수 있음을 이해합니다.

A -> Aa | b
-- becomes --
A -> bR
R -> aR | ε

여기에서이 답변 보기

어떻게해야합니까?

답변

2 BartKiers Nov 13 2020 at 13:24

간접 왼쪽 재귀는 허용되지 않지만 직접 왼쪽 재귀는 허용됩니다. 이것은 잘 작동합니다.

expr: expr (PLUS | MINUS) expr
   | LBR expr RBR
   | ID
   | NUMBER
   | TRUE
   | FALSE
;

그리고 여전히 별도의 frag규칙을 원한다면 다음과 같이 할 수 있습니다.

frag : ID
   | NUMBER
   | TRUE
   | FALSE
;

expr: expr (PLUS | MINUS) expr
   | LBR expr RBR
   | frag
;