TL 하강 기반, DR을 :재귀 계산기 스택 오버플로
내 계산기 문법 둥지 재귀 하강에 의존 서로 내에서 그룹을 괄호 만 (20 정도) 너무 많은 중첩 된 괄호는 스택 오버 플로우가 발생합니다. 이 문제를 어떻게 해결할 수 있습니까? 문제를보다 평평하게 만드는 방법이 있습니까?
장편 :
그것은 오래 전에 그 아니었다 - 나의 머리는 작은 규모의 임베디드 시스템에 깊이 갇혀 - 아니 사람을 반 두뇌와 스택 오버플로 실행해야합니다. 이제는 훨씬 추상적 인 작업으로 인해 겸손 해지고, 나는 여기에 조언을 구한다.
동기 부여 프로젝트는 Android 용 계산기입니다. 현재의 계산기는 여러 가지면에서 눈부신 정도로 부족하지만, 오늘 내 soapbox를 가져 오지 않았으므로, 지금 막 나와있는 문제에 직면하게 될 것입니다 : 스택 오버플로!
특히 사용자가 함수 등을 포함하여 너무 많은 중첩 된 괄호 그룹을 만드는 경우 이것은 계산기가 ANTLR 문법에 의존하기 때문에 발생합니다. 즉, 재귀 적 디센트를 사용한다는 의미입니다. 편리하게, 이것은 PEMDAS를 통해 지속적으로 실행되어 중첩 된 함수와 괄호를 쉽게 계산할 수있게합니다. 그러나! 나는 전화에 따라 - 괄호 버튼을 20 번 누르는 것은 재귀 적 강하 방법의 자연스런 결과 인 약 100 개의 함수 호출에 대한 콜 스택에서 발생하는 스택 오버플로로 인한 크래시를 유발한다는 것을 알았다.
플랫은 중첩 된 것보다 낫지 만, 아래로 내려가는 레벨 (함수) 중 4 개가 완전히 필요하며 다른 몇 레벨은 내 생애를 대수적으로 쉽게 만듭니다. 이러한 레벨을 제거해도 문제가 해결되지는 않습니다. 사용자는 몇 분 내에 시스템을 중단시킬 수 있습니다. "너무 많은 팸!" 오류 메시지가 잘못되었습니다 (다른 계산기 중 하나가하는 것임). 또한 AST 출력을 사용하여 입력 문자열을 형식화하여 꽤 비슷하게 만들었으므로 괄호 그룹을 사전 계산하면 전체 시스템을 약간 복잡하게 만들 수 있습니다.
그래서, 질문 :
에도이 질문은 바보 같다,하지만 질문 : 구문 분석하고 호출 스택 폭발하지 않고 복잡하고 중첩 표현을 해석 할 수 ANTLR의 문법을 구현하는 방법이?
문법 :
grammar doubleCalc;
options {
language = Java;
output = AST;
// k=2;
}
// Calculation function.
prog returns [double value]
: e=addsub EOF {$value = $e.value;}
;
addsub returns [double value]
: e=muldiv {$value = $e.value;}
( PLUS^ e=muldiv {$value += $e.value;}
| MINUS^ e=muldiv {$value -= $e.value;}
)*
;
muldiv returns [double value]
: e=power {$value = $e.value;}
( MUL^ e=power {$value *= $e.value;}
| DIV^ e=power {$value /= $e.value;}
)*
;
power returns [double value]
: e = negate {$value = $e.value;}
( POW^ f=power {$value = java.lang.Math.pow($value, $f.value);}
)?
;
negate returns [double value]
: ( MINUS^ neg = atom {$value = -$neg.value;}
| neg = atom {$value = $neg.value;}
)
;
atom returns [double value]
: LOG10^ '(' e=addsub ')' {$value = java.lang.Math.log10($e.value);}
| LOG8^ '(' e=addsub ')' {$value = java.lang.Math.log10($e.value)/java.lang.Math.log10(8.0);}
| LOG2^ '(' e=addsub ')' {$value = java.lang.Math.log10($e.value)/java.lang.Math.log10(2.0);}
| LN^ '(' e=addsub ')' {$value = java.lang.Math.log($e.value);}
| ASIN^ '(' e=addsub ')' {$value = Math.asin(Math.PI*(($e.value/Math.PI) \% 1));}//com.brogramming.HoloCalc.Trig.asin($e.value);}
| ACOS^ '(' e=addsub ')' {$value = Math.acos(Math.PI*(($e.value/Math.PI) \% 1));}
| ATAN^ '(' e=addsub ')' {$value = Math.atan(Math.PI*(($e.value/Math.PI) \% 1));}
| SIN^ '(' e=addsub ')' {$value = Math.sin(Math.PI*(($e.value/Math.PI) \% 1));}
| COS^ '(' e=addsub ')' {$value = Math.cos(Math.PI*(($e.value/Math.PI) \% 1));}
| TAN^ '(' e=addsub ')' {$value = Math.tan(Math.PI*(($e.value/Math.PI) \% 1));}
| ASIND^ '(' e=addsub ')' {$value = Math.asin(Math.PI*(($e.value/180f) \% 1));}//com.brogramming.HoloCalc.Trig.asin($e.value);}
| ACOSD^ '(' e=addsub ')' {$value = Math.acos(Math.PI*(($e.value/180f) \% 1));}
| ATAND^ '(' e=addsub ')' {$value = Math.atan(Math.PI*(($e.value/180f) \% 1));}
| SIND^ '(' e=addsub ')' {$value = Math.sin(Math.PI*(($e.value/180f) \% 1));}
| COSD^ '(' e=addsub ')' {$value = Math.cos(Math.PI*(($e.value/180f) \% 1));}
| TAND^ '(' e=addsub ')' {$value = Math.tan(Math.PI*(($e.value/180f) \% 1));}
| SQRT^ '(' e=addsub ')' {$value = (double) java.lang.Math.pow($e.value, 0.5);}
| CBRT^ '(' e=addsub ')' {$value = (double) java.lang.Math.pow($e.value, 1.0/3.0);}
| ABS^ '(' e=addsub ')' {$value = (double) java.lang.Math.abs($e.value);}
// Numbers
| n = number {$value = $n.value;}
| '(' e=addsub ')' {$value = $e.value;}
;
number returns [double value]
: PI {$value = java.lang.Math.PI;}
| EXP {$value = java.lang.Math.E;}
| INT {$value = (double) Double.parseDouble($INT.text.replaceAll(",", ""));}
| DOUBLE {$value = Double.parseDouble($DOUBLE.text.replaceAll(",", ""));}
;
LN : 'ln';
LOG10 : 'log10';
LOG8 : 'log8';
LOG2 : 'log2';
SIN : 'sin';
COS : 'cos';
TAN : 'tan';
ASIN : 'asin';
ACOS : 'acos';
ATAN : 'atan';
SINH : 'sinh';
COSH : 'cosh';
TANH : 'tanh';
ASINH : 'asinh';
ACOSH : 'acosh';
ATANH : 'atanh';
SIND : 'sind';
COSD : 'cosd';
TAND : 'tand';
ASIND : 'asind';
ACOSD : 'acosd';
ATAND : 'atand';
SINHD : 'sinhd';
COSHD : 'coshd';
TANHD : 'tanhd';
ASINHD : 'asinhd';
ACOSHD : 'acoshd';
ATANHD : 'atanhd';
PI : 'pi';
IM : 'i';
EXP : 'e';
ABS : 'abs';
FACT : 'fact';
SQRE : 'sqre';
CUBE : 'cube';
SQRT : 'sqrt';
CBRT : 'cbrt';
POW : '^';
PLUS : '+';
MINUS : '-';
MUL : ('*');
DIV : '/';
BANG : '!';
DOUBLE: ('0'..'9' | ',')+ '.'('0'..'9')* ;
INT : ('0'..'9' | ',')+ ;
NEWLINE:'\r'? '\n' ;
PERCENT
: '%';
EOF : '<EOF>' {$channel=HIDDEN;};
나는 이것이 스택 오버플로에 대한 스택 오버플로와 관련된 질문을 본 첫 번째라고 생각합니다. :) – vijay