LL 파싱이란 Left to right scanning (왼쪽에서 오른쪽으로 스캔하고) Left parse (좌파스를 구하는) 결정적인 구문 분석 방법이다. 이 때 이 LL조건을 만족하는 문법을 결정적으로 파싱할 수 있는 것을 LL Paser라 한다. LL Parser에는 recursive-descent parser와 predictive parser가 있다.

1. Recursive-descent parser

주어진 입력 스트링을 파싱하기 위해 recursive 프로시저를 사용하기 때문에 Recursive-descent parser라고 한다.

LOOKAHEAD

LOOKAHEAD란 한 생성 규칙을 적용했을 때 그 생성 규칙에서 생성할 수 있는 terminal의 집합이다.

• rhs의 FIRST

• rhs가 ε를 유도할 수 있는 경우에 lhs의 FOLLOW
  를 ringsum 연산 한 것이 그 생성 규칙의 LOOKAHEAD이다.

• 단 rhs가 terminal로 시작하는 생성 규칙의 LOOKAHEAD는 바로 그 terminal 심벌만이 된다.

  ex) LOOKAHEAD(A → aX) = {a}

생성 규칙에서 첫 번째로 유도될 수 있는 terminal 심벌들의 집합이 nobacktracking의 조건을 설명할 수 있는 생성 규칙의 LOOKAHEAD이다.

strong LL 조건

• LOOKAHEAD(A → α) 와 LOOKAHEAD(A → β)의 교집합이 공집합이다.

를 만족하는 것이 strong LL 조건이다.

LOOKAHEAD가 같다면 생성 규칙이 유도하는 첫 번째 심벌이 같으므로 어떤 생성 규칙으로 확장해야 올바른 스트링을 유도할지 결정적인 구문분석을 할 수 없다.

strong LL(1) 문법

Strong LL 조건을 만족하는 문법 recursive-descent 구문 분석기가 결정적으로 구문 분석하기 위해서는 strong LL(1) 문법이어야 한다.

recursive - descent parser

strong LL(1) 문법의 경우 terminal과 nonterminal symbol에 대한 프로시저를 작성함으로써 구현한다.

• terminal

  심벌 a 프로시저 pa 토큰번호 ta

• nonterminal

  현재의 입력 심벌과 LOOKAHEAD가 같은 생성 규칙을 선택해야 한다.
  = 현재의 입력 심벌을 생성할 수 있는 생성 규칙을 선택하도록 프로시저 작성.

프로시저 작성하는 건 수업시간에 하지 않았다!

2. Predictive Parser

Recursive-descent parser는 생성 규칙이 바뀔 때마다 구문 분석기를 구현한 프로그램을 다시 고쳐 써야한다. 하지만 Predictive Parser의 경우에는 생성 규칙이 바뀌더라도 구동 루틴은 고치지 않고, parsing table만 다시 구해서 구문분석기를 구현한다.

문법 의존적인 parsing table + 문법 독립적인 driver routine = 구문분석 스택을 이용하여 구현한다.

구성요소

• Input

  구문 분석이 될 input string과 $를 저장한다.

• Stack

  Sentencial Form에서 input string과 아직 매칭되지 않은 부분을 유지한다.
  bottom marker로 $를 갖는다.

• Output

  parse tree나 구문 분석시 적용된 일련의 생성 규칙 번호(좌파스)

• Parsing Table = predictive parsing table = LL parsing table

  크기 : (Nonterminal의 수) x (Terminal의 수 + ++1++)
  (bottom marker인 $이 존재하기 때문에 1을 더한다. )

파싱 행동

• Pop : stack의 top 이 현재의 입력 심벌과 같은 경우

  stack에서 top심벌 제거, 입력스트링에서 현재 입력 심벌 제거

• expand : stack의 top이 nonterminal인 경우

  생성규칙을 적용해서 확장한다.

• accept :stack의 top과 현재의 입력 심벌 모두가 $인 경우

  올바른 스트링입니다!!!!! 파싱을 종료한다.

• error : stack의 top으로 부터 현재 보고있는 입력 심벌을 유도할 수 없는 경우

  에러에러!!!!!

Algorithm Predictive_Parser_Action;
begin
	repeat
    	if X가 Terminal symbol 이거나 $이면
        /* pop */
     	   if X = a면 begin pop X; get_nextSymbol end else error fi
       else /* X가 nonterminal인 경우 */
       	/* expand */
        	if M[X,a] = X→Y1Y2...Yk 이면 stack에서 X를 제거하고 rhs의 역순으로 스택에 넣는다.  
            else error fi /* error */
          fi
       until x = a = $ /* accept */
end.

이라고 할 때 스택에서의 $는 bottom marker를 나타내고, 입력스트링에서의 $는 end marker를 의미한다. 또한 N은 적용된 생성 규칙의 번호를 의미한다.

실제 문제에서는

이런식으로 적용해서 풀어나간다.

Predictive Parsing Table

M[X,a] = r 이면 stack top이 X이고 현재의 입력 심벌이 a 일 때 r번 생성 규칙으로 확장하라는 뜻이다.

책에는

생성규칙 A → α에 대해서 parsing table을 만들기 위해서는 다음과 같이 채워 나간다.

1. FIRST(α)에 포함된 모든 terminal symbol a에 대해 M[A,a] := A → α로 채운다.
2. FIRST(α)에 ε가 포함된다면 FOLLOW(A)에 포함된 모든 terminal symbol b에 대해 M[A,b] := A → α 로 채운다.
   라고 수록되어있다.

다시 말하자면 어떤 생성규칙 A → α가 있을 때, FIRST(α)에 포함된 terminal 심벌을 a라 하면 parsing table의 M[A,a] 칸은 A → α의 번호를 쓰면된다. 다만 α가 ε이라면 FOLLOW(A)에 포함된 terminal 심벌을 b라 할 때 parsing table의 M[A,b]칸을 A → α로 채운다.