갱스터의 블로그

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) 구문 분석은 어휘 분석을 통해 나온 토큰에 대해 각 토큰들을 조합하여 해당 토큰들의 역할을 확인한다. 위 그림은 어휘분석기를 통해 파싱된 토큰들을 구문분석기에 넣어 파스트리를 만드는 모습이다. 각 토큰들이 조합되어 어떤 의미를 가질 수 있는지를 보여준다. 코드말고, 우리의 언어로 되어 있는 예시를 보자. 문법이 맞는지 확인하고, 각 단어의 역할을 확인한다. 구문 분석할 때, 두 가지의 질문을 던..