분류 전체보기

문법(Grammar) 이전 형식언어 포스팅에서는 언어의 정의에 대해 알아보았다. 언어는 스트링을 원소로 갖는 집합으로 정의될 수 있는데, 그렇다면 이렇게 정의된 언어를 어떻게 표현할 수 있을까? 유한 언어는 그 집합에 포함된 스트링을 모두 열거하여 표현할 수 있으나, 무한 언어는 그 언어의 유한 표현을 찾아야 한다. 이전 포스팅에서도 짧게 알아보았듯, 1. 집합을 이용한 조건 제시법, 2. 문법, 3. 인식기 이용과 같은 방법을 이용해 무한 언어의 유한 표현이 가능하다. 언어를 정의하기 위한 문법은 심벌의 분리된 두 집합인 VN, VT로 표시하는 두 심벌의 집합을 사용한다. 여기서 VN은 nonterminal 심벌의 집합, VT는 terminal 심벌의 집합이다. nonterminal 심벌은 문법에서..

언어 컴파일러 개론 포스팅에서 컴파일러의 전단부를 위해서 언어(Language)를 잘 정의해야 하는 것을 알았다. 이렇게 잘 정의된 언어를 형식 언어(Formal Language)라 하며, 보통 문장의 집합으로 정의된다. 잘 정의된 언어는 문장의 집합으로 정의되며, 알파벳(Alphabet)은 문장을 이루는 기본적인 심벌(Symbol)로, 알파벳 T는 심벌들의 유한 집합이다. 언어의 정의알파벳과 스트링 알파벳 T에 대한 스트링(String)은 알파벳 T에 속하는 심벌이나 T에 속하는 하나 이상의 심벌들을 나열한 것이다. 쉽게 말해 스트링은 알파벳의 유한 집합이다. 스트링의 길이는 스트링을 구성하는 심벌들의 개수이며, 어떤 스트링 w의 길이는 |w|로 표기한다. 예시 몇 가지를 살펴보자. T1 = {ㄱ, ..

문제https://www.acmicpc.net/problem/1049 풀이 맨 첫 줄에 구매해야 하는 기타줄의 수와 브랜드 수가 입력된다. 이후 6줄 묶음의 가격과 1줄의 개별 가격이 입력으로 주어지게 된다. 그리디 알고리즘을 이용해야 하는 문제로, 이 문제를 처음 봤을때는 무조건 같은 브랜드에서만 모든 줄을 구매해야 하는 줄 알고 건드리지 못하고 있었는데, 지금와서 잘 읽어보니 두 브랜드에서 섞어서 사도 상관이 없는 문제였다. 문제 해결의 아이디어는 다음과 같다. 1) 입력되는 여러 브랜드 중, 가장 싼 6줄 묶음 가격과 가장 싼 개별 1줄의 가격을 구한다.2) 1)에서 구한 가장 싼 6줄 묶음 / 개별 1줄 가격에 그리디 알고리즘을 적용해 n개의 기타 줄을 구매한다. 그리 어렵지 않게 구현할 수 ..

문제https://www.acmicpc.net/problem/1343 풀이 알고리즘 분류에 구현, 그리디 알고리즘, 문자열 태그가 달려있는 문제이다. 문제는 입력받은 문자열의 X로 구성된 부분을 AAAA 혹은 BB로 채울 수 있으면 문자열의 X 부분을 AAAA 혹은 BB로 채운 결과를 출력하거나, AAAA와 BB로 채울 수 없다면 결과로 -1을 출력하도록 요구한다. 문제를 처음 봤을 때에는 입력 문자열의 X로 구성된 부분의 길이를 리스트에다 저장하고 "."을 만나면 앞에서 저장한 X 문자열의 길이만큼 그리디 알고리즘을 적용해 AAAA 혹은 BB로 채우면 되지 않을까? 하고 생각했다. 그런데 이렇게 하니 "."이 연속해서 나왔을 때에 제대로 작동하지 않아서 접근 방식을 조금 바꿨다. 이 문제에 그리디..

문제https://www.acmicpc.net/problem/14496 풀이 주어진 문자를 얼마나 적은 횟수로 변환시켜서 원하는 문자로 변환할 수 있는지 최소 변환 횟수를 구하는 문제이다. 문제 이해가 조금 난해할 뿐이지 실제로는 굉장히 간단한 BFS 문제이다. 입력은 모두 숫자로 주어지므로 단순 정수 기본 아이디어는 다음과 같다. 1. 변환 횟수를 저장할 int 타입의 dis 배열, 방문 여부를 저장할 boolean 타입의 visit 배열 선언2. 연결 리스트 형태로 그래프를 저장하기 위해 list 선언3. BFS는 a에서 시작 (문자 변환을 a부터 시작하기 때문)4. BFS 종료 후, b를 방문하였다면 dis[b]를 출력. 방문하지 않았다면 -1을 출력 추가로, 입력되는 a와 b가 같다면 변환할 필요..

개요 프로그래밍 언어론 포스팅에 이어 형식언어 내용을 포스팅해보려 한다. 사용한 교재가 이름부터 '컴파일러 입문'이지만 교재의 중반부는 형식언어론과 관련된 부분이고, 중후반부는 LL, LR 구문 분석 등과 같은 컴파일러와 관련된 부분이다. 추가로, 프로그래밍 언어론에서 사용한 용어들이 꽤나 많이 등장하여 프로그래밍 언어론과 연결하여 공부하면 꽤 좋은 내용이라고 생각한다. 번역기와 컴파일러 번역기(translator)란 한 프로그래밍 언어로 작성된 프로그램을 입력으로 받아 이와 동등한 의미를 갖는 다른 프로그래밍 언어로 된 프로그램을 출력하는 시스템 프로그램을 뜻한다. 여기서 입력되는 프로그램을 소스 프로그램이라 하며 이 프로그램을 기술한 언어를 소스 언어(source language)라 한다. 그리고 ..

상속 프로그래밍 언어론에 대한 마지막 포스팅이다. 이 포스팅에서는 이전 포스팅에서 알아본 객체지향 언어의 핵심 기능인 캡슐화, 상속, 다형성 중 상속 기능에 대해 알아보자. 이 블로그에 있는 디자인 패턴 포스팅을 몇 개 살펴봤다면 상속 기능에 대해서는 다들 알 것이다. 상속 기능을 이용하면 새로운 클래스를 정의할 때 기존 클래스를 상속받아 새로운 클래스를 정의할 수 있으며, 여기서 기존 클래스는 부모 클래스(parent class)이며 새로운 클래스는 자식 클래스(child class)이다. 이때, 부모 클래스는 슈퍼 클래스(super class), 자식 클래스는 서브 클래스(sub class)라고도 부른다. 상속을 이용해 자식 클래스를 새로 정의하면 자식 클래스는 부모 클래스의 멤버 변수, 메소드를 상..

문제https://www.acmicpc.net/problem/25418 풀이 문제를 간단히 요약하면 입력받은 정수 값 A에 두 가지 연산을 적용해 정수 K로 만드는 것이다. 연산 1은 정수 A에 1을 더하기, 연산 2는 정수 A를 2로 곱하기이다. 처음에는 문제 해결을 위한 아이디어를 다음과 같이 잡았다. 먼저 방문 여부를 체크할 visit 배열과 해당 인덱스까지 몇 번만에 도달할 수 있는지를 저장할 arr를 선언한다. 이후 bfs 메소드를 만들어 인자로 정수 n을 받아, arr[n * 2]가 방문하지 않은 상태라면 arr[n] + 1의 값을 저장한다. 그리고 n * 2에 bfs를 다시 걸어 n * 2를 기준으로 bfs를 또 실행한다. 마찬가지로 arr[n+1]이 방문하지 않은 상태라면 arr[n] + ..