프로그래밍노리터

앞의 글에서 문법에 대해 RDP(Recursive Descent Parser)를 직접 만드는 방법을 살펴보았습니다. 그러나 문법이 아주 큰 경우 모든 넌터미널 심볼에 대해 직접 메소드를 만들고 모든 터미널 심볼을 직접 다루는 것은 결코 쉬운 일이 아닙니다. 그래서 많은 경우 토큰을 읽어들이는 일은 Lexer라는 툴을 많이 이용하고 파서는 역시 파서를 만들어주는 툴을 많이 사용합니다. 그리고 그런 파서는 LL 또는 LR 파싱 방법으로 구현되어 있습니다. 여기서는 LL 파싱 알고리듬이 어떻게 동작하는지를 설명해 보려고 합니다. 사실 이것을 몰라도 바로 파서생성기를 이용하는 것이 가능하나 RDP 방법을 익힌 다음이라면 체계적인 파싱 알고리듬으로서 LL 알고리듬을 이해하는 것이 어렵지 않습니다. 앞의 글에서 살..

이전 포스트에서 E -> T { (+|-) T }, T -> num | (E) 라는 문법의 파서를 만들어보았습니다. 여기서는 문법을 좀더 확장하고 수식 계산 과정을 보여줄 수 있는 파서를 만들어보도록 하겠습니다. (완성된 코드와 실행결과는 하단에 링크되어 있습니다.) /* * E -> T { (+|-) T } * T -> F { (*|/) F } * F -> num * | ( E ) */ 이전 포스트에서 +와 - 연산만 지원하는 문법에서 *와 /를 지원하는 문법으로 확장한 것입니다. 우선순위를 고려하기 위해 새로운 넌터미널을 도입하여 괄호()로 둘러싼 부분이 가장 우선순위가 높고 *|/가 그 다음 순위고 +|-가 가장 우선순위가 낮아서 마지막으로 처리되도록 문법을 만든 것입니다. 이렇게 되면 T() 메소..

파서는 우리가 많이 쓰면서도 정확하게 그 알고리즘을 알지 못하는 대표적인 방법 중 하나입니다. 컴파일러의 한 분야이고 알아야 하는 용어가 많아서 쉽게 이해하기 어려운 분야입니다. 여기서는 완전 처음부터 자바만 가지고 파서를 구현하는 방법을 알아보려고 합니다. 물론 문맥무관문법(CFG: Context-Free Grammar)나 토큰, 어휘분석기의 개념 등을 알고 있어야 하지만 대략의 개념만 이해한다면 파서의 알고리듬과 구현 코드까지도 들여다 볼 수 있습니다. 함께 출발해 봅시다. 먼저 문법에 대한 간단한 설명입니다. 문맥무관문법은 생성규칙이라는 걸 가지고 왼쪽에 넌터미널 심볼이 나오고 오른쪽에 여러 개의 심볼이 연속해서 나타납니다. 그래서 시작심볼에서 시작해서 차례로 생성규칙을 적용해 가다보면 입력을 처리..

이번에는 좀 다른 형태의 예제를 살펴보자. 입력파일에서 "Harry"라는 부분을 모두 찾아 그 나온 회수를 괄호로 보여주는 어휘분석기를 만들려고 한다. 이것은 일종의 입력에 대한 변환이라고 볼 수 있다. 기본적으로 입력파일과 출력파일은 실행명령에서의 파이프라인 리디렉션으로 처리하려고 한다. 그러므로 표준입력과 표준출력으로 입출력하면 된다. (파워쉘에서는 < 리디렉션이 허용되지 않음) %option noyywrap %{ #include int count=0; %} %% Harry{ ++count; printf("%s(%d)", yytext, count); } %% 이 코드는 놀라울 정도로 간단하다. 회수 변수의 증가와 harry 문자열 출력이 전부다. 여기서 규칙부에 .에 대한 규칙은 기술하지 않았음을 주..

앞의 글에서 렉스의 설치와 실행 방법을 살펴보았다. 이번에는 좀더 본격적인 lex 사용 사례를 살펴보겠다. %option noyywrap %{ int lineno = 0; %} digit[0-9] number{digit}+ float {number}(\.{number})? newline \n %% {number}{int n = atoi(yytext); printf("[%2d] %5d\n", lineno+1, n);} {float}{float n = atof(yytext); printf("[%2d] %f\n", lineno+1, n);} {newline}{lineno++;} . ; %% int main() { yylex(); return 0; } 이 예제에서는 룰 부분(%%와 %% 사이)의 앞에 들어가는 ..

1. lex란 무엇인가? 어휘분석기 코드를 생성하는 도구인 렉스는 어휘(토큰)를 정의해 주면 그것을 인식하여 하나씩 돌려주는 어휘분석기 C 함수 코드를 생성해 준다. 다음 그림과 같이 렉스의 입력 파일(확장자 .l)을 작성하여 렉스를 실행하면 어휘분석기 C 코드가 생성된다. 이것을 컴파일하면 어휘분석기 실행파일 exe가 얻어진다. 어휘분석기는 여러 가지 일을 할 수 있지만 기본적으로는 토큰을 차례로 한개씩 인식해 주는 역할을 한다. 다음 실행 화면은 숫자와 문자열 토큰을 인식하는 실행프로그램의 예를 보여준다. 2. 렉스의 설치 http://techapple.net/2014/07/flex-windows-lex-and-yaccflex-and-bison-installer-for-windows-xp788-1/ ..

정규표현식을 이용해서 가장 많이 접하는 예가 아이디와 패스워드가 제약 조건을 검사하는 것입니다. 여기서는 여러 가지 제약조건을 검사하는 정규표현식의 예를 살펴보겠습니다. 우리는 입력에 대해 검사해야 할 조건이 여러개라면 굳이 하나의 정규표현식 안에 모든 조건을 다 넣어야 하는 것은 아닙니다. 입력 문장을 몇 가지 정규표현식에 대해 차례로 검사하는 것으로 충분합니다. 그를 위해서는 앞에서 살펴본 RegexTestHarnessEjlee 프로그램의 (2)번 메뉴를 이용하면 됩니다. 입력을 먼저 넣고 여러 가지 정규표현식으로 그 입력을 검사해 볼 수 있습니다. 먼저 길이를 검사하는 조건을 생각해 봅시다. 아이디가 6글자 이상이어야 한다 라는 조건을 나타낼 수 있겠지요? 보통 아이디는 영문자와 숫자를 섞어서 쓸 ..

정규표현식에서 패턴을 입력문장에 매치한다는 것은 입력문장에서 패턴 전체의 규칙에 만족되는 부분을 찾는 것입니다. 매치되는지 여부를 참 거짓으로 돌려주기도 하고 앞의 글에서 살펴본 도구에서처럼 매치되는 부분 문자열을 모두 찾는 것도 가능합니다. 여기까지는 패턴에 매치되는 부분 전체를 다루게 됩니다. 그런데 캡처그룹은 거기서 한걸음 더 나아가서 매치된 부분에 속하는 일부를 다시 분리하여 돌려주는 방법입니다. 예를 들어 이메일에 매치된 문자열 부분을 찾았다면 거기서 @ 앞에 있는 아이디 부분만 따로 떼내고 싶을 수 있을 것입니다. 또는 끝에 도메인이 .kr인 것에서 앞부분만 구분해 내고 싶을 수도 있지요. 또는 패턴에 매치된 부분에서 일부를 바꿔치기 할 수도 있습니다. 예를 들다면 kyonggi.ac.kr로 ..

이번에는 패턴을 입력의 어느 부분에 대해 매치할 것인가를 지정하는 방법을 알아봅시다. 정규표현식에서는 위치의 개념이 시작, 끝, 단어 경계 등 여러 가지가 있습니다. 물론 각각이 아닌 경우도 조건으로 표현할 수 있겠지요. 경계를 지정하는 기호들은 다음과 같습니다. 경계 요소 설명 ^ 한 줄의 시작부 $ 한 줄의 끝 \b 단어 경계 \B 단어 경계가 아닌 곳 \A 입력의 시작부 \G 직전 매치의 끝 \Z 마지막 종료문자가 아닌 입력의 끝 \z 입력의 끝 이렇게 다양한 경계 매처를 어떻게 이용할 수 있을까요? 한 가지씩 살펴보겠습니다. (1) 입력 시작부에서만 매치하기 패턴 앞에다 ^을 넣으면 입력의 시작 부분에서 한번만 매치하라는 뜻이 됩니다. 입력 중간에 매치되는 부분이 있어도 무시하게 됩니다. (2) ..

(3) 한정자 (quantifier) quantifier의 의미는 수량 한정자입니다. 정규표현식은 반복과 선택(합집합)을 나타낼 수 있는 언어이므로 반복이 매우 중요한 기능입니다. 여기서 한정자는 반복을 몇번 할 것인가, 또는 얼마나 허용할 것인가에 관한 규칙을 표현하게 해 줍니다. 우리가 흔히 알고 있듯이 *는 0번 이상, +는 한번 이상 무한번까지 제한없는 반복을 의미합니다. 프로그래밍 언어의 정규표현식은 그냥 반복을 나타내는 *나 + 이외에도 몇번 반복할 수 있는지 범위를 정확히 표현할 수 있는 기능을 제공합니다. X? X가 한번 또는 0번 X* X가 0번 이상 X+ X가 한번 이상 X{n} X가 정확히 n번 반복, n은 정수 X{n,} X가 n번 이상 반복 X{n,m} X가 n번 이상, m번 이하..