하향식 파싱

 

4.하향식 파싱 | JAVA 2004/04/14 13:04

http://blog.naver.com/lunasea94/1779658

4. 하향식 파싱(Top-Down Parsing) 4.0  소개 하향식 파서는 predictive(예측) 파서라고 부른다. 이 파서는 어떤 상태에서나 파스 트리 (parse tree)의 다음 낮은 단계를 예측하려고 시도한다. 이러한 예측(prediction)은  입력 의 다음 토큰과 현재의 트리를 검사한 후, 다음에 시도할 생성규칙을 선택하는 것으로  행해진다. 따라서, 파서는 3.3.1절에서 설명한 좌측유도(leftmost derivation)를 시도하면서, 위에서 아래로 파스 트리를 구축한다. 3장에서는 하향식 파서의 문법적인 문제를 논의하였다. 가장 간단한 형태의 파서인 recusive descent 파서는 왼쪽 반복(left recursive) 문법을 사용할 수 없다. 　 4.1 Recursive Descent 파싱 Recursive Descent 파싱은 파스 트리를 구성하기 위해서 되부름 프로시듀어(recursive procedure)를 사용한다. 문법에 있는 각각의 난터미널에 대하여 그 난터미널을 구문분석 하는 프로시듀어를 가진다. 이들 프로시듀어들은 입력을 읽으면서 생성규칙의 오른쪽에 있는 터미널 심볼들을 맞추어보거나, 입력을 읽는 프로시듀어나 터미널 심볼들을 맞추어 보는 프로시듀어들을 호출한다.   다음 왼쪽 반복이 제거된 식(ｅxpression)에 대한 문법을 보자. E -> T E' E' -> + T E' | e T -> F T' T' -> * F T' | e F -> ( E ) | id Recursive Descent 파싱에서, 문법은 각각의 생성규칙이 하나의 (되부름) 프로시듀어로 구현된 것으로 간주된다. 따라서, 위의 문법에서 난터미널 E와 E'는 다음과 같은 프로시 듀어가 될 것이다. 프로시듀어 E BEGIN {E}    Call T    Call E'    PRINT ("E found") END {E} 　 프로시듀어 E' BEGIN {E'}    IF NextSymbol in input = "+" THEN    BEGIN       PRINT ("+ found")       다음 심볼을 읽는다       Call T       Call E'    END {IF}    PRINT ("E' found") END {E'} 이 프로시듀어는 만약 "+"가 발견되지 않으면 E'  ->  e 인 생성규칙 임을 전제하고 있으 므로, 정확한 프로그램에 대해서 잘 동작한다. 난터미널 T와 T'도 비슷한 생성규칙을 가지므로 비슷하게 구성된다. 프로시듀어 T BEGIN {T}    Call F    Call T'    PRINT ("T founf") END {T} 　 프록시듀어 T' BEGIN {T'}    IF NextSymbol in input = "*" THEN    BEGIN       PRINT ("* found")       다음 심볼을 읽는다       Call F       Call T'    END {IF}    PRINT ("T' found") END {E'} 　 생성규칙 F는 다음과 같이 기술될 수 있다. 프로시듀어 F BEGIN {F} CASE NextSymbol is "(":    PRINT ("( found")    다음 심볼을 읽는다    Call E    IF NextSymbol = ")" THEN    BEGIN {IF}       PRINT (") found")       다음 심볼을 읽는다       PRINT ("F found")    END {IF}    ELSE    error "Id":    PRINT ("Id found")    다음 심볼을 읽는다    PRINT("F found") otherwise : error END {F} 여기에서 NextSymbol은 어휘분석기에서 생성된 토큰이다. "다음 심볼을 읽는다"는 다음 토큰을 얻기 위한 호출이 있어야 한다. PRINT문장은 좌측 유도 과정의 역순을 출력해 낼 것이고, 파스 트리는 손으로 그려 내거나, 아니면, 출력되는 정보를 스택에 모아서 트리의 레벨에 따른 들여쓰기 출력에 의하여 실제의 좌측 유도과정을 출력할 수 있다. 　 4.2 LL 문법 Recursive descent파서는 LL(1)파서와 비슷한 하향식 파싱 기법이다. LL(1)파서는 구문 분석을 위하여 테이블을 사용한다. 첫번째 L은 입력 스트링이 왼쪽에서 오른쪽으로(Left-to-right) 스캔 됨을 의미한다. 두 번째 L은 좌측유도(Leftmost derivation) 가 구성됨을 의미하고, 1은 테이블이 한 개의 lookahead(미리보기)에 의해서 만들어 졌음 을 말한다. 단지 하나의 lookahead는 다음 심볼 만을 본다는것을 의미한다. LL(1)파서는 테이블 유도에 의한 recursive descent 파서인 것이다. 　 4.2.1 LL(1) 문법 LL(1)파서로 구문분석하기 위해서는 문법이 LL(1)조건을 만족해야 한다. LL(1)조건을 정의 하고, 한 문법이 LL(1)조건을 만족하는지 검사하기 위하여, 두 가지의 사전 정의가 필요하 다. (1) 터미날과 난터미날 스트링인  a 의 FIRST(a), (2) 난터미날 A의 FOLLOW(A) 등이다. 　 FIRST(a) 터미날들과 난터미날들의 스트링인 a에 대하여, FIRST(a)는 a로부터 유도될 수 있는 스트링으로 시작하는  e을 포함한 터미날 심볼들의 집합을 말한다. 따라서, 식을 나타내 는 문법: E -> E + T | T T -> T * F | F F -> ( E ) | id                 ( Left-Recursion 이 있다. . )   에서, FIRST(E) = {(, Id}이다. E는 "("와 "id"로 시작되는 스트링을 유도할 수 있기 때문이다. "("에 대하여 보면, E -> T -> F -> (E)의 과정을 가지므로, "("는 E로부터 유도될 수 있다. 마찬가지로, FIRST(T * id) = { (, id }이다. 왜냐하면, T * id ->F * Id ->( E ) * id이고,  T * id ->F * id -> id * id이기 때문이다. 또한, FIRST (id + id) = {id} FIRST (id) = {id} 다음은 왼쪽 반복(left-recursion)이 제거된 식(ｅxpression)을 위한 문법이다. E -> T E' E' -> + T E' | e T -> F T' T' -> * F T' | e F -> ( E ) | id 여기에서, FIRST(E) = FIRST(T) = FIRST(F) = { ( , id } FIRST(T * id) = { ( , id } FIRST(id + id) = {id} FIRST(id) = {id} 이다.   두 가지 문법이 같은 FIRST 집합을 가진다는 것에 유의하자. 　 FOLLOW(A) aAb 와 같이,  a와b 는 터미날과 난터미날들의 스트링일때, 문장형태에 있는 난터미날 A에 대하여 FOLLOW(A) = FIRST(b)   이다. 즉, FOLLOW(A)는 문장형태 안에 있는 "A의 오른쪽에 나타날 수 있는 터미날"들의 집합이다.   식을 위한 문법 E -> E + T | T T -> T * F | F F -> ( E ) | id 에서, FOLLOW(E) = { ) , + }이다. "(E)"는 "E" 다음에 ")"가 나오는 문장형태이기 때문에, FOLLOW(E)에 ")"가 있고, "E + T"는 "E"다음에 "+"가 나오는 문장형태이기 때문에, FOLLOW(E)에 포함된다. 또한, FOLLOW(T) = {+, ), *} 이다. "+"는 E -> E + T -> T + T 의 유도과정을 가지기 때문에 FOLLOW(T)에 포함된다. ")"와 "*"는 어떻게 FOLLOW(T)에 포함될까? FIRST(a)와 FOLLOW(A)를 이용하여 LL(1) 조건이 정의될 수 있다. 　 LL(1) 조건 직관적으로 보아서, 입력 스트링에서 다음의 토큰만을 보는 것만으로 한 문법에서 적용할 생성규칙을 선택할 수 있다면, 이 문법은 LL(1)이다. 보다 형식적으로 정의하면, 두 개의 생성규칙, A -> a, A -> b가 있을 때 이 문법이 LL(1) 이려면, 다음을 만족한다.   (a) FIRST(a ) Ç FIRST( b) = f (b) a -> ... -> e 와 같이 a혹은  b가 e로 유도된다면, FIRST(b) Ç FOLLOW(A) = f이다.   예 1 LL(1)이 아닌 문법 다음 문법을 생각해 보자. A -> d A A -> d B A -> f B -> g 이 문법은 정의의 (a)를 위반하기 때문에 LL(1)이 아니다. 즉, 두 개의 생성규칙, A -> d A 와 A -> d B 에서, FIRST(d A) Ç FIRST(d B) = {d} ¹ f 이다. 　 예 2 LL(1)이 아닌 또 다른 문법 다음 문법을 살펴보자. S -> X d X -> C X -> B a C -> e B -> d 두 개의 생성규칙 X -> C와 X -> B a에 대해서, C -> e이고 FIRST(B a) Ç FOLLOW(X) = {d} ¹ f 이므로, 이 문법은 LL(1)이 아니다. 　 4.3 LL(1) 파싱 4.3.1 알고리즘 LL(1)파싱은 본질적으로 테이블 주도(table driven)의 recursive descent 파싱이다. 프로시 듀어를 되부름(recursive call)하는 대신에, 다음 행동의 수행을 지시하는 하나의 테이블 과 하나의 명시적인 스택(stack)이 쓰인다. 이미 테이블이 만들어졌다고 가정하고, 파싱 알고리즘을 살펴보자. 알고리즘 LL(1) 파싱 "$"를 스택에 넣는다. 스택을 시작 심볼로 초기화한다. REPEAT WHILE 스택이 비지 않았다    CASE StackTopSymbol    터미널 심볼: IF InpuSymbol = StackTopSymbol THEN                          입력을 넘긴다.                          Pop Stack                      Else                          Error    난터미널 심볼:                     난터미널 심볼과 InpuSymbol을 이용하여 테이블에서 적절한 생성규칙을 찾는다.                     Pop Stack                     스택에 생성규칙의 오른쪽을 넣는다(가장 왼쪽 심볼이 탑에 오도록). END REPEAT IF 입력 끝 THEN     Accept ELSE     Error 　 예 3  LL(1) 파싱 다음의 문법, 파싱 테이블을 이용하여, 입력 스트링을 구문 분석하자. 문법: E  -> T E' E' -> + T E' | e T  -> F T' T' -> * F T' | e F  -> id | ( E ) 이 문법은 LL(1)인가? (연습 문제 참조) 테이블은 행에는 난터미널이 놓여지고, 열에는 각각의 터미널 심볼이 놓여져서 다음과 같이 마련된다. 파싱 테이블: 입력 심볼 id + * ( ) $ 난 터 미 널 E E -> T E'     E -> T E'     E'   E' -> + T E'      E' -> e E' -> e T T -> F T'     T -> F T'     T'   T' -> e T' -> * F T'   T' -> e T' -> e F F -> id     F ->  ( E )     입력 스트링: id * id + id 파싱: 알고리즘의 처리 과정을 따라가면, E가 스택에 먼저 넣어진다. (스택의 탑은 오른쪽에 표시됨.) ((1)을 보라.) E가 스택의 탑에 있으므로, CASE문장에서 난터미널이 선택된다. 현재 입력 심볼은 id이므로, 테이블에서 선택되는 생성규칙은 E -> T E'이다. 알고리즘이 스택에서 E를 팝하고 생성규칙의 오른쪽인 T E'를 넣으라고 하고 있다. (2)이 이의 결과이다. (스택의 탑은 오른쪽이다.) (3)에서 스택의 탑은 id이고, 현재 입력 심볼도 id이다. 알고리즘은 스택의 탑에서 id를 제거하고, 입력에서도 id를 지나보내도록 한다. 전체적인 파싱 과정은 다음과 같다. 스택 입력 생성규칙 (1) (2) 　 (3) 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 $E $E'T $E'T'F $E'T'Id $E'T' $E'T'F* $E'T'F $E'T'Id $E'T' $E' $E'T+ $E'T $E'T'F $E'T'Id $E'T' $E' $ Accept 　 id * id + id $ id * id + id $ id * id + id $ id * id + id $ * id + id $ * id + id $ id + id $ id + id $ + id $ + id $ + id $ id $ id $ id $ $ $ $ 　 　 E -> T E' T -> F T' F -> Id 　 T' -> * F T'  　 F -> Id 　 T' -> e E' -> + T E' 　 T' -> * F T'  F  -> Id 　 T' -> e E' -> e 　 　 　 우리가 이 과정의 생성규칙란에 적용된 생성규칙들을 따라서 유도하면, 좌측유도 (left-most derivation)을 얻게 된다. 　 4.3.2  LL(1) 파싱 테이블의 구축 테이블은 다음의 알고리즘을 이용하여 구성할 수 있다. 알고리즘 LL(1) 테이블  구성 문법에서 A -> a인 모든 생성규칙들에 대하여 1. 만약, a가 a로 시작되는 스트링을 유도할 수 있으면, 즉, FIRST(a)에 속하는 모든 a에 대하여,    Table[A, a] = A -> a 2. a가 빈 스트링인 e를 유도할 수 있으면, A로부터 유도되는 한 스트링의 뒤를 따르는 모든 b에 대하여, 즉, FOLLOW(A)에 속하는 모든 b에 대하여,    Table[A, b] = A -> a 테이블에서 정의되지 않는 요소는 오류이다. 만약 테이블의 한 요소가 한 개 이상의 생성규칙으로 정의되면( 충돌이 생기면 ), 이 문법은 LL(1)이 아니다.   예 4 LL(1) 파싱 테이블 구성하기 다음의 문법을 이용하여 LL(1)파싱 테이블을 구성하여 보자. E  -> T E' E' -> + T E' | e T  -> F T' T' -> * F T' | e F  -> id | ( E ) (i) 생성규칙 E -> T E'에 대하여  FIRST(T E') = { (, Id } 이므로, Table[E, (] = E -> T E'이고, Table[E, Id] = E -> T E' 이다. (ii) 생성규칙 E' -> e 에 대하여  FOLLOW(E') = {), $} 이므로, Table[E', )] = E' -> e이고, Table[E', $] = E' -> e이다.　 LL(1) 파싱 테이블은 자동적으로 생성되도록 만들 수 있다. 먼저, FIRST(a)와 FOLLOW(A)를 계산하는 프로시듀어를 작성한 다음, 문법이 입력되면, 각각의 생성규칙에 대해서 A와 a를 찾고, 위의 두 과정을 통해서 테이블을 구성하도록 한다. 　 4.4. 하향식 파서 생성기 3장에서 언급한 바와 같이, 현재 수많은 파서 생성 도구들이 있다. 대부분의 파서 생성 도구들이 다음 장에서 언급할 상향식 파서를 만들어 내지만, 몇 가지 하향식 도구들도 있다. 일반적으로 상향식 파싱 보다 하향식 파싱이 더 쉬운 것처럼, 상향식 파서를 만드는 일보다 하향식 파서를 만들어내는 일이 훨씬 더 쉽다. 한 가지 방법은 문법을 읽고 4.3.2절에서 설명한 방법으로 LL(1)파싱 테이블을 구성하는 것이다. 여기에 4.3.1절에서 제시된 알고리즘을 구현하는 드라이버 루틴을 기술하면 된다. 다른 방법으 로는, 테이블을 생성해내는 대신에 case문장들을 써서 테이블을 구현하는 프로그램을 만들어내게 할 수 있다. 이러한 방식은 테이블을 대치하게 하는 것 보다 사용자가 요구 하는 대로 프로그램을 손쉽게 맞추어줄 수 있으므로, 더 나은 접근 방식으로 평가된다. 만약, 사용자가 테이블을 바꿀 경우가 없다면, 단순히 테이블을 생성하게 하는 것이 더 쉬운 방법이다. 　 4.5 이장의 요약 하향식 파싱은 우리가 손으로 파싱하는것과 같은 방식이기 때문에 개념적으로 간단한 파싱 방식이다. 입력 스트링과 문법이 주어지면, 하향식 파싱은 시작 심볼을 확장하여, 스트링에서 가장 왼쪽 심볼이 생성될 때까지 좌측유도를 통한 확장을 계속한다. 이어서 다음의 가장 왼쪽 심볼이 유도되는 것이다. 이 장에서는 두 가지의 파싱 방식이 설명되었다. 즉, Recursive descent 파싱과 테이블 주도의 LL(1)파싱이다. 하향식 파싱이 파싱하기에는 직관적인 방식이지만, 가장 효율적인 파싱방법도 아니고, LL(1)문법은 파싱할 수 있는 언어의 범위도 가장 크지 않다. 한 언어가 하향식으로 파싱되기 위해서는 문법의 모호성을 없애야 하고, left factoring해야 하며, 왼쪽 반복도 수정되어야 한다. 우리는 다음 장에서, 파싱하기에는 직관적이지는 않으나, 하향식 보다는 효율적인 파싱 방식인 상향식 파싱을 다룬다. 상향식 파싱은 파싱할 수 있는 문법의 제한이 별로 없고, 하향식 보다 훨씬 많은 범위의 언어를 파싱할 수 있다. ( 문법의 제한 , 파싱가능한 언어의 범위 ) 　 연습문제 1. 다음 문법을 보자. Z -> S S -> w S S -> A B A -> x A A -> y B -> z 이 문법을 보고 하향식 파싱 과정을 보이시오. 스택과 입력 스트링의 초기치는 다음과 같다. 스택        입력 스트링       생성규칙  $Z             wwxyz $ 　 2. 다음 문법을 보자. S -> C C C -> a C C -> b 스택과 입력 스트링의 초기치가 다음과 같을 때 이 문법을 이용하여 하향식 파싱 과정을 보이시오. 스택       입력 스트링      생성규칙  $S             abab$ 　 3. 예 1의 파스(parse)에 대하여 파스 트리를 그리시오. 　 4. 다음 문법은 LISP와 유사한 식을 나타내는 문법이다. S -> x S -> ( S R R -> , S R R -> ) 이 문법은 다음과 같은 식을 생성한다. x (x, (x,x)) ((x, (x,x)),x) (a) 이 문법이 LL(1)임을 보이시오. (b) 이 문법의 LL(1) 파싱 테이블을 구성하시오. (c) 테이블을 이용하여 스트링  "(x, (x,x))" 의 하향식 파싱 과정을 보이시오. 스택        입력 스트링       생성규칙 　 5. 다음 문법을 보자. S -> x A A -> y S -> x C C -> z (a) FIRST(S)를 계산하시오. (b) 이 문법은 LL(1)인가? LL(1)인 근거 혹은 아닌 근거를 밝히시오. 　 6. 3장의 끝에 제시된 부분 Ada언어의 문법을 보고, 모든 난터미날들의 FIRST와 FOLLOW들을 구하시오. 　 7. (a) 다음의 식에 대한 문법이 LL(1)이 아님을 보이시오. E -> E + T | T T -> T * F | F F -> ( E ) | Id 　 (b) 다음 왼쪽 반복이 제거된 문법이 LL(1)인지 아닌지를 보이시오. E -> T E' E' -> + T E' | e T -> F T' T' -> * F T' | e F -> Id | ( E ) 　 8. LL(1) 정의를 보고 k > 1인 LL(k)를 정의하여 보시오. 　 9. Non-LL(1)인 문법을 가진 언어의 파싱: 파싱 시간에 선택하게 하는 방법으로 LL(1)이 아니거나 모호한 문법을 가진 언어를 파싱할 수 있다. IF-THEN-ELSE문장의 문법을 간략하게 표기한 다음 문법을 보자(i = IF, t = THEN, e = ELSE, a = 터미널 문장, c = 조건). S -> i E t S S' S -> a S' -> e S S' -> e E -> c (a) 이 문법이 LL(1)이 아님을 보이시오. (b) LL(1) 파싱 테이블을 구성하시오.(이 문법이 LL(1)이 아니기 때문에 적어도 한 개의 이중 엔트리가 있다.) (c) 테이블을 이용하여 입력 스트링 "IF c THEN IF c THEN a ELSE a"를 하향식 파싱하는 과정을 보이시오. 이때 "ELSE"는 이중 테이블 엔트리에서 하나를 선택하게 하여 가장 가까운 IF에 결합시키시오. 스택      입력 스트링                         생성규칙 $S           IF c THEN IF c THEN a ELSE a $ 　 컴파일러 프로젝트 III 파싱 3장에서 제시된 문법을 다시 보자. Program   → begin  SequenceOfStatements  end  ; SequenceOfStatements → Statement  { Statement } Statement  → SimpleStatement SimpleStatement  → AssignmentStatement AssignmentStatement  → Name  :=  ｅxpression  ; Name   → SimpleName SimpleName  →  Identifier ｅxpression  →  Relation Relation   →  Simpleｅxpression Simpleｅxpression  →  Term  { AddingOperator  Term } Term  →  Factor  { MultiplyingOperator Factor } Factor  →  Primary Primary  →  Name  |  NumericLiteral  |  (ｅxpression) AddingOperator  →  +  |  - MultiplyingOperator   →  *  |  /  |  mod  |  rem NumericLiteral  →  DecimalLiteral DecimalLiteral  →  Integer 　 문제 1 이 문법을 구현하는 recursive descent parser를 설계하시오.  2장에서 주어졌던 다음 프로그램을 입력하여 파싱하시오. begin    a := b3;    xyz := a + b + c    - p / q;    a := xyz * (p + q);    p := a - xyz - p; end; 　 문제 2 두 개의 프로그램을 작성하여 파서를 만드시오.  (1) 입력으로서 BNF 문법을 읽어서 LL(1) 테이블을 생성하는 프로그램을 작성하시오. (2) 테이블을 읽고 입력 스트링을 읽어서 파싱하여 파스트리를 생성하는 드라이버 루틴을 작성하시오. LL(1) 테이블을 생성하는 일은 테이블을 표현하는 case문장들로 구성된 프로그램을 생성시키게 하는 것으로 대신하고, 이 프로그램이 연결되어 LL(1)파서를 생성하도록 하는 드라이버프로그램을 생성하도록 만들 수도 있다.