Chapter 06 구문분석
01 구문분석의개요 02 하향식구문분석 03 상향식구문분석 04 모호한문법의사용과에러처리루틴
구문분석의종류와특징을이해할수있다. 하향식구문분석방법이해할수있다. 상향식구문분석방법이해할수있다. 모호한문법사용과에러처리루틴을이해할수있다.
6.1 구문분석의개요 구문분석 (Syntax analysis) 주어진입력이올바른프로그램인가를검사하고다음단계에서필요한정보를구성하는과정 스캐너에의해생성된토큰을입력으로받아주어진문법에맞는지를검사하고, 문법에맞으면파스트리를생성하고맞지않으면에러를내는단계 구문분석을담당하는도구를구문분석기 (Syntax analyzer) 혹은파서 (parser) 라고함 4
6.1 구문분석의개요 구문분석방법 - 파스트리를어떤순서로만들어가느냐에따라분류 하향식구문분석 : 입력문자열을한번에한심벌씩좌에서우로검사 (left to right scanning) 하면서루트노드에서시작하여터미널노드로만들어나가는방법이다. 즉하향식구문분석은시작기호 S 로부터문법의규칙을적용하여좌단유도에의해주어진문장을찾아가는방법이고하향식구문분석의경우좌단유도에의한좌파스가생성된다. 상향식구문분석 : 입력문자열을한번에한심벌씩좌에서우로검사 (left to right scanning) 하면서터미널노드에서시작하여루트노드로만들어나가는방법이다. 상향식구문분석은입력된문장에서감축에의해시작기호를찾아가는방법으로우단유도의역순이된다. 상향식구문분석의경우우단유도의역순에의한우파스가생성된다. 5
6.2 하향식구문분석 하향식구문분석은시작기호로부터생성규칙에좌단유도만을적용하는방법 으로구현이간단하여학습할때는자주사용하지만, 역추적문제때문에상업적 인용도로는잘사용하지않는다. 일반적인하향식구문분석방법은여러가지가있지만다음과같은과정을거 친다고가정한다. 1 시작기호에대해생성규칙을적용한다. 이때생성규칙이여러개존재하면첫번째생성규칙부터적용한다. 생성규칙을적용할때마다부분파스트리를구성해나간다. 2 생성된문장형태의문자열과입력기호를차례로비교한다. 3 만약유도된문자열과입력기호가같으면계속비교해나간다. 4 비교한두기호가같지않으면생성규칙을잘못적용한것이므로현재적용된생성규칙을제거하고다른생성규칙을적용한다. 이때입력기호의위치는제거한생성규칙에서보았던기호의개수만큼뒤로이동하는데이를역추적이라한다. 5 이와같은과정을반복하다가더이상적용할생성규칙이없으면주어진문장을주어진문법에올바르지않은문장으로인식하고에러메시지를출력한다. 만약생성된문자열이주어진문자열과일치하면올바른문장으로인식하고파스트리를출력으로내보낸다. 6
6.2 하향식구문분석 [ 예제 6-1] 하향식구문분석 다음문법에대해문자열 cabdd 가문법에맞는문장인지하향식구문분석방법으로검사하고, 좌단유도가적용될때마다파스트리를구성해보자. 1 S cdd 2 D a 3 D ae 4 E bb 5 E bd [ 풀이 ] 1) 시작기호가 S 이므로 S 의생성규칙을적용한다. 생성규칙 S cdd 에대해 S cdd 를유도한다. 입력 c 와생성된 c 가같으므로입력위치는오른쪽으로하나이동하고다음과같은파스트리를생성한다. 7
6.2 하향식구문분석 2) 다음논터미널기호 D 에대해 D 의생성규칙이 2 개존재하므로첫번째생성규칙을적용한다. 새로생성된기호 a 와현재의입력기호가같으므로입력위치를오른쪽으로하나이동한다. 파스트리는다음과같다 3) 다음으로생성된기호 d 와현재의입력기호가맞지않으므로적용된생성규칙을제거하고, 제거한상태에서논터미널기호 D 에대한다른생성규칙을적용한다. 물론이생성규칙은입력기호와맞아야하며아직적용하지않은것이어야한다. 논터미널기호 D 로돌아갈때는처음에 D 로갔을때의입력위치로가야한다. 이는논터미널기호 D 에대한프로시저가지역변수로입력상태를저장하고있어야한다는뜻이다. 즉 S cdd 에 D ae 를적용하면 S cdd caed 가된다. 파스트리는다음과같다. 8
6.2 하향식구문분석 4) 새로생성된기호 a 와입력기호 a 가맞으므로입력위치를오른쪽으로하나이동한다. 5) 다음논터미널기호 E 에대해 E 의첫번째생성규칙인 E bb 를적용한다. 파스트리는다음과같다 6) 새로생성된기호 b 와현재의입력기호 b 가같으므로입력위치를오른쪽으로하나이동한다 9
6.2 하향식구문분석 7) 다음생성된기호 b 와현재의입력기호가맞지않으므로적용된생성규칙을제거하고, 제거된상태에서논터미널기호 E 에대해다음의생성규칙 E bd 를적용한다. 현재의입력위치를조정한다. 파스트리는다음과같다 8) 새로생성된기호 b 와현재의입력기호 b 가같으므로입력위치를오른쪽으로하나이동한다 9) 다음생성된기호 d 와현재의입력기호 d 가같으므로입력위치를오른쪽으로하나이동한다. 10
6.2 하향식구문분석 10) 다음생성된기호 d 와입력기호 d 가일치하므로입력문자열 cabdd 는정의된문법에맞는문장이며, 다음과같은파스트리를구문분석의출력으로내보낸다. 결론적으로일반적인하향식구문분석은역추적을하면서차례로생성규칙을적용한다. 이때주어진문자열과같은문자열을생성하면올바른문장으로인식하고, 시작기호로부터모든생성규칙을적용해도주어진문자열과같은문자열이생성되지않으면주어진문자열이주어진문법으로부터생성될수없는문장이라고판단하여에러메시지를내보낸다. 이과정에서생성규칙이잘못적용되어주어진문자열을생성할수없으면그생성규칙에서보았던문자열을다시검조하기위해입력으로보내며다른생성규칙을가지고유도를시도한다. 11
6.2 하향식구문분석 이와같은과정을역추적이라하는데, 한입력기호를여러번반복해서검조하기때문에시간이아주많이소요되어하향식구문분석은실제적인컴파일러의구문분석알고리즘으로사용하기에부적당하다. 따라서역추적을하지않고결정적으로구문분석을할수있는방법이필요하다. 하향식구문분석에서는문법에어떤제약적인조건을붙여서결정적인구문분석이가능한데이런제약조건을 LL 조건 (LL condition) 이라한다. 그리고 LL 조건을만족하는문법을 LL 문법이라하며, LL 문법으로하향식구문분석기를만들어구문분석을하는방법을 LL 구문분석이라한다. LL 은입력문자열을왼쪽에서오른쪽으로읽어가며 (left to right scanning) 좌파스를생성하기때문에붙은이름이다. LL 방법은주어진문자열과같은문장을생성하기위해현재의입력기호를보고적용될생성규칙을결정적으로선택하여유도한다. 그리고현재의입력기호와생성된터미널기호가같지않으면주어진문장을틀린문장으로간주한다. LL 조건은유도과정에서나타난문장형태에서논터미널을대체하는생성규칙을결정적으로선택하기위한것으로 FIRST 와 FOLLOW 를이용한다. 먼저 FIRST 와 FOLLOW 등몇가지용어를정의하고 LL 조건에대해설명한다음, LL 조건을만족하는하향식구문분석의종류를살펴보자. 12
6.2 하향식구문분석 [ 정의 6-1] FIRST 문법 G = (V N, V T, P, S) 가문맥자유문법일때논터미널기호 A에대한 FIRST는다음과같다. * FIRST(A) = {b V T {ε} A bβ, β V * } 즉논터미널기호 A 로부터유도되어첫번째로나타날수있는터미널기호의집합이다. [ 예제 6-2] FIRST 구하기 1 다음문법에서각논터미널기호에대한 FIRST 를구해보자. S C D C ac b D cd d [ 풀이 ] 논터미널기호는 S, C, D 이므로이것들에대한 FIRST 를구하면된다. S C ac 로유도되므로 a 는 S 의 FIRST 이다. S C b 로유도되므로 b 는 S 의 FIRST 이다. S D cd 로유도되므로 c 는 S 의 FIRST 이다. S D d 로유도되므로 d 는 S 의 FIRST 이다. FIRST(S) = {a, b, c, d} 13
6.2 하향식구문분석 C ac로유도되므로 a는 C의 FIRST이다. C b로유도되므로 b는 C의 FIRST이다. FIRST(C) = {a, b} D cd로유도되므로 c는 D의 FIRST이다. D d로유도되므로 d는 D의 FIRST이다. FIRST(D) = {c, d} 그러므로 FIRST(S) = {a, b, c, d} FIRST(C) = {a, b} FIRST(D) = {c, d} 14
6.2 하향식구문분석 [ 예제 6-3] FIRST 구하기 2 다음문법에서각논터미널기호에대한 FIRST 를구해보자. E TE E +TE ε T FT T *FT ε F (E) id [ 풀이 ] 논터미널기호는 E, E, T, T, F에대한 FIRST를구하면된다. E TE FT E (E)T E 로유도되므로 ( 는 E의 FIRST이다. E TE FT E idt E 로유도되므로 id는 E의 FIRST이다. FIRST(E) = {(, id} E +TE 로유도되므로 + 는 E 의 FIRST이다. E ε으로유도되므로 ε은 E 의 FIRST이다. FIRST(E ) = {+, ε} 15
6.2 하향식구문분석 T FT (E)T 로유도되므로 ( 는 T의 FIRST이다. T FT idt 로유도되므로 id는 T의 FIRST이다. FIRST(T) = {(, id} T *FT 로유도되므로 * 는 T 의 FIRST이다. T ε으로유도되므로 ε은 T 의 FIRST이다. FIRST(T ) = {*, ε} F (E) 로유도되므로 ( 는 F의 FIRST이다. F id로유도되므로 id는 F의 FIRST이다. FIRST(F) = {(, id} 그러므로 FIRST(E) = {(, id} FIRST(E ) = {+, ε} FIRST(T) = {(, id} FIRST(T ) = {*, ε} FIRST(F) = {(, id} 16
6.2 하향식구문분석 [ 정의 6-2] nullable 하다 논터미널 A 가 을유도할수있으면 A 를 nullable 하다고부른다. * 즉, A 이면 nullable 하다. [ 예제 6-4] nullable 한지검사하기 1 [ 예제 6-3] 의문법에서 E 는 nullable 한가? [ 풀이 ] E TE FT E (E)T E 로유도되므로 nullable 하지않다. [ 정의 6-3] ring sum 1. A then A B = A 2. if A then A B = if (A { }) B. [ 정의 6-4] FIRST(A 1 A 2 A n ) FIRST(A 1 A 2 A n ) = FIRST(A 1 ) FIRST(A 2 ) FIRST(A n ) 즉, 어떤문자열의 FIRST 는문자열의가장왼쪽기호로부터유도되는터미널기호를찾는과정이다. 즉문자열의첫번째기호가 nullable 하면그문자열다음기호의 FIRST 도해당문자열의 FIRST 에속한다. 이렇게 nullable 이아닐때까지기호들의 FIRST 를합집합한것이문자열의 FIRST 가된다. 17
6.2 하향식구문분석 FIRST(X) 계산규칙 1 만약 X 가하나의터미널기호이면 {X} 는 FIRST(X) 에포함된다. 2 만약 X 가하나의논터미널기호이고 X aβ 의생성규칙이존재하면터미널기호인 {a} 는 FIRST(X) 에속한다. 3 만약 X ε 의생성규칙이존재하면 {ε} 도 FIRST(X) 에속한다. 4 만약 X Y 1 Y 2 Y k 의생성규칙이존재하면 FIRST(X) = FIRST(X) FIRST(Y 1 Y 2 Y k ) 이다. [ 예제 6-7] FIRST 구하기 2 [ 예제 6-3] 의문법에서각논터미널기호에대한 FIRST 를 FIRST(X) 계산규칙으로구해보자. [ 풀이 ] 먼저생성규칙형태에따라 2 번규칙을적용하면각논터미널기호는다음과같은초기값을갖는다. FIRST(E) = { } FIRST(E ) = {+} FIRST(T) = { } 18
6.2 하향식구문분석 FIRST(T ) = {*} FIRST(F) = {(, id} 다음으로 3번규칙을적용하면각논터미널기호는다음과같은값을갖는다. FIRST(E) = { } FIRST(E ) = {+, ε} FIRST(T) = { } FIRST(T ) = {*, ε} FIRST(F) = {(, id} 마지막으로 4번과 1번규칙을적용한다. FIRST(E) = FIRST(E) FIRST(TE ) = FIRST(E) (FIRST(T) FIRST(E )) = FIRST(E) FIRST(T) FIRST(T) = FIRST(T) FIRST(FT ) = FIRST(T) (FIRST(F) FIRST(T )) = FIRST(T) FIRST(F) = {(, id} 19
6.2 하향식구문분석 그러므로 FIRST(E) = {(, id} FIRST(E ) = {+, ε} FIRST(T) = {(, id} FIRST(T ) = {*, ε} FIRST(F) = {(, id} [ 예제 6-3] 의결과와같다. 20
6.2 하향식구문분석 [ 정의 6-5] FOLLOW(A) 문법 G = = (V N, V T, P, S) 가문맥자유문법일때논터미널기호 A 의 FOLLOW(A) 는다음과같다. FOLLOW(A) = {a V T {$} S αaaβ, α, β V * } * FOLLOW(A) 는어떤문장형태에서논터미널기호 A 다음에나오는터미널기호들의집합이다. 여기서 $ 는입력문자열의끝을나타내는기호이고, 시작기호에대한 FOLLOW 는 $ 이다. [ 예제 6-9] FOLLOW 구하기 2 [ 예제 6-3] 의문법에서 FOLLOW를구해보자. [ 풀이 ] [ 예제 6-3] 의문법에다음과같은생성규칙번호를부여한다. 1 E TE 2 E +TE ε 3 T FT 4 T *FT ε 5 F (E) id 21
6.2 하향식구문분석 먼저 FOLLOW(E) 를구한다. E 가시작기호이므로입력문자열의끝에 $ 가있다. 또한 5 번생성규칙에서 E 다음에 ) 가있다. FOLLOW(E) = {$, )} 다음으로 FOLLOW(E ) 를구한다. 1 번생성규칙 E TE 에서 E 다음에나오는기호는 E 다음에나오는기호가됨을알수있다. 따라서 FOLLOW(E) 에속하는기호는 FOLLOW(E ) 에도속한다. 즉 FOLLOW(E) FOLLOW(E ) 그밖에더이상 FOLLOW(E ) 가없다. FOLLOW(E ) = FOLLOW(E) 다음으로 FOLLOW(T) 를구한다. 1 번생성규칙 E TE 에서 FOLLOW(T) FIRST(E ) = {+} 임을알수있다. 단, ε 은제외된다. 그런데 2 번생성규칙에서 E ε 이므로 1 번생성규칙은 E T 가된다. 따라서 FOLLOW(E) 에속하는기호는 FOLLOW(T) 에도속한다. 즉 FOLLOW(T) FOLLOW(E) = {$, )} FOLLOW(T) = {$, ), +} 다음으로 FOLLOW(T ) 를구한다. 3 번생성규칙 T FT 에서 FOLLOW(T ) FOLLOW(T) = {$, ), +} 임을알수있다. FOLLOW(T ) = {$, ), +} 22
6.2 하향식구문분석 다음으로 FOLLOW(F) 를구한다. 3 번생성규칙 T FT 에서 FOLLOW(F) FIRST(T ) = {*} 임을알수있다. 단, ε 은제외된다. 그런데 4 번생성규칙에서 T ε 이므로 3 번생성규칙은 T F 가된다. 따라서 FOLLOW(F) FOLLOW(T) = {$, ), +} 이다. FOLLOW(F) = {$, ), +, *} 그러므로 FOLLOW(E) = {$, )} FOLLOW(E ) = {$, )} FOLLOW(T) = {$, ), +} FOLLOW(T ) = {$, ), +} FOLLOW(F) = {$, ), +, *} 23
6.2 하향식구문분석 FOLLOW(A) 계산규칙 1 만약 A 가시작기호이면 $ 는 FOLLOW(A) 에속한다. 2 만약 B αaβ, β ε 인생성규칙이존재하면 A 의 FOLLOW 에 ε 을제외한 FIRST(β) 를첨가한다. 3 만약 B αa 이거나 B αaβ 에서 β ε 이면 B 의 FOLLOW 전체를 A 의 FOLLOW 에첨가한다. * [ 예제 6-11] FOLLOW 구하기 4 [ 예제 6-3] 의문법에서 FOLLOW 를구해보자. [ 풀이 ] 먼저 FOLLOW 의 1 번규칙에의해 FOLLOW(E) = {$} 이다. 그리고 FOLLOW 의 2 번규칙에의해 E +TE, T *FT, F (E) 를적용하면다음을얻는다. FOLLOW(T) FIRST(E ) = {+} (ε 은제외 ) FOLLOW(F) FIRST(T ) = {*} (ε 은제외 ) FOLLOW(E) FIRST( )) = { )} 24
6.2 하향식구문분석 다음으로 FOLLOW 의 3 번규칙에의해 E TE, T FT 를적용하면다음과같다. FOLLOW(E ) FOLLOW(E) = {$, )} FOLLOW(T ) FOLLOW(T) = {+} 또한 FOLLOW 의 3 번규칙에의해 E TE, E ε 과 T FT, T ε 이다. FOLLOW(T) FOLLOW(E) = {$, )} FOLLOW(F) FOLLOW(T) = {+} 그러므로 FOLLOW(E) = {$, )} FOLLOW(E ) = {$, )} FOLLOW(T) = {$, ), +} FOLLOW(T ) = {$, ), +} FOLLOW(F) = {$, ), +, *} 25
6.2 하향식구문분석 [ 정의 6-6] LL 조건 LL 조건은임의의생성규칙 A α β P 에대해다음조건을만족해야한다. FIRST(α) FIRST(β) =ø; if ε FIRST(α) then FOLLOW(A) FIRST(β) =ø [ 예제 6-13] LL 조건검사하기 [ 예제 6-3] 의문법이 LL 조건을만족하는지알아보자. [ 풀이 ] [ 예제 6-7] 과 [ 예제 6-11] 에서구한 FIRST와 FOLLOW를이용하여검사한다. FIRST(E) = {(, id} FIRST(E ) = {+, ε} FIRST(T) = {(, id} FIRST(T ) = {*, ε} FIRST(F) = {(, id} 26
6.2 하향식구문분석 FOLLOW(E) = {$, )} FOLLOW(E ) = {$, )} FOLLOW(T) = {$, ), +} FOLLOW(T ) = {$, ), +} FOLLOW(F) = {$, ), +, *} LL 조건을검사하면다음과같다. 생성규칙 E +TE ε에서 FIRST(+TE ) FOLLOW(E ) = {+} {$, )} =ø 생성규칙 T *FT ε에서 FIRST(*FT ) FOLLOW(T ) = {*} {$, ), +} =ø F (E) id에서 FIRST((E)) FIRST(id) = {( } {id} =ø 그러므로 LL 조건을만족하며이문법은 LL 문법이다 27
6.2 하향식구문분석 재귀적하강구문분석 LL 방법을실제로파싱으로사용하는구문분석기 재귀적하강구문분석 (Recursive-descent parsing) 예측구문분석 (Predictive parsing) 재귀적하강구문분석 LL 방법의일종 주어진입력문자열을구문분석하기위해재귀적프로시저를사용 재귀적프로시저는각논터미널에해당하는것으로논터미널에대한유도를재귀적프로시저호출로처리하는방법 재귀적하강구문분석기를구현하는방법 각논터미널기호에대한프로시저를작성하고터미널기호에대한프로시저를작성한다음이를통합함으로써구현할수있다. 터미널기호에대한프로시저는생성규칙에있는터미널기호와입력기호가같은지비교하여만일같은경우다음입력기호를읽게하면된다. 또한논터미널기호의경우현재의입력기호를생성할수있는적절한생성규칙이선택되도록프로시저를작성한다. 28
6.2 하향식구문분석 재귀적하강구문분석 주어진문자열에대한구문분석은먼저현재의입력기호를보고시작기호에대한프로시저를호출한다. 그리고마지막에는현재의입력기호가입력의끝을나타내는 $ 이면 accept 이고, 그렇지않으면에러로처리한다. 재귀적하강구문분석은문법으로부터재귀적프로시저를이용하여구문분석기를쉽고도빠르게구성할수있으며오류가발생할가능성이적다는것이장점이다. 반면에프로시저를부르는시간이많이걸려서속도가느리고구문분석기의크기가커진다는단점이있다. 또한결정적인구문분석이되지않아역추적이필요할수도있다. 게다가생성규칙에대한프로시저를작성함으로써생성규칙이바뀔때마다구문분석기전체를다시고쳐야한다. [ 예제 6-14] 재귀적하강구문분석기를만들고구문분석하기 다음문법에대해재귀적하강구문분석기를만들고문장 aaabbb$ 의구문분석을해보자. S aab A as A b 29
6.2 하향식구문분석 [ 풀이 ] 먼저각터미널기호와논터미널기호에대한프로시저를작성한다. 1. 터미널기호에대한프로시저 procedure pa; begin if nextsymbol = qa then get_nextsymbol else error end; procedure pb; begin if nextsymbol = qb then get_nextsymbol else error end; 30
6.2 하향식구문분석 2. 논터미널기호에대한프로시저 procedure PS; begin if nextsymbol = qa then begin pa; PA: pb end; else error end; procedure PA; begin case nextsymbol of qa : begin pa; PS end; qb : pb; otherwise : error end end; 31
6.2 하향식구문분석 3. 주프로그램에대한프로시저 begin get_nextsymbol; PS; if nextsymbol = q$ then accept else error end; 이렇게작성된재귀적하강구문분석기에서문자열 aaabbb$ 의구문분석을해보자. 먼저주프로그램에대한프로시저에서는 get_nextsymbol 에의해 nextsymbol 이 a 가되고프로시저 PS 를호출한다. PS 에서 nextsymbol 이 a 이므로 get_nextsymbol 에의해 nextsymbol 이 b 가되고프로시저 PA 를호출한다. PA 에서 nextsymbol 이 b 이므로 get_nextsymbol 에의해 nextsymbol 이다시 b 가되고프로시저 PS 로리턴된다. 다시 PS 에서 nextsymbol 이 b 이므로 get_nextsymbol 에의해 nextsymbol 이 $ 가되고주프로그램으로리턴된다. nextsymbol 이 $ 이므로 accept 된다. 32
6.2 하향식구문분석 예측구문분석 생성규칙이바뀌더라도전체구문분석기를고치지않고단지구문분석기의행동을제어하는파싱테이블 (parsing table) 만수정해서구문분석기를구현하는방법 실제로스택을이용하여구현하며입력과스택, 파싱테이블, 출력으로구성 입력은구문분석이될입력문자열과 $ 을저장하고, 스택은문장형태에서입력문자열과아직매칭되지않은부분을유지하며 bottom marker 로역시 $ 를갖는다. 출력은파스트리나구문분석시적용된일련의생성규칙번호 ( 좌파스 ) 가될수있다. 33
6.2 하향식구문분석 구문분석기는주어진입력문자열을왼쪽에서오른쪽으로읽고, 현재입력기호와스택의톱기호에따라파싱표에서주어진행동을취하며구문분석을한다. 예측구문분석기의행동은제거, 확장, 인식, 에러등이며그의미는다음과같다. 제거 (pop) : 스택의톱과현재의입력기호가같은경우로, 스택의톱기호를제거하고현재의입력기호를입력문자열에서제거한다. 현재의입력기호를입력문자열에서제거한다는것은입력버퍼의제어가오른쪽으로한자리이동하고다음기호를검조한다는의미이다. 확장 (expand) : 스택의톱이논터미널기호인경우로, 생성규칙을적용하여확장한다. 즉생성규칙의왼쪽기호대신에오른쪽문자열로대치하는것이다. 인식 (accept) : 스택의톱과현재의입력기호가모두 $ 인경우로, 입력문자열이올바른문자열임을알려준다. 여기서 $ 는문자열의끝과스택의바닥을나타낸다. 즉구문분석시스택의초기상태는 $S 로출발하며입력문자열은 w$ 로표시한다. 에러 (error) : 스택의톱이논터미널기호인경우로, 그기호로부터현재보고있는기호를유도할수없음을나타낸다. 34
6.2 하향식구문분석 [ 알고리즘 6-1] 예측파싱표구성방법 [ 입력 ] LL 문법 [ 출력 ] 예측파싱표 M [ 방법 ] begin for each A α P do begin for a FIRST(α) do M[A, a] = A α; if α * ε then for b FOLLOW(A) do M[A, b] = A α end end. 35
6.2 하향식구문분석 [ 예제 6-15] 예측파싱표구성하기 36
6.2 하향식구문분석 [ 예제 6-17] 예측구문분석 37
상향식구문분석은주어진문장이문법에맞는지아닌지를검사하기위해입력 된문자열을읽어가면서감축에의해시작기호를찾아가는방법이다. 주어진문 자열이시작기호로감축되면올바른문장이라고판단하여파스트리를생성하 고, 그렇지않으면올바르지않은문장으로서에러메시지를출력한다. [ 정의 6-7] 감축과핸들 S * αaw αβw의유도과정이존재할때문장형태 αβw에서 β를 A로대체하는것을감축 (reduce) 이라하고, β를문장형태 αβw의핸들 (handle) 이라한다. 즉한문장형태에서감축되는부분이핸들이다. [ 정의 6-18] 우단유도와핸들찾기 앞에서자주사용한다음문법에서문장 id + id * id 에대해우단유도과정을보이고핸들을찾아보자. 1 E E + T 3 T T * F 5 F (E) 2 E T 4 T F 6 F id 38
[ 풀이 ] 우선우단유도를하자. E E + T (1) E + T * F (13) E + T * id (136) E + F * id (1364) E + id * id(13646) T + id * id(136462) F + id * id(1364624) id + id * id(13646246) 상향식구문분석은우단유도의역순이다. 그러므로 id + id * id 에대한상향식구문분석과정은다음과같다. 39
40
다음으로핸들을찾아보자. id 를구별하기위해 id1, id2, id3 이라고한다. 41
[ 정의 6-8] 핸들대체 S 1 2 n-1 n (= ) 의유도과정이있을때각 의 i 문장형태 rm rm rm rm rm 에서핸들을찾아 i-1 로가면서시작심벌로감축되는과정을핸들대체 (handle pruning) 라고한다. 이동 - 감축 (shift-reduce) 구문분석 이동 - 감축구문분석은상향식방법의일종 스택 (stack) 과입력버퍼 (input buffer) 를사용하여구현 스택은보통파싱스택 (parsing stack) 이라부르며문장형태에서핸들을찾을때까지필요한문법심벌들을유지하고입력버퍼는주어진문자열을보유 이동 - 감축구문분석기 42
이동 - 감축구문분석기의행동 이동 (Shift) : 현재의입력기호를스택의톱에옮기는것을의미 이과정은스택의톱에핸들이나타날때까지계속 감축 (Reduce) : 핸들이스택의톱에나타나면스택의톱이핸들의오른쪽끝이되고, 핸들의왼쪽끝을찾아서완전한핸들을찾은다음핸들에해당되는생성규칙의왼쪽에있는기호로대체되는것 수락 (Accept) : 주어진문자열이주어진문법에맞는문장이라는것을나타냄. 에러 (Error) : 주어진문장이주어진문법에맞지않는문장임을의미하고에러처리호출한다. 43
다음의이동 - 감축구문분석과정을살펴보자. 1 입력문자열을읽고핸들을발견한다. 2 핸들을찾으면감축하고부분파스트리를구성한다. 3 같은방법으로계속진행한다. 4 입력문자열을모두읽은후시작기호를만나면주어진문장은맞는문장이된다 [ 예제 6-20] 이동 - 감축구문분석 2 다음문법에서문장 id + id * id 에대해이동 - 감축구문분석을해보자. 1 E E + E 2 E E * E 3 E id 4 E (E) 44
[ 풀이 ] 구문분석을하기전에문장 id + id * id 가생성되는지우단유도를해본다. E E + E E + E * E E + E * id E + id * id id + id * id 시작기호로부터문장 id + id * id 가생성되므로주어진문장은이동 - 감축구문분석에의해구문분석을하면맞는문장이라고해야할것이다. 구문분석을하려면파싱표가있어야하지만파싱표없이앞에서우단유도한역순으로구문분석을한다. 45
그런데 [ 예제 6-20] 의경우여러가지문제가대두된다. 두번째줄을보면핸들이 id 가되어 id 를 E 로감축했다. 하지만이경우에감축하지않고 + 를이동할수도있다. 즉두번째줄은감축할수도있고이동할수도있다는문제점이있다. 마찬가지로다섯번째줄에서 id 가핸들이되어 E 로감축할수도있고 * 를이동할수도있으며, 여섯번째줄에서도 * 를이동했지만 E + E 가핸들이될수도있다. 이와같이이동 - 감축구문분석에서는핸들을어떻게찾을것인지, 그리고찾은핸들에대해생성규칙이여러개존재한다면어떤생성규칙을적용할것인지에대한문제가발생한다. 먼저핸들을어떻게찾을것인가에대한해결방법으로우선순위구문분석방법이등장했다. 46
연산자우선순위구문분석 연산자우선순위구문분석 (operator precedence parsing) 은연산자상호간의우선순위관계 (operator precedence relation) 에의해핸들을찾는방법으로연산자우선순위문법이필요하다. [ 정의 6-9] 연산자우선순위문법 연산자우선순위문법 (operator precedence grammar) 은연산자문법이면서 2 개의터미널기호사이에많아야 1 개의연산자우선순위관계를갖는것을말한다. 이문법에의해정의된언어를연산자우선순위언어라고한다. 어떤문법이주어졌을때그문법이연산자우선순위문법인지바로알수가없다. 연산자우선순위관계는연산자우선순위파싱표를만들어봐야알수있기때문이다. 47
연산자우선순위구문분석방법은연산자우선순위문법이주어졌을때생성규칙의문법기호상호간의연산자우선순위관계에의해핸들을찾는방법으로상향식구문분석방법이다. 이방법은파싱표를작성하기가쉽고연산자간에우선순위를정하여구문분석을할수있어산술식을위한구문분석방법으로아주적당하다. 반면에구문분석되는문법의범위가작고터미널과터미널만의우선순위관계에의해핸들을찾으므로구문분석이완전하게되지않는다는단점이있다. 그럼에도불구하고단순성때문에연산자우선순위구문분석기를사용한컴파일러가많이만들어졌다. 연산자우선순위구문분석기는연산자우선순위관계를가진연산자우선순위문법을사용한다. 연산자우선순위구문분석이정확히이뤄지도록연산자우선순위관계를만드는여러가지방법이있다. [ 예제 6-20] 의문법에대해적합한우선순위관계를얻기위해다음과같은경험적방법을사용해보자. [ 예제 6-20] 에주어진문법은모호한문법이다. 다음규칙은이항연산자에대해결합법칙과우선순위를반영하여적절한핸들을선택하게한것이다. 48
1 만약연산자 θ1 이연산자 θ2 보다우선순위가높다면 θ1 θ2 그리고 θ2 θ1 이다. 예를들어 * 가 + 보다높은우선순위일때 * + 그리고 + * 이다. 이러한관계를통해식 E + E * E + E 에서가운데에있는 E * E 가가장먼저감축될핸들임을알수있다. 2 만약연산자 θ1 과 θ2 가동일한우선순위이고연산자들이왼쪽결합법칙을가지면 θ1 θ2 그리고 θ2 θ1 이다. 또한연산자들이오른쪽결합법칙을가지면 θ1 θ2 그리고 θ2 θ1 이다. 예를들어 + 가왼쪽결합법칙을가지면 + + 이다. 3 모든연산자 θ 에대해 θ id, id θ, θ (, ( θ, ) θ, θ $, $ θ 이다. 또한다음과같이되게한다. ( ) $ ( $ id ( ( id $ ) $ ( id id ) ) ) 이규칙은 id 와 (E) 를모두 E 로축소시킨다. 또한 $ 와 $ 사이어디에서나핸들이발견되어야하므로 $ 는스택의톱과입력버퍼오른쪽끝의표시 (right endmarker) 로사용된다. 49
[ 예제 6-22] 연산자우선순위구문분석 2 [ 예제 6-20] 의문법에 [ 예제 6-21] 의연산자우선순위파싱표를적용하여문장 id + id * id 에대해연산자우선순위구문분석을해보자. 1 E E + E 2 E E * E 3 E id 4 E (E) [ 풀이 ] 문장 id + id * id 를구문분석하는과정은다음과같다. 구문분석이완전히이루어지지않는다. 우선순위문법을이용한방법은문법의제약이많고, 구문분석시에도어떻게핸들을정확하게찾을것인지, 여러개의핸들이존재하면어떻게핸들을결정할것인지등의문제가있다. 이러한문제를해결하기위한방법이바로 LR 구문분석이다 50
LR 구문분석 결정적인상향식구문분석방법 LR (Left to right scanning and Right parse) 은입력문자열을왼쪽에서오른쪽으로읽어가며, 출력으로우파스를생성 LR 방법으로구문분석을행하는구문분석기 : LR parser 주요내용 주어진문법으로부터파싱테이블을구성하는이론과방법 파싱테이블이주어졌을때, LR 파서가어떻게동작하는가? 모호한문법으로부터파싱테이블을구성하는방법 LR 파서를실제적인컴파일러의구문분석기로구현하는내용 51
LR 구문분석의장점 LR 구문분석기는모호하지않은문맥자유문법으로쓰인모든프로그래밍언어에대해구성이가능하다. LR 구문분석방법은가장일반적인역추적이없는결정적인이동 - 감축구문분석방법이다. LR 구문분석기는입력을왼쪽에서오른쪽으로검조하면서구문오류를쉽게발견할수있다. LR 구문분석의단점 프로그래밍언어에대해 LR 구문분석기를직접작성하는일이너무방대한작업 LR 구문분석종류 - 파싱표를어떻게구성하느냐에따라 SLR(simple LR) 구문분석 - LR(0) 항목의집합과 FOLLOW CLR(canonical LR) 구문분석 - LR(1) 항목의집합 LALR(lookahead LR) 구문분석 - LR(0) 항목의집합과 lookahead 로부터 또는 LR(1) 항목의집합 52
LR 구문분석기의구성 이동 - 감축구문분석기와마찬가지로구동프로그램및 action 과 GOTO 두부분을포함한파싱표로구성되고파싱표의행동도이동 - 감축구문분석기와똑같다. 구동프로그램은 LR 구문분석기가모두같지만파싱표는구문분석기에따라다르다. LR 구문분석에대한장단점 SLR 방법은구현하기가쉽지만강력하지못하며, CLR 방법은가장강력하지만구현하기가매우어렵다. LALR 방법은 SLR 과 CLR 의중간형태로강력함은 CLR 과유사하고파싱표의크기는 SLR 방법으로구성가능. 이세가지방법의부분집합관계는 [ 그림 6-4] 와같다. 53
LR 파싱표행동구성 상태번호 기호 ACTION 표 V T {$} GOTO 표 V N 0 이동 (shift) 1 2 감축 (reduce) 수락 (accept) 상태번호 에러 (error) LR 파싱표의 4 가지행동 1. 이동 : ACTION[S m, a i ] = 이동 S S m 상태에서입력기호 a i 를본행동이이동 S 라는것은 입력기호를스택으로이동하고다음상태를 S 로만들기위해 S 도 stack 에넣는다. 는의미 2. 감축 : ACTION[S m, a i ] = 감축 A S m 상태에서입력기호 a i 를본행동이감축 A 라는의미는스택에서핸들 를 제거하고스택에생성규칙의오른쪽부분을다음상태와함께스택에넣는다. 54
3. 수락 : ACTION[S m, a i ] = 수락 S m 상태에서입력기호 a i 를본행동이수락이라면주어진문자열이올바른문자열이라는의미이며 parsing 을끝낸다. 4. 에러 : ACTION[S m, a i ] = 에러 S m 상태에서입력기호 a i 를본행동이에러라면입력문자열이틀린문자열이라는의미이며일반적으로에러처리루틴을불러처리 [ 정의 6-10] LR(k) 문법 LR(k) 문법은모든항목 (entry) 에대해유일하게정의되는파싱표를만들수있는문법을말한다. 여기서 k 를 lookahead 의길이이다. [ 정의 6-11] 증가문법 G = (V N, V T, P, S) 에서 G 에추가된문법으로 G' = (V N {S'}, V T, P {S' S}, S') 이다. S' : 새로운시작기호 S' S : 추가된생성규칙 생성규칙 S' S 를두는이유 - 주어진문장이안전하게수락되게하기위해사용 55
[ 예제 6-23] 증가문법만들기 다음문법에대해증가문법을만들어보자. 1 E E + E 2 E E * E 3 E id 4 E (E) [ 풀이 ] S E 1 E E + E 2 E E * E 3 E id 4 E (E) 56
[ 정의 6-12] LR(0) 항목 LR(0) 항목은생성규칙의오른쪽에점기호 (dot symbol) 를가진생성규칙이다 [ 예제 6-24] LR(0) 항목구하기 생성규칙 A BCD 에대해 LR(0) 항목을구해보자. [ 풀이 ] LR(0) 항목은생성규칙의오른쪽에점기호를가진것으로다음과같이 4 개가존재한다. [A BCD], [A B CD], [A BC D], [A BCD ] LR(0) 항목 A B CD 의경우 B 는이미읽었고 CD 는앞으로읽을기호임을나타낸다. 그리고 LR(0) 항목 A BCD 는문자열 BCD 를모두읽었고이제 BCD 를 A 로감축할수있음을의미한다. LR(0) 항목을만들기위해생성규칙의오른쪽에점기호를찍는것을마 (marking) 한다고한다. 또한 LR(0) 항목에서점기호다음에있는기호를마크기호 (mark symbol) 라부른다. 57
[ 정의 6-13] LR(0) 항목의세가지종류 LR(0) 항목 [A α β] 에서 α ε 이거나 A = S (S 는증가문법의시작기호 ) 이면이항목을커널 (kernel) 항목 LR(0) 항목 [A α] 와같이점기호가생성규칙처음에있는항목을클로저 (closure) 항목 LR(0) 항목 [A α ] 와같이생성규칙끝에점기호가있는항목을감축항목 정규항목집합 (canonical collection) 이라불리는, 어떤문법에대한 LR(0) 항목으로구성된집합은 LR 파싱표를구성하는데반드시필요하다. 주어진문법에대한정규항목집합을구성하려면하나의증가문법과 2개의함수 CLOSURE, GOTO를정의해야한다. 58
[ 정의 6-14] CLOSURE(I) 를구하는규칙 I 가문법 G 에대한 LR(0) 항목으로구성된집합이면 CLOSURE(I) 는다음두가지규칙에따라구한다. 초기에 I 에속한모든 LR(0) 항목을 CLOSURE(I) 에추가한다. [A α Bβ] 가 CLOSURE(I) 에포함되어있고 B γ 의생성규칙이존재하는경우, B γ 가 CLOSURE(I) 에포함되어있지않으면이항목을 CLOSURE(I) 에추가한다. 이러한규칙은새로운 LR(0) 항목이 CLOSURE(I) 에더이상추가될수없을때까지반복적으로계속적용된다. 즉, CLOSURE(I) = I {[B. ] [A.B ] CLOSUR(I), B P} CLOSURE(I) 를구하는알고리즘 [ 알고리즘 6-4] 와같다. [ 예제 6-25] CLOSURE 구하기 다음문법에서 LR(0) 항목 E E와 E E + T의 CLOSURE를구해보자. E E E E + T T T T * F F F (E) id 59
[ 풀이 ] CLOSURE([E E]) = { [E E], [E E+T}, [E T], [T T*F], [T F], [F (E)], [F id]} CLOSURE([E E+ T]) = {[E E + T], [T T*F], [T F], [F (E)], [F id] [ 정의 6-15] GOTO 함수 LR(0) 항목의 GOTO 함수는 I 가항목의집합이고 X V 이면 GOTO(I, X) = CLOSURE({[A αx β] [A α Xβ I}) 이다. [ 예제 6-26] GOTO 함수계산하기 [ 예제 6-25] 의문법에서 I = {[E E ], [E E + T]} 일때 GOTO(I, +) 를계산해보자. [ 풀이 ] GOTO(I, +) = CLOSURE([E E + T]} = {[E E + T], [T T*F], [T F], [F (E)], [F id]} 60
[ 정의 6-16] LR(0) 항목집합의정규항목집합 LR(0) 항목집합의정규항목집합은 C 0 으로표기하며, C 0 = {CLOSURE ({[S S])} {GOTO (I, X) I C 0, X V} 이다. [ 예제 6-27] LR(0) 항목집합의정규항목집합구하기 다음문법에서 LR(0) 항목집합의정규항목집합을구해보자. 1 E E + T 2 E T 3 T T * F 4 T F 5 F (E) 6 F id [ 풀이 ] 1. 먼저증가문법을만든다. S E 1 E E + T 2 E T 3 T T * F 4 T F 5 F (E) 6 F id 2. LR(0) 항목집합의정규항목집합은다음과같다. I0 : CLOSURE([S E]) = {[S E], [E E+T], [E T], [T T*F], [T F], [F (E)], [F id]} GOTO(I0, E) = I1 = CLOSURE([S E ], [E E +T]) = {[S E ], [E E +T]} GOTO(I0, T) = I2 = CLOSURE([E T ], [T T *T]) = {[E T ], [T T *T]} 61
GOTO(I0, F) = I3 = CLOSURE([T F ]) = {[T F ]} GOTO(I0, ( ) = I4 = CLOSURE([F ( E)]) = {[F ( E)], [E E+T], [E T], [T T*F], [T F], [F (E)], [F id]} GOTO(I0, id) = I5 = CLOSURE([F id ]) = {[F id ]} GOTO(I1, +) = I6 = CLOSURE([E E+ T]) = {[E E+ T], [T T*F], [T F], [F (E)], [F id]} GOTO(I2, *) = I7 = CLOSURE([T T* F]) = {[T T* F], [F (E)], [F id]} GOTO(I4, E) = I8 = CLOSURE([F (E )], [E E +T]) = {[F (E )], [E E +T]} GOTO(I4, T) = I2 GOTO(I4, F) = I3 GOTO(I4, ( ) = I4 62
GOTO(I4, id) = I5 GOTO(I6, T) = I9 = CLOSURE([E E+T ], [T T *T]) = {[E E+T ], [T T *T]} GOTO(I6, F) = I3 GOTO(I6, ( ) = I4 GOTO(I6, id) = I5 GOTO(I7, F) = I10 = CLOSURE([T T*F ]) = {[T T*F ]} GOTO(I7, ( ) = I4 GOTO(I7, id) = I5 GOTO(I8, )) = I11 = CLOSURE([F (E) ]) = {[F (E) ]} GOTO(I8, +) = I6 GOTO(I9, *) = I7 63
SLR 구문분석 SLR 구문분석은 LR 구문분석방법중가장간단하게구현할수있는방법으로, LR(0) 항목집합과 FOLLOW 를이용하여 SLR 파싱표를만든다. SLR 파싱표는 LR(0) 항목의정규항목집합으로부터이동과 GOTO 행동을구하고, 생성규칙에있는논터미널기호의 FOLLOW 를가지고감축을결정한다. SLR 구문분석기의파싱표구성은 [ 알고리즘 6-5] 와같다. [ 알고리즘 6-5] SLR 파싱표구성 [ 입력 ] 문법 G = (V N, V T, P, S) [ 출력 ] 증가문법 G 에대한 SLR 파싱표 [ 방법 ] ❶ G 를위한 LR(0) 항목집합의정규항목집합 C0 = {I0, I1,, In} 을구성한다. ❷ 상태 i 는 Ii 에서구성되었다. 상태 i 를위한구문분석동작은다음과같이결정된다. 만약 LR(0) 항목 [A α aβ] Ii, GOTO(Ii, a) = Ij 이면 action 표의 M[i, a] = 이동 j 만약 LR(0) 항목 [A α ] Ii 이면논터미널기호 A 의 FOLLOW(A) 에속한모든기호 a 에대해 action 표의 M[i, a] = 감축 A α 만약 LR(0) 항목 [S S ] Ii 이면 action 표의 M[i, $] = 수락 ❸ 만약 LR(0) 항목 [A α Bβ] Ii 이고 GOTO(Ii, B) = Ij 이면 GOTO 표의 M[i, B] = j ❹ 이렇게해서정의되지않은파싱표의항목들은모두에러가되며, 첨가된생성규칙의 LR(0) 항목 [S S] 를포함하는상태가시작상태이다 64
SLR 구문분석기를만드는과정 1 문법이주어진다. 2 증가문법을만든다. 3 LR(0) 항목집합의정규항목집합을구한다. 4 감축행동을결정하기위해 FOLLOW를계산한다. 5 SLR 파싱표를작성한다. [ 예제 6-28] SLR 파싱표구하기 1 [ 예제 6-27] 의문법에대한 SLR 파싱표를만들어보자. [ 풀이 ] (1) 증가문법 0. S' E 1. E E + T 2. E T 3. T T * F 4. T F 5. F (E) 6. F id (2) LR(0) 항목집합의정규항목집합과 GOTO 그래프 65
66
(3) FOLLOW 의계산 : FOLLOW(E) = {$, +, )} FOLLOW(T) = {*, +, ), $} FOLLOW(F) = {*, +, ), $} 67
(4) 파싱표작성 : 68
[ 알고리즘 6-6] LR 구문분석알고리즘 [ 입력 ] 입력문자열 w와 LR 파싱표 [ 출력 ] 만약 w가 L(G) 안에있으면 w에대한파스트리를생성하고, 그렇지않으면에러 [ 방법 ] 구문분석기는스택의초기상태인 S0을가지고있다. begin ip는 w$ 의처음기호를가르친다. repeat s 는 stack의톱상태 a 는 ip에의해지적된기호 ; if action [s, a] = 이동 s then begin a를스택에삽입하고그다음에 s 를스택에삽입한다. ip 가다음입력기호로이동한다. end else if action [s, a] = 감축 s ( 생성 A β) then begin β 개의기호를스택에서삭제한다. A 를스택에삽입한다. GOTO[s, A] = n이라면 n을스택에삽입한다. end else if action [s, a] = 수락 then return else 에러 until (ip = $ 이고스택의톱 = $) end. 69
[ 예제 6-29] SLR 파싱표를이용하여구문분석하기 [ 예제 6-28] 에서만들어진파싱표를이용하여문장 id * (id * id) 의구문분석을해보자. [ 풀이 ] 파싱표인 [ 표 6-3] 을이용하고 [ 알고리즘 6-6] 을적용하여구문분석을한다. 70
71
[ 예제 6-28] 과 [ 예제 6-29] 에서 SLR 구문분석방법은순위구문분석에서발생한, 핸들을어떻게찾을것인지와핸들이 2개이상인경우정확한핸들을어떻게결정할것인지에대한모든문제를해결했다. 그런데모든 SLR(1) 문법은모호하지않지만 SLR(1) 이아닌모호한문법이존재한다. 다음예제를살펴보자. [ 예제 6-30] SLR 파싱표구하기 2 다음문법에대한 SLR 파싱표를만들어보자. 1 S L = R 2 S R 3 L *R 4 L id 5 R L 72
[ 풀이 ] 1. 증가문법을만든다. S S 1 S L = R 2 S R 3 L *R 4 L id 5 R L 73
74
FOLLOW 를계산한다. FOLLOW(S) = {$} FOLLOW(R) = {$, =} FOLLOW(L) = {$, =} 75
76
[ 표 6-4] 의파싱표에서 2 번상태 : ACTION[2,=] := shift 6 ACTION[2,=] := reduce 5 이동 - 감축충돌 (shift-reduce conflict) [ 예제 6-30] 에주어진문법은 SLR 문법이아니다. 위에서왜이런문제가발생했는지를살펴보자. 지금 2 번상태에서다음입력으로 = 를만나게되면충돌발생한다. 감축이발생한이유는 2 번상태에서감축항목에있는 R 에대해서 FOLLOW 를계산했다. FOLLOW(R) = {$, =} 이다. 그런데실제로는 R 다음에 = 이나타나는우문장형태는존재하지않는다. 따라서 2 번상태에서감축행동은유효하지않다. SLR 구문분석기를구성할때충돌이발생하는것은 SLR 문법이충분히강력하지않기때문이다. 그래서결정적인 LR 파싱을하기위해 SLR 문법보다훨씬강력한 CLR 문법과 LALR 문법으로구문분석기를작성 충돌의종류는이동 - 감축충돌과감축 - 감축충돌 (reduce-reduce conflict) 이있는데이에 대해서는 4 절에서좀더자세히설명하겠다. 77
CLR 구문분석 SLR 방법에서파싱표를작성할때 FOLLOW 에속하는기호에대해감축행동을만들었다. 그러나어떤상태에서는감축항목 [A α ] 에대한 FOLLOW(A) 에는속하지만그상태에서 A 다음에나올수없는기호가존재한다. 반면에한상태에서어떤논터미널기호다음에나올수있는정확한터미널기호를 lookahead 라고하는데, 이를이용하는방법이 CLR 구문분석이다. LR(0) 항목에서 lookahead 정보를첨가한것이 LR(1) 항목이며, 이는 [ 정의 6-17] 과같다. [ 정의 6-17] LR(1) 항목 LR(1) 항목은 [A α β, a] 형태이며, 여기서 A αβ P 이고 a {V T $} 이다. 첫번째부분인 A α β 를코어 (core) 라하며, 이는 LR(0) 항목과같은의미이다. 두번째부분인 a 를 lookahead 라하며, 이는감축항목일때그기호에대해감축행동을하라는것이다. 78
CLR 파싱표작성 LR(1) 항목집합의정규항목집합으로구성 CLOSURE 함수와 GOTO 함수가필요 GOTO 함수는 LR(0) 항목집합의정규항목집합을구할때와같지만, CLOSURE 함수는 lookahead 정보때문에약간수정해야함 [ 정의 6-18] LR(1) 항목에서의 CLOSURE 함수구하기 CLOSURE(I) = I {[B., b] [A.B, a] CLOSURE(I), B. P, b FIRST( a)} LR(1) 항목집합의 CLOSURE 는 LR(0) 항목집합의 CLOSURE 와유사하며 lookahead 를구해서첨가하는것만이차이점 [A.B, a] 에서마크기호 B 다음에오는 의 FIRST 가항목 [B. ] 의 lookahead 만일 가 을유도할수있으면, 항목 [A.B ] 의 lookahead 인 a 도 lookahead 가된다. 항목 [B. ] 의 lookahead 는 a 의 FIRST 가된다. 79
[ 예제 6-31] LR(1) 항목에대한 CLOSURE 구하기 다음문법에서 LR(1) 항목 [S S, $] 에대한 CLOSURE를구해보자. S S S CC C Cc C d [ 풀이 ] CLOSURE([S S, $]) = {[S S, $], [S CC, $], [C cc, c/d], [C d, c/d]} 여기서 [C cc, c/d] 는 2개의항목 [C cc, c] 와 [C cc, d] 가축약된표현이다. 80
LR(1) 항목의정규항목집합을만드는방법은 SLR에서 LR(0) 항목의정규항목집합을구하는방법과동일하며, 이는 [ 알고리즘 6-7] 과같다. [ 예제 6-31] LR(1) 항목에대한 CLOSURE 구하기 다음문법에서 LR(1) 항목 [S S, $] 에대한 CLOSURE를구해보자. S S S CC C Cc C d [ 풀이 ] CLOSURE([S S, $]) = {[S S, $], [S CC, $], [C cc, c/d], [C d, c/d]} 여기서 [C cc, c/d] 는 2개의항목 [C cc, c] 와 [C cc, d] 가축약된표현이다. 81
[ 예제 6-32, 33] LR(1) 항목의정규항목집합구하고구문분석하기 다음문법에서 LR(1) 항목의정규항목집합을구해보자. S CC C cc C d [ 풀이 ] (1) 증가문법 : 0. S' S 1. S CC 2. C cc 3. C d 82
(2) CLR 정규항목집합과 GOTO 그래프 83
(3) CLR 파싱표 84
(4) 문장 ccdd 의구문분석은다음과같다. 85
이제 [ 예제 6-30] 에서 SLR 파싱표를구했으나충돌이발생하여 SLR 문법이아닌것을확인한문법에대해이번에는 C LR 파싱표를구해보자. [ 예제 6-34] CLR 파싱표구하고구문분석하기 2 [ 예제 6-30] 에서만든 LR(1) 항목의정규항목집합을이용하여 CLR 파싱표를구성하고, 이파싱표를이용하여 * id = id 의구문분석을해보자. [ 풀이 ] (1) 다음과같이증가문법을만든다. S S 1 S L = R 2 S R 3 L * R 4 L id 5 R L 86
87
SLR 파싱표에서나타났던충돌문제가 CLR 파싱표에서는나타나지않는다. 그러므로예제에주어진문법은 SLR 문법은아니지만 CLR 문법에는맞는다는것을알수있다. 88
문장 * id = id 의구문분석은다음과같다. 89
CLR 방법은 SLR 방법보다매우강력하지만 lookahead 를구해야하므로과정이복잡하고시간이오래걸리며파싱표가커진다는단점이있다. 따라서이러한단점을보완하기위해 LR(1) 의경우처럼감축행동은 lookahead 를이용하고파싱표의크기는되도록작게구성할수있는방법을적용하게되었는데이를 LALR 방법이라한다. LALR 방법을이해하기위해다음예제를살펴보자 [ 예제 6-35] CLR 파싱표를구성하고 SLR 파싱표와 CLR 파싱표의크기비교 [ 예제 6-27] 의문법에대해 [ 예제 6-28] 에서 SLR 파싱표를만들었다. 이문법에대한 CLR 파싱표를구성하고 SLR 파싱표와 CLR 파싱표의크기를비교해보자. [ 풀이 ] 1. 다음과같이증가문법을만든다. E E 1 E E + T 2 E T 3 T T * F 4 T F 5 F (E) 6 F id 90
2. CLR 파싱표 91
[ 표 6-3] 의 SLR 파싱표와 [ 표 6-7] 의 CLR 파싱표를비교해보자. 똑같은예제를가지고 SLR 파싱표와 CLR 파싱표를작성했는데 SLR 파싱표는 12 9 행렬이고 CLR 파싱표는 22 9 행렬이다. 단순비교이지만 SLR 방법이 CLR 방법보다파싱표의크기를작게할수있음을알수있다. 92
LALR 구문분석 LALR 구문분석방법은 lookahead 정보를이용하기때문에 lookahead LR 방법이라고도한다. SLR 방법보다훨씬강력하고, 파싱표의크기가 CLR 방법보다상당히작으면서도프로그래밍언어의구문구조를대부분편리하게표현할수있다는것이장점이다. 파싱표의크기를비교해보면 SLR 파싱표와 LALR 파싱표는주어진문법에대해항상동일한개수의상태로만들수있으며, C 언어의경우전형적으로수백개정도이다. 반면에 CLR 파싱표는동일한규모의언어에대해전형적으로수천개의상태이다. 그러므로 CLR 파싱표보다 SLR 파싱표나 LALR 파싱표를구성하는것이훨씬더쉽고경제적이다. 또한모호하지않은문맥자유문법으로표현된거의모든언어를인식할수있으며, 에러를초기에탐지할수있다. 그러나 LALR 방법은 LR(0) 항목의집합을구한후파싱표를만들기위해감축항목이있는각상태에서 lookahead 기호를구하는데상당한시간과노력이소요된다. LALR 파싱표를구성하는방법은두가지가있다. 파싱표를구성하기가쉽지만파싱표의크기가커지는 LR(1) 을가지고구성하는방법과효율적으로파싱표를구성할수있는 LR(0) 과 lookahead 를가지고구성하는방법이그것이다. 첫번째방법은먼저 LR(1) 항목을가지고파싱표를구성하는방법으로같은코어를가진 LR(1) 항목을묶어서하나의상태로구성하는것이며, lookahead 는 LR(1) 항목의 lookahead 를합한것이다. 93
[ 예제 6-36] CLR 파싱표로부터 LALR 파싱표구하기 [ 예제 6-32] 의문법과 [ 예제 6-33] 의 CLR 파싱표를가지고 LALR 파싱표를구해보자. [ 풀이 ] [ 예제 6-32] 의 [ 그림 6-7] 에서 LR(1) 항목의정규항목집합을구했다. 여기서코어가같은상태를찾아보자. 우선상태 I3 과 I6 이같은코어를가지므로다음과같다. I3 I6 I36 = {[C c C, c/d/$], [C cc, c/d/$], [C d, c/d/$]} 같은방법으로다음과같이된다. I4 I7 I47 = [[C d, c/d/$]} I8 I9 I89 = {[C cc, c/d/$]} 따라서 LALR 파싱표는 [ 표 6-8] 과같다. 94
95
LALR parsing table 작성방법 LR(1) 항목의집합으로부터작성하는방법 이론적으로쉽게설명 C 1 의크기가너무커져서실질적인방법이되지못함» Lookahead에따라상태수가매우커지고시간이오래걸리기때문 LR(0) 항목의집합으로부터작성하는방법 이론적으로복잡하고어려움 시간과기억공간이작아지는실질적인방법 96
[ 정의 6-19] lookahead 의정의 상태 p 에서 LR(0) 항목 [A. ] 의 lookahead 는 LA(p, [A. ]) 로표기하며 p 상태에서 A 다음에나올수있는터미널기호의집합이다. LA(p, [A. ]) = {a a FIRST( ), S' A, accesses p}. 가상태 p 를 access 한다는것은시작상태로부터 만큼보고상태 p 로이동 을하였다는의미 [ 예제 6-38] LALR 파싱표를구성하고구문분석하기 [ 예제 6-30] 과 [ 예제 6-34] 에서같은문법을가지고 SLR 파싱표와 CLR 파싱표를만들었다. 이번에는 LALR 파싱표를만들고문장 * id = id 의구문분석을해보자. * 97
98
99
100
[ 표 6-9] 의파싱표에 2개이상의행동이함께정의되어있지않으므로주어진문법은 LALR 문법이다. [ 예제 6-30], [ 예제 6-34], [ 예제 6-38] 에서한가지문법을가지고 SLR, CLR, LALR 파싱표를만들어보았다. 파싱표에충돌이있는지없는지에따라문법을말할수있는데, 이문법은 CLR, LALR 문법이지만 SLR 문법은아니다. CLR, LALR 문법에맞으므로파싱표의크기를비교할수있으며, LALR 파싱표가 CLR 파싱표보다매우작다. 101
6.4 모호한문법의사용과에러처리루틴 모호한문법의사용과에러처리루틴 모호한문법은언어의명세에서매우유용하다. 표현식과같은언어구조에대해모호한문법은동등한모호하지않은문법보다더짧고더자연스러운명세를제공한다. 즉모호한문법은동등한모호하지않은문법보다문법의표현이간단하며, 사람들이사용하기에훨씬자연스러운문법이다. 모호한문법을가지고파싱표를작성하면항상이동 - 감축충돌이나감축 - 감축충돌을야기한다. 이러한충돌을없애는두가지방법이있다. 첫번째방법은앞에서다루었던모호한문법을동등한의미를가진모호하지않은문법으로변환하는것이다. 두번째방법은모호한문법을가지고파싱표를작성한다음파싱표에서발생하는충돌을제거하는것. 두가지의모호한문법을통해파싱표에나타난충돌을제거하는방법을도입. 첫번째는산술식에서연산자우선순위와결합법칙을이용하여충돌을제거하는것이고, 두번째는현수 else 라고하는모호한문법이다. 먼저산술식에서연산자우선순위와결합법칙을이용하여충돌을제거하는방법을살펴보자. 충돌은이동 - 감축충돌과감축 - 감축충돌이있는데, 이동 - 감축충돌의경우감축되는생성규칙과입력기호의우선순위를비교하여생성규칙의우선순위가높으면감축을선택하고, 그렇지않으면이동을선택한다. 생성규칙의우선순위는그생성규칙내에있는터미널기호로결정할수있다. 반면에감축 - 감축충돌은감축되는생성규칙의우선순위를비교하여우선순위가높은쪽으로감축하면된다 102
6.4 모호한문법의사용과에러처리루틴 충돌을제거하는방법 이동 - 감축충돌인경우충돌을해결하는방법 감축되는생성규칙과입력기호의우선순위를비교하여결정 생성규칙의순위가높으면감축을선택, 그렇지않으면이동을선택 같은순서인경우에는결합법칙을이용 좌측결합을만족하면감축, 우측결합을만족하면이동을선택 감축 - 감축충돌인경우충돌을해결하는방법 감축되는생성규칙들의순위를비교하여어느생성규칙으로감축할것인가를결정하는데우선순위가높은것을선택 생성규칙의순위는그생성규칙내에있는터미널기호로결정가능 103
6.4 모호한문법의사용과에러처리루틴 [ 예제 6-40] 모호한문법에대한 SLR 파싱표를만들고충돌제거하기 [ 예제 6-39] 에주어진모호하지않은문법에대한 SLR 파싱표를만들고, 모호한문법에대해서도 SLR 파싱표를만들어충돌이발생하는지확인한다. 충돌이발생하면연산자우선순위와결합법칙을적용하여충돌을제거하고, 충돌을제거한후모호하지않은문법의파싱표와비교해보자. [ 풀이 ] [ 예제 6-27] 과 [ 예제 6-28] 에서모호하지않은문법으로변환된문법에대해 [ 표 6-3] 과같은파싱표를만들었으며, [ 표 6-3] 에서는충돌이발생하지않았다. 여기서는모호한문법에대해 SLR 파싱표를만들어보자. 1. 증가문법을만든다. 2. FOLLOW 를계산한다. FOLLOW(E) = {+, *, ), $} 104
6.4 모호한문법의사용과에러처리루틴 3. SLR 파싱표 105
6.4 모호한문법의사용과에러처리루틴 이문법에서는상태 I7, I8 에서이동 - 감축충돌이발생했다. 파싱표의크기를비교해보면모호하지않은문법에대한파싱표는 12 9 행렬인데비해모호한문법에대한파싱표는 10 9 행렬이다. 즉충돌만해결한다면모호한문법에대한파싱표를모호하지않은문법에대한파싱표보다작게만들수있고구문분석시간도빠르게할수있다. 상태 I 7 과 I 8 에대한파싱표다음과같다. 충돌의해결 LA(I 7, [E E + E.]) = {+, *, ), $} LA(I 8, [E E * E.]) = {+, *, ), $} 상태 id + * ( ) $ E I 7 r1,s4 r1,s5 r1 r1 I 8 r2,s4 r2,s5 r2 r2 생성규칙에있는기호와이동기호의순위를비교하여생성규칙에있는기호의순위가높으면감축하고그렇지않으면이동한다. 같은순위일경우, 좌측결합을만족하면감축하고우측결합을만족하면이동한다. 106
6.4 모호한문법의사용과에러처리루틴 107
6.4 모호한문법의사용과에러처리루틴 입력문장 id + id * id 에대해모호한문법의파싱표를가지고구문분석을해보자. 더이상진행하지못한다. 108
6.4 모호한문법의사용과에러처리루틴 마지막으로입력문장 id + id * id 에대해충돌을해결한파싱표를가지고구문분석을해보자. 109
6.4 모호한문법의사용과에러처리루틴 구문분석을해보니모호하지않은문법에대해서는 22 단계의과정을거치지만, 모호한문법에대해파싱표를만든후충돌을제거한파싱표를이용하여구문분석을하면 16 단계만에똑같은결과를얻는다. 따라서모호하지않은문법에대한파싱표보다모호한문법에대한파싱표가크기도작고구문분석시간도단축할수있다. 110
6.4 모호한문법의사용과에러처리루틴 [ 예제 6-42] 에러검출과에러처리 다음의모호한문법에대한 LR 파싱표를구성하고에러처리에대해설명해보자. E E + E E * E (E) id [ 풀이 ] 에러검출과에러처리를위해수정된 LR 파싱표는 [ 표 6-12] 와같다. 111
6.4 모호한문법의사용과에러처리루틴 112
6.4 모호한문법의사용과에러처리루틴 에러처리내용은다음과같다. e1 : 이루틴은상태 0, 2, 4, 5로부터호출된다. 이러한상태는모두 id를기대하는데 +, *, $ 가발견되었다. missing operand 를출력한다. 계속처리한다면상태 0, 2, 4, 5에서 id를읽어갈수있는상태 3이므로 id를 push 하고상태 3을 push 한다. e2 : 오른쪽괄호를발견했을때상태 0, 1, 2, 4, 5로부터호출된다. 왼쪽괄호없이오른쪽괄호를발견한경우이므로입력에서오른쪽괄호를제거하라고하거나왼쪽괄호를추가하라고한다. unbalanced right parenthesis 를출력한다. 계속처리한다면입력에서오른쪽괄호를제거한다. e3 : 이루틴은상태 1, 6으로부터호출된다. 피연산자를읽고연산자를기대하고있는데 id나오른쪽괄호가발견된경우이다. missing operator 를출력한다. 계속한다면 + 에상응하는상태 4를스택에저장한다. e4 : 이루틴은상태 6으로부터호출되고입력의끝인 $ 가발견되었다. 왼쪽괄호는나왔는데오른쪽괄호가없는경우이다. missing right parentheses 를출력한다. 계속한다면오른쪽괄호에상응하는상태 9를스택에저장한다 113
6.4 모호한문법의사용과에러처리루틴 [ 예제 6-43] 에러복구를위한구문분석하기 [ 예제 6-42] 의파싱표를이용하여입력문장 id+)$ 의구문분석을해보자. [ 풀이 ] 114