갱스터의 블로그

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..

구글 플레이스토어에 어플리케이션을 출시하기 위해서는 구글 개발자 계정을 만들어야 한다. 개발자 계정을 만드는 방법은 다른 사람들이 더 자세히 설명을 해뒀을 것이니 다른 블로그를 참고하도록 하자. cmd+shift+f를 눌러서 com.example.[프로젝트명]을 검색하여 example 부분을 회사/기업 이름으로 바꾸던지, 원하는 이름으로 바꾸어 준다. example로 되어 있다면 구글 플레이 스토어에서 받아 주지 않는다고 한다. 그 다음으로 안드로이드 스튜디오에서 프로젝트의 android 폴더를 연다. (인텔리제이로 개발하여 인텔리제이로 하려고 했는데 안 되었다...) android 폴더를 안드로이드 스튜디오로 열면 사진과 같이 귀여운 안드로보이가 보일 것이다. 이때, Build탭의 Generate Si..

인터넷 주소 인터넷 주소는 인터넷에 연결된 장치의 주소이다. 장치의 주소는 두 가지로 나눌 수 있는데, ip 주소와 mac 주소가 그것이다. ip address ip주소는 인터넷에 연결되어 있는 개체(컴퓨터 또는 네트워크 카드)의 식별자(주소)이다. 즉, 논리적인 주소로 네트워크에 따라 변동된다는 특징이 있으며, ISP/공유기에서 할당한다. mac address mac 주소는 디바이스 고유의 식별자로 hardware에 존재하는 physical 주소이다. 즉, 물리적인 주소로 네트워크 카드를 만드는 제조사에서 일정한 규칙에 따라 부여한다. 물리적 주소와 논리적 주솔흘 쉽게 이해하기 위해 예를 들어 보자면, 우리가 택배를 보낼 때 사용하는 도로명주소가 논리적 주소의 예이고, 위치를 지구상의 위도와 경도로 표..