Shift-Reduce 구문 분석을 사용하여 구문 분석 트리 구축

Question

나는 자유 시간에 구문 분석을 실험하고 있으며 매우 간단한 문법에 대한 시프트 감소 구문 분석기를 구현하고 싶었습니다.나는 많은 온라인 기사를 읽었지만 여전히 구문 분석 트리를 만드는 방법에 대해 혼란스러워합니다.내가 하고 싶은 일의 예는 다음과 같습니다.

---

문법:

Expr -> Expr TKN_Op Expr 
Expr -> TKN_Num

입력 예시는 다음과 같습니다.

1 + 1 + 1 + 1

토큰화 후에는 다음과 같습니다.

TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num

---

나는 이해:

1. 이동 스택의 첫 번째 입력 토큰을 푸시하고 입력에서 제거하는 것을 의미합니다.
2. 감소 스택에 있는 하나 이상의 요소를 문법 요소로 대체하는 것을 의미합니다.

따라서 기본적으로 다음과 같은 일이 발생해야 합니다.

Step 1:
    Stack:
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Stack is empty. Shift.

Step 2:
    Stack: TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.

Step 3:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 4:
    Stack: Expr TKN_Op 
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 5:
    Stack: Expr TKN_Op TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.
    // What should I check for reduction? 
    // Should I try to reduce incrementally using 
    // only the top of the stack first, 
    // then adding more stack elements if I couldn't
    // reduce the top alone?

Step 6:
    Stack: Expr TKN_Op Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: Expr TKN_Op Expr can be reduced to Expr. Reduce.

Step 7:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: ...
    // And so on...

외에도 "무엇을 줄일까?" 의심의 여지가 없습니다. 구문 분석 트리를 올바르게 구축하는 방법에 대한 단서가 없습니다.트리는 아마도 다음과 같을 것입니다:

1    +    o
          |
     1    +    o
               |
          1    +    1

축소 시 새 노드를 만들어야 합니까?

그리고 새로 생성된 노드에 언제 하위 노드를 추가해야 하나요/언제 새 루트 노드를 생성해야 하나요?

Answer 1

간단하고 분명한 일은 모든 축소에서 트리 노드를 생성하고 해당 트리 노드로 축소된 문법 요소에서 트리 노드를 추가하는 것입니다.

이는 원시 파서가 사용하는 "시프트 토큰" 스택과 병렬로 실행되는 노드 스택을 통해 쉽게 관리됩니다.길이 N의 규칙에 대한 모든 축소에 대해 시프트 토큰 스택은 N만큼 단축되고 비터미널 토큰은 시프트 스택에 푸시됩니다.동시에 상위 N개 노드를 제거하여 노드 스택을 줄이고, 비터미널용 노드를 생성하고, 제거된 N개 노드를 하위 노드로 연결하고, 해당 노드를 노드 스택에 푸시합니다.

이 정책은 오른쪽 길이가 0인 규칙에도 작동합니다.트리 노드를 생성하고 여기에 빈 자식 집합을 연결합니다(예: 리프 노드 생성).

터미널 노드의 "전환"을 (터미널을 형성하는 문자의) 터미널 노드로의 축소로 생각하면 터미널 노드 전환이 딱 들어맞습니다.터미널용 노드를 생성하고 스택에 푸시합니다.

이렇게 하면 문법과 동형적으로 일치하는 "구체적인 구문/구문 분석 트리"를 얻게 됩니다.(제가 제공하는 상용 도구에 대해 이 작업을 수행합니다).실제로 많은 가치를 추가하지 않는 키워드 노드 등을 포함하기 때문에 이러한 콘크리트 트리를 좋아하지 않는 사람들이 많이 있습니다.사실입니다. 그러나 그러한 트리는 구성하기가 매우 쉽고 문법이 매우 이해하기 쉽습니다. ~이다 트리 구조.2500개의 규칙이 있는 경우(전체 COBOL 파서의 경우와 마찬가지로) 이것이 중요합니다.이는 모든 메커니즘이 구문 분석 인프라에 완전히 구축될 수 있기 때문에 편리합니다.문법 엔지니어는 단순히 규칙을 작성하고, 파서는 실행됩니다. 짜잔, 트리입니다.문법을 변경하는 것도 쉽습니다.그냥 바꾸세요. 짜잔, 여전히 구문 분석 트리를 얻을 수 있습니다.

그러나 구체적인 트리를 원하지 않는 경우, 예를 들어 "추상 구문 트리"를 원하는 경우 문법 엔지니어가 노드를 생성하는 축소를 제어하도록 해야 합니다.일반적으로 축소 단계에서 실행될 각 문법 규칙에 일부 절차적 첨부(코드)를 추가합니다.그런 다음 그러한 절차적 연결이 노드를 생성하면 노드 스택에 유지됩니다.노드를 생성하는 모든 절차적 부착은 오른쪽 요소에 의해 생성된 노드를 부착해야 합니다.이것이 있다면 YACC/Bison/...대부분의 시프트 감소 파서 엔진이 그렇습니다.Yacc이나 Bison에 대해 읽고 문법을 살펴보세요.이 계획은 귀하가 통제권을 갖도록 주장하는 대가로 귀하에게 많은 통제권을 제공합니다.(우리가 하는 일은 문법을 구축하는 데 이렇게 많은 엔지니어링 노력이 들어가는 것을 원하지 않습니다.)

CST를 생성하는 경우 트리에서 "쓸모 없는" 노드를 제거하는 것은 개념적으로 간단합니다.우리 도구에서 그렇게 합니다.결과는 모든 절차적 첨부 파일을 수동으로 작성하지 않고도 AST와 매우 유사합니다.

Answer 2

문제의 원인은 문법에 변화/감소 충돌이 있기 때문입니다.

expr: expr OP expr
    | number

이 문제는 다음 두 가지 방법으로 해결할 수 있습니다.

expr: expr OP number
    | number

왼쪽 연관 연산자의 경우 또는

expr: number OP expr
    | number

올바른 연관을 위해.이것은 또한 나무의 모양을 결정해야 합니다.

축소는 일반적으로 하나의 절이 완전한 것으로 감지될 때 수행됩니다.올바른 연관 사례에서는 숫자를 예상하는 상태 1에서 시작하여 값 스택에 푸시하고 상태 2로 이동합니다.상태 2에서 토큰이 OP가 아닌 경우 숫자를 expr로 줄일 수 있습니다.그렇지 않으면 오퍼레이터를 밀어 상태 1로 전환합니다.상태 1이 완료되면 숫자, 연산자 및 표현식을 다른 표현식으로 줄일 수 있습니다.감소 후에 "반환"하는 메커니즘이 필요합니다.그런 다음 전체 파서는 상태 0에서 시작하여 즉시 상태 1로 이동하고 축소 후 수락합니다.

yacc 또는 bison과 같은 도구는 모든 낮은 수준의 기계와 스택을 가져오기 때문에 이러한 종류의 작업을 훨씬 쉽게 만듭니다.