[컴파일러] - LL Parsing

Basic Parsing Strategies

• Bottom-up
  • 입력을 가장 낮은 단계부터 시작해 트리구성, 다음 입력을 shift 하거나 핸들을 진행해 reduce
  • 모든 입력이 읽히고 그 결과가 문법의 시작 심볼로 reduce되면 파싱 완료
  • LR(k)와 subset들(SLR(k), LALR(k),…)
• Top-Down
  • 시작심볼로부터 출발해 반복적으로 non-terminal을 선택하고 확장
  • 확장된 트리가 입력과 일치하면 성공적으로 파싱완료
  • LL(k)

Predictive Parsing

• 다음 입력 심볼만 보고 어떤 문법 규칙을 적용할지 결정할 수 있을때 사용하는 기법

• LL파싱에 해당하며 Backtracking하지 않는 top-down 파싱

• 룩어헤드(Lookahead) 토큰을 사용하여 어떤 규칙을 적용할지 미리 예측

    A::= α
    A::= β

  두 법칙이 있으면 어떤것을 선택하면 예측이 될지

LL(k) Property

A::= α
A::= β

• LL(1) 은 FIRST(α) FIRST(β)가 달라야한다.

LL Parsers

• 모든 LL(k) 파서
  • Left to right로 스캔
  • Leftmost derivation
  • Looking ahead at mosts k symbols

Table-Driven LL(k) Parsers

• Example

    1. S ::= ( S ) S
    2. S ::= [ S ] S
    3. S ::= ε

• Table

  

LL vs LR

• LL과 LR 둘다 tools(Lex, Yacc)에 의해 자동적으로 table이 만들어진다.
• LL(1)은 single non-terminal과 next input에 대해서 결정한다.
• LR(1)은 다음 input symbol 뿐만아니라 전체 left context에 대해 결정한다.
• LR(1)은 stack을 사용해 더 많은 건텍스트 정보를 저장한다.
• LL(1)은 구현이 더 간단하고 이해하기 쉽지만 처리할 수 있는 문법의 범위가 좁다. LR(1)은 더 복잡한 것에 강하다, 파싱 테이블이 크고 구현이 더 복잡할 수 있다.

Recursive-Descent Parsers(RD parsers)

• 모든 Top-down 방식의 일반적인 방식

• 핵심 idea: 각 non-terminal에 대응하는 function 작성

• Example

    // parse while (exp) stmt
    void whileStmt() {
        // skip “while (” -> terminal
        getNextToken();
        getNextToken();
        // parse condition
        exp(); // -> non-terminal
        // skip “)”
        getNextToken();
        // parse stmt
        stmt();
    }
  
    // parse return exp ;
    void returnStmt() {
        // skip “return”
        getNextToken();
        // parse expression
        exp();
        // skip “;”
        getNextToken();
    }

Possible Problems

• recursive-descent에 관한 두개의 흔한 문제 존재

  • Left recursion (eg. E::= E+T\…)

  • Common prefixes

    • 규칙의 우변에서 둘 이상의 선택 사항이 같은 심볼로 시작할 때 발생합니다. 예를 들어, 문법에 A ::= αB | αC와 같은 규칙이 있다면, α가 공통 접두사

    • 해결: Left Factoring

      • Example

        • Original grammer

          ifStmt::= if ( expr ) stmt | if ( expr ) stmt else stmt

        • Factored grammar

          ifStmt::= if ( expr ) stmt ifTail
          ifTail ::= else stmt | ε