갱스터의 블로그

모호성(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..