왼쪽 연관 연산자가 하향식 LL (1) 파서가 이해할 수있는 방식으로 표현 될 수 있습니까?

Question

계산기 언어 용 LL (1) 하향식 파서를 구현하려고했습니다. 그것은 단지 합계, 빼기, 나누기 및 곱하기 수 있습니다. 괄호가 없습니다. 이 문법은 LL (1) 파서에 적합하지 않습니다으로

S -> A 

A -> B + A 
    | B - A 
    | B 

B -> int * B 
    | int/B 
    | int 

, 나는 그것을 아주 약간 수정했다 :

S -> A 

A -> B A' 
A'-> + A 
    | - A 
    | λ 

B -> int B' 
B'-> * B 
    |/B 
    | λ 

문제는 이제 문법이를 위해 왼쪽부터 결합되지 않는 것입니다 4 명의 연산자가 표시되어 있으므로 그렇게해야합니다. 이 문제를 해결하는 방법? 그렇게 할 수 있습니까?

Answer 1

재귀를 반복으로 바꾸면 왼쪽 연관성을 얻을 수 있습니다. 다음의 sort-of-pseudocode는 단순성을 위해 값을 직접 계산하지만 동일한 메소드를 사용하여 구문 분석 트리를 생성 할 수 있습니다.

function A() { 
    val = B(); 
    t = peek(); 
    while (t=='+' || t=='-') { 
    match(t); 
    val1 = B(); 
    if (t=='+') 
     val = val + val1; 
    else 
     val = val - val1; 
    t = peek(); 
    } 
    return(val) 
} 

peek() 그것을 먹는 않고 다음 토큰을 반환

및 match() 다음 토큰을 먹는다. B()에 대해서도 똑같은 일을 할 것입니다.