LL(1) parsing

LL(1) Parsing

하향식 Predictive Top Down 파싱의 일종으로, 입력된 문자열의 왼쪽에서부터 파싱을 시작한다. 미리 결과를 예측해서 파싱 방향을 정하기 때문에 backtracking 과정을 대신할 수 있어서 더 효율적이다. 이때 lookahead이라는 정보를 통해 몇 개의 토큰을 미리 볼 것인지의 depth를 지정한다. LL(1)의 경우 depth가 1이므로, 다음 토큰 1개를 미리 보는 형식이다.

Preconditions in LL(1) Parsing

먼저 LL Parsing을 하기 전, 문법을 다음 조건에 충족시켜 주어야 한다.

• grammar should be unambiguous

  방법 : left associativity, precedence를 기반으로 하나의 파스 트리 형성

• grammar should be Left -> Right Recursive

  방법 : 무한 루프를 생성하는 부분을 새로운 변수로 치환

• grammar should be deterministic

  방법 : left factoring 기법을 통해 common factor들을 소거

1. Finding First, Follow

어떤 문법이 있을 때, First는 다음에 오는 terminal이 무엇인지를 나타내고 Follow는 뒤에 따라오는 terminal은 무엇인지를 나타내는 것으로, 반복적으로 찾아야하는 것들을 미리 정의해서 더 효율적으로 만들기 위함이다.

• First 찾는 방법

  First()는 해당 variable이 전개된 생성 규칙에서 가장 앞에 오는 terminal의 집합이다.

  

• Follow 찾는 방법

  Follow()는 해당 variable 뒤에 오는 가장 근접한 terminal의 집합이다.

  

2. Make LL Parsing Table

Predictive 파싱의 경우 사전에 parsing table을 만들어서 다음에 어떤 토큰이 나올지를 찾는다. 그리고 해당 parsing table 셀 내에서 중복이 생기는지 확인해서 해당 문법이 LL(1) grammar인지 아닌지 확인할 수 있다.

먼저 각각의 문법들에 대해 First와 Follow를 구한다.

세로 항에는 모든 variable, 가로 항에는 모든 terminal을 넣어서 테이블을 만든다. 그리고 생성규칙에 각각 번호를 부여하고, 각 규칙의 First에 해당하는 항에 번호를 기입한다.

만약 한 셀 당 한 개의 숫자만 가지고 있다면(= 중복이 없다면), 해당 문법은 LL(1) grammar !

3. LL Parsing, Parse Tree Generation

해당 문법이 LL(1) grammar인 것을 확인했다면, 이제는 입력 받은 문자열이 해당 문법을 따르는지 확인해야 한다. 만들어 놓은 parsing table과 stack을 사용해서 파싱을 하고, 최종적으로 parse tree를 반환한다.

먼저 First, Follow를 구하고 이를 바탕으로 Parsing Table을 생성한다. 그리고 셀에 넣었던 숫자들을 각각의 해당 생성 규칙으로 바꿔서 기입한다.

문자열 맨 앞에 lookahead 화살표를 위치시키고, 맨 뒤에 \$ 기호를 추가한다. 그리고 stack을 하나 생성해서 맨 뒤쪽에 \$ 와 starting variable($S$)를 각각 push하면 파싱을 위한 준비가 완료된다. 여기서 \$ 기호를 추가하는 것은 문자열의 끝까지 파싱했는지 확인하기 위함이다.

문자열에서 lookahead가 가르키는 값과 stack의 맨 위의 값을 매칭해서 이에 해당하는 production rule을 찾고, 해당 규칙을 reversed order로 stack에 push한다. 만약 lookahead가 가르키는 값이 stack 값과 일치한다면 pop한다. 위의 과정을 반복한다.

위와 같이 모든 값들이 소거되어 $ 기호가 매칭되면 해당 문자열은 LL(1) parsing 성공 !

최종 Parse Tree : 한 번 production rule을 expand할 때마다 생성해주면 된다.

이렇게 하면 LL(1) parsing 끝 !-!

맨 위로 이동하기