갱스터의 블로그

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 심벌 생성 규칙 번호 리스트 문법의 생성 규칙을 통해 유도하는 과정에서 적용되어 온 일련의..

모호성(Ambiguity) 모호성이란 문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도트리를 갖는 경우 문법 G는 모호하다고 한다. 아래 예시는 입력으로 a + a * a가 들어 온 경우이다. 위의 두 개의 예시에서 모두 두 개 이상의 유도트리가 나왔으므로, 해당 문법들은 모호하다고 할 수 있다. 그렇다면 이러한 모호성은 어떻게 해결할 수 있을까? 모호성의 해결 같은 뜻을 가지는, 모호하지 않은 문법을 만들어보자. 이때, 같은 뜻을 가지는 여러 방법의 문법이 존재하는데, S -> a 의 문법을 S -> A, A -> a로 바꿀 수 있다. 즉, 모호성을 해결하는 방법은 같은 언어를 생성하는 다른 문법을 사용하는 것이다. 모호성은 크게 두 가지 방법으로 해결할 수 있다. 1. 연산자 우선 순위 도입 ..

앞서 코드가 어떻게 컴파일 되는지에 대해 설명한 적이 있는데, 다시 한 번 복기하겠다. 컴파일러는 소스코드를 어휘분석기를 거치고, 구문분석기를 거친 후, 의미분석기 총 세 단계에 걸쳐 추상구문트리(AST)를 만들어 낸다. 이번 시간에는 구문 분석에 대해 알아보도록 하겠다. 구문 분석(Syntax Analysis) 구문 분석은 어휘 분석을 통해 나온 토큰에 대해 각 토큰들을 조합하여 해당 토큰들의 역할을 확인한다. 위 그림은 어휘분석기를 통해 파싱된 토큰들을 구문분석기에 넣어 파스트리를 만드는 모습이다. 각 토큰들이 조합되어 어떤 의미를 가질 수 있는지를 보여준다. 코드말고, 우리의 언어로 되어 있는 예시를 보자. 문법이 맞는지 확인하고, 각 단어의 역할을 확인한다. 구문 분석할 때, 두 가지의 질문을 던..