갱스터의 블로그

LALR Parsing LR(1) 파싱의 문제점 LR(1) 파싱은 정교하기 때문에 상태의 개수가 어마어마하게 많다. Pascal 언어를 통해 만들면 SLR은 수백 개, LR(1)은 수천 개의 상태가 나온다. 하지만 이렇게 많은 개수의 상태는 메모리에 과부화를 준다. 따라서 우리는 이러한 LR(1)의 상태 개수를 줄이고자 LALR 파싱을 시작하였다. LALR Parsing LR에서 두 상태의 core가 동일하면 하나의 상태로 묶어준다. 위 사진에서 두 개의 상태 중 일부가 동일한 것을 볼 수 있다. 동일한 부분을 LALR 파서에서는 묶어준다. 이러한 LALR 파싱은 1. SLR보다 많이 정교하다. LR(1)보다 이론적으로 less powerful하지만, 실제 처리할 수 있는 의미 있는 문법의 종류는 거의 ..

Shift와 Reduce의 의미 입력으로 '((a),b)'이 들어 온 경우 아래와 같이 파싱할 수 있다. SLR Parser 앞선 LR(0)의 파싱 테이블은 conflict가 발생한다. 왜냐하면 reduce 시에 모든 셀에 대해 reduce를 채우기 때문이다. 따라서 이러한 LR(0)의 충돌을 줄이기 위해 SLR(Simple LR) Parser가 등장했다. SLR 파싱 테이블은 약간의 노력을 더해 LR(0)의 conflict를 줄이고 정교하게 만들어 주는 것으로 I1이 [X -> β.]를 포함할 때, M[I1, a] = 'reduce X -> β'이다 (단, a ∈ FOLLOW(X)) 즉, 파싱 테이블에서 X의 팔로우에 속하는 터미널에 대해서만 reduce를 진행한다는 의미이다. 나머지는 LR(0)과 동..

LR Parsing: 파서 상태 파서는 파싱 테이블을 통해 현재 상태, 입력 심벌을 보고 shift 할 지, reduce 할 지 결정하고(action), 파서의 상태로 변경한다.(goto) 그렇다면 '상태'란 무엇일까? LR(0) 아이템 LR(0)은 lookahead 없이 파싱하는 shift-reduce 형태이다. LR(0)의 파싱 테이블은 파서 상태를 정하고, 각 파서 상태들의 상태 전이도를 테이블에 담아내는 형태로 만들어진다. 이때, LR(0)item이란 rhs에 점('.') 심벌을 가진 생성규칙이라고 할 수 있다. 생성 규칙의 형태가 A -> XYZ일 때, [A -> .XYZ], [A -> X.YZ], [A -> XY.Z], [A -> XYZ.] 모두 LR(0) item이라 할 수 있다. 또, 생성..

YACC YACC는 LALR 파서 생성기로, Yet Another Compiler Compiler의 약자이다. Lex와 함께 AT&T Bell Lab.에서 70년대 유닉스 운영체제용으로 개발하였으며 유닉스 표준으로 채택되었는데, 요즘은 GNU Flex(Lex)/Bison(YACC)을 더 많이 사용한다. 위와 같은 흐름으로 진행된다. foo.y 파일이 들어오면 yacc나 bison을 통해 y.tab.c파일로 만들어지고, y.tab.c파일은 gcc를 통해 컴파일된다. 이때 .y 파일의 형태는 아래와 같은데, 해당 구조는 lex/flex와 동일하다. LR Conflict 위와 같은 생성 규칙이 있다. 스택에 $ E * E 가 있고, 입력 버퍼에 + ... $가 있을 때, reduce를 해야 할 것인지, shi..

위 사진은 앞 포스트에서 보여준 reduce 과정이다. 이 과정을 stack을 통해 시행해보자. 초기 상태는 스택에 $, 입력 버퍼에는 입력 스트링과 $를 모두 넣는다. accept 상태는 스택의 top에 시작 심벌이 있고 입력은 모두 읽은 상태이다. 스택의 top 모습을 보고 reduce와 shift를 한다. 이때 reduce 할 때는 입력 버퍼에 영향이 없다. 이때, 우리는 shift와 reduce를 어떻게 판단할 수 있을까? 스택에 β가 있고 입력 글자가 b일 때, β = αγ이고, X -> γ가 있다면, 스택을 αX로 만들 것인지, βb로 만들 것인지에 대한 고민에 빠진다. 또, 여러 가지 reduce가 있는 경우 스택 중 어디까지 handle로 봐야 하는 것일까.즉, 스택이 β = αγ일떄, X..

Top-Down vs. Bottom-Up 아래는 입력이 '(a + a)'가 들어온 경우 Top-Down과 Bottom-Up 방식으로 파싱한 과정이다. 이때, Bottom-Up 방식이 조금 더 자연스럽다. 이때, Top-Down에 비해 Bottom-Up 방식이 더 강력한데, 생성 규칙을 선택할 때, Top-Down에 비해 더 많은 토큰을 볼 수 있기 때문이다. 따라서 Top-Down으로 파싱 시 불가능했던 left-recursion을 파싱할 수 있다. 위 그림에서 볼 수 있듯이 Top-Down 방식은 파싱 시 root를 찾아야 하지만, Bottom-Up은 root를 찾을 필요 없이, 아래에서만 파싱할 수 있으므로 표현력이 더 강하다고 볼 수 있다. Bottom-Up Parsing Bottom-Up = 우파..

지금까지 알아보았던 LL(1)파싱 방법을 통해 파서를 만들 수 있다. LL 파서는 두 가지 방법으로 만들 수 있다. 1. Recursive descent parser 2. Predictive parser 이제 각 방법의 특징과 어떻게 파서를 만들 수 있는지 설명하겠다. Recursive descent parser recursion을 이용하고, 각 non-terminal마다 하나의 procedure를 둔다. 직관적이고, 쉽다는 장점이 있지만, 생성 규칙이 바뀌면 구문 분석기를 고쳐야 한다는 점에서 융통성이 떨어진다는 단점이 있다. 모든 terminal 심볼 a에 대한 파서 코드 모든 non-terminal 심볼 A에 대한 파서 코드 아래는 위 로직을 코드로 구현한 예시이다. /* S -> aAb * A -..

FIRST의 한계 우리는 이전 포스트에서 FIRST에 대해 학습하였다. 하지만 이런 FIRST에도 한계가 존재한다. A -> XXX와 같은 생성 규칙이 있을 때, non-terminal A가 nullale한 경우 문제가 발생하게 된다. 왜냐하면 FIRST만 가지고 생성 규칙을 결정적으로 선택할 수 없기 때문이다. S -> Ab, S -> c, A -> ε의 경우 입력 문자열로 'b'가 들어온 경우 S -> Ab, 'c'가 들어온 경우 S -> c로 유도한다.FIRST(S) = {b, c}이기 때문이다. 하지만, 문법이 S -> Ab, S -> c, A -> a, A -> ε인 경우FIRST(A) = {a, ε}인데, FIRST(S) = FIRST(A) ⊕ FIRST(b)이므로 FIRST(S) = {a, ..

LL parsing(LL 파싱) Top-down으로 구문 분석하기 Top-down 방법으로 구문 분석하는 것은 직관적이고, 좌측 유도 과정과 비슷하다는 특징이 있다. Top-down 방법으로 구문을 분석하는 순서는 아래와 같다. 1. 시작 심벌의 첫 번째 생성 규칙으로 유도하여 문자열을 생성한다. 2. 유도 과정에서 생성된 문자열과 입력 문자열을 차례로 비교한다. 이때, 유도된 문자열과 입력된 문자열이 같으면 계속 비교해 나가고, 유도 과정에서 생성된 문자열에 non-terminal이 나오면, 이 non-terminal의 첫 번째 생성 규칙으로 다시 유도하여 새 문자열을 생성한 후 비교한다. 3. 생성된 문자열과 입력 문자열이 다르다면 backtracking를 통해 원상 복구한다. Backtracking..

구문 분석 (= parse) 구문 분석 구문 분석이란 주어진 문자열이 정의된 문법에 의해 생성될 수 있는지의 여부(적합성)를 결정하는 과정이다. 따라서, 문법에 대해 유도가 되는지를 확인하면 되는데, 올바를 문장에 대해서는 문장 구조를, 틀린 문장에 대해서는 오류 메세지를 나타낸다. 구문 분석기(= parser) 파스 트리(parse tree) 파스트리는 문장 구조를 나타내는 트리로, 문법을 나타내는 생성 규칙을 적용한 유도 트리와 같은 모양의 트리이다. 루트 노드: 정의된 문법의 시작 심벌 중간 노드: 각 생성 규칙의 좌측 nonterminal 심벌 단말 노드(잎 노드): 주어진 스트링을 생성하는 terminal 심벌 생성 규칙 번호 리스트 문법의 생성 규칙을 통해 유도하는 과정에서 적용되어 온 일련의..