갱스터의 블로그

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

이번에는 가장 전통적으로 유명한 도구를 이용하여 어휘 분석기를 직접 만들어 보자. 오래 되었지만, 다른 도구들도 이 도구를 기반하여 만들어졌다. 어휘 분석기 도구 Lex 전통적인 방법으로 C 언어가 기반이다. 구문 분석기인 yacc과 밀접한 관련이 있으며 발전된 버전인 flex를 더 많이 사용한다. ANTLR java 기반으로, 구문 분석 시 다시 언급하겠다. 기타 도구로는 JavaCC, SableCC가 있다. Lex(렉스) 렉스는 1975년 레스크에 의해 발표된 어휘분석기 생성기이다. 이때 주의할 점은 어휘 분석기가 아니라 어휘 분석기 "생성기"라는 것이다. 사용자가 정의한 프로그램의 정규표현과 실행코드를 입력받아 C언어로 쓰여진 프로그램(어휘분석기)을 출력한다. 어휘 분석기의 생성 및 동작 어휘 분석..

토큰을 어떻게 기술할까? 프로그래밍 언어 제작자는 토큰에 대해 하나하나 기술해야 할 필요가 있다. 이때 주로 사용하는 방법이 정규 표현식(regular expression)이다. 정규표현식이란 특정한 규칙을 가진 문자열의 집합을 표현하는 데에 사용하는 형식 언어이다. 표현 방식에 대한 설명은 사진으로 대체하겠다. 위는 표현, 아래는 예시이다. 마지막 예시는 2진수 집합? 이라고 쓰여있는데, 해당 표현 방식이 2진수의 모든 집합을 나타낸 것일까? 정답은 아니요이다. 왜냐하면, 2진수에는 0을 포함해야 하는데, 해당 예시에서는 무조건 1부터 시작해야 하기 때문이다. 또 다른 표현식과 예시를 보자. 위의 표현식에서 표기할 수 있는 기호와 괄호 안에 들어간 지의 여부를 파악해서 헷갈리지 않도록 조심하자. 토큰을..

컴파일 과정 컴파일러는 소스코드를 입력으로 받으면 전처리기를 통해 소스코드를 전처리(#include, #defines, #ifdef 등을 처리)하고 해당 결과물로 어휘, 구문, 의미 분석 과정을 거쳐 추상구문트리(AST)를 만든다. 이 과정에서 어휘 분석이라는 과정을 거치는데, 어휘 분석이 무엇인지 알아보자. 어휘 분석(Lexical Analysis) 어휘 분석이란 원시 프로그램(소스 코드)을 긴 문자열로 보고 차례대로 문자를 검사하여 의미 있는 최소 단위들로 변환하는 것이다. space와 같은 공백을 제거하여 코드의 크기도 줄일 수 있다. 이때, 의미 있는 최소 단위를 토근(token)이라고 하는데 이 토큰은 문법적으로 의미있는 최소 단위이다. 토큰의 종류는 아래와 같다. 식별자: x, y와 같은 변수..

컴파일러란? 우리도 한국어, 영어 등의 언어가 존재하지만, 컴퓨터에도 마찬가지로 언어가 존재한다. 컴퓨터는 2진수를 통해 통신하는데, 이를 사람이 보고 해석하기란 불가능에 가깝다. 따라서 사람들은 어셈블리어를 만들어 컴퓨터와의 소통을 시작하였다. 어셈블리어 사람들이 직접 2진수를 쓰지 않고 기호로 표기하였다. 예를 들면 ADD(덧셈) -> 0010, SUB(뺄셈) -> 0101 등과 같이 말이다. 이렇게 기호로 표기된 언어(어셈블리어)를 어셈블러에 넣으면 컴퓨터 언어로 전환해주는데, 이때 어셈블러란 번역을 전담하는 SW이다. 그러나, 이러한 어셈블러는 CPU가 바뀌면 새롭게 만들어야 했다. 고급 언어 CPU 별 다른 어셈블러를 만들어야 한다는 사실을 불편하게 여겨 우리는 고급 언어를 탄생시켰다. 0과 1..