좌측 연관성 대 왼쪽 재귀

Question

저는 C (더 간단한 문법) 용 컴파일러를 작성하려고합니다.

내가 잠시 머물러있는 것이 있습니다. 필자가 정확하게 말하면, 모든 이진 연산은 연관성을 유지합니다. 그래서 우리가 "x + y + z"를 가지면 x + y가 먼저 발생하고 그 다음에 z가 더해진다.

그러나 왼쪽 결합을 강제하지 않으면 무한 왼쪽 재귀가 발생합니까?

지금까지 확인한 모든 솔루션은 연관성이 왼쪽이거나 재귀가 남아 있지 않지만 은 모두이 아닙니다. 두 가지 속성을 모두 갖춘 문법을 사용할 수 있습니까? 심지어 가능할까요?

예 :

왼쪽 연관 :

Expr = Term | Expr + Term 
Term = Element | Term ∗ Element 
Element = x|y|z|(Expr) 

왼쪽 재귀는 탈락 :

Expr = Term ExprTail 
ExprTail = epsilon | + Term ExprTail 

Term = Element TermTail 
TermTail = epsilon | * Element TermTail 

Element = x|y|z|(Expr) 

어떤 아이디어?

Answer 1

연산자가 왼쪽 연관 형인 경우 해당 프로덕션은 재귀 적으로 남아 있습니다.

LR 파서 생성기를 사용하는 경우 문제가 없습니다. LR 알고리즘은 왼쪽 재귀를 다루는 데 아무런 문제가 없습니다 (약간의 스택 공간이 필요할지라도 다른 종류의 재귀에는 거의 문제가 없습니다).

기존 연산자 우선 순위 알고리즘 (shunting yard)과 같은 다른 상향식 기법을 사용할 수도 있지만 LR 구문 분석은 표현력이 풍부하고 구문 분석기는 구현을 비교적 간단하게 만듭니다.

반복적 인 하향 파싱을 주장하면 루프를 사용하여 반복적 인 패턴을 구문 분석 할 수 있기 때문에 (이론적으로는 재귀적임) 요소가 왼쪽에서 오른쪽으로 결합되기 때문에 가능합니다. 이론적 인 의미에서, 이것은 AST의 트리 재 작성이지만 많은 프로그래머가 트리 픽스 업에주의하지 않고 코딩 한 것으로 의심됩니다.