관리 메뉴

HAMA 블로그

Scala 언어를 이용한 미니언어 만들기 본문

인터프리터

Scala 언어를 이용한 미니언어 만들기

[하마] 이승현 (wowlsh93@gmail.com) 2015. 6. 6. 14:05

미니언어를 만들기위한 상황으로는 

"로보트를 만들고 해당 로보트에게  "go 3 left 4"   라는 명령어를 주면 저 명령을 파싱해서 실행해야하는 순간"

"문서를 분석하기위해   "(love & like ) & baby  " 문서에 저런 문자가 있으면 true 를 뱉어내는 , 감성분석할때 필요" 

"소켓통신할때 패킷으로 명령집합을 보내고, 받아서 해석해서 실행" 

" SQL 언어의 where 절 분석" 

등등   자바나 C++같은  언어만큼 복잡한 기능이 필요없지만  많은 경우  필요할때가 있다..

미니언어를 만들기위한 방법으로는 여러가지 방법이 있지만

이 글에서는 스칼라언어의 컴비네터 파싱에 대해 간단히 알아본다. 

( 언어 만드는것에 대한 깊이있는 내용은 나도 잘 모른다. 파싱만해도 굉장히 많은 알고리즘이 있다.

컴비네이터 파싱에 대해 알아보기전에 몇가지 알아보자.


형식문법 (Formal Grammar) 

컴퓨터 프로그램에게 완벽히 의미를 전달하기 위해서는 같은 표현이 서로 다른 의미로 해석되는 경우가 없어야 할것이다. 또한 표현하고자 원하는것은 모두 표현이 가능해야 하며 표현에 사용되는 기본 단어들도 명확하고 유한하게 정의되어야 할 것이다. 이같은 조건들을 만족시키기 위해서는 우리가 일단적으로 사용하는 자연어와는 달리 철저히 정형화된 언어가 필요한데 이런 특성을 가진 언어를 우리는 형식언어라고 부른다. 형식언어는 모든 표현들을 정형화 시키기 위해 특정한 문법에 기초하게 되는데 이를 우리는 형식 문법이라고 한다.

문맥 자유 문법(Context-free grammar, CFG) :http://ko.wikipedia.org/wiki/%EB%AC%B8%EB%A7%A5_%EC%9E%90%EC%9C%A0_%EB%AC%B8%EB%B2%95

EBNF ( http://talkingaboutme.tistory.com/513 , http://ko.wikipedia.org/wiki/%EB%B0%B0%EC%BB%A4%EC%8A%A4-%EB%82%98%EC%9A%B0%EB%A5%B4_%ED%91%9C%EA%B8%B0%EB%B2%95 )

http://www.devpia.com/MAEUL/Contents/Detail.aspx?BoardID=17&MAEULNo=8&no=53447&ref=53426

BNF및 EBNF는 문맥자유문법(Context free grammar)를 표기하기 위한 방법중 하나 입니다. 

여기서문맥자유문법(Context free grammar)은 주로 한 언어를 설계할때 그 언어의 구문구조(syntactic structure)에 대한 명세를 말합니다. 이는 주로 프로그래밍 언어론 및 컴파일러론에서 다루는 문제고 아마 질문하신 분이 아시고자 하는것은 통신에서 EBNF로 기술된 grammar를 어떻게 처리해야 하는가에 대한 질문이 아닐까 하네요. 일단 BNF및 EBNF에 대한 자세한 설명은 컴파일러 이론 책을 보시면 잘 설명되어 있습니다. 일반적으로 전산과에서 많이 쓰는 교재인 ‘Compilers/principles, techniques, and tools’(A.V. Aho, et. al)-공룡책이라고 많이 하는거 같더군요-나 제가 본 컴파일러 제작/원리와 실제(Kenneth C. Louden)을 보시면 좋은 설명을 보실 수 있을 겁니다. 통신에서의 EBNF의 응용은 ASN.1을 들 수 있습니다. 이는 추상적인 통신 프로토콜 명세라고 보시면 될 거 같습니다. 
X시리즈 프로토콜(X.400, X.500, X.200등)이 ASN.1으로 기술되어 있습니다. 
이러한 명세를 읽어들여 소스코드를 생성해 주는 ASN.1컴파일러(상용/GNU)들도 많이 있습니다. 어떤 ASN.1컴파일러는 파스트리 생성뿐 아니라 실제 오브젝트를 형성하게 도와 주는 클래스 까지 생성해 주는것도 있더군요. ASN.1에 대한 정보는 
http://asn1.elibel.tm.fr/en/introduction/index.htm 를 출발점으로 하여 찾아보시면 될거 같습니다. 

옛날에는 YACC란 툴을 써서 BNF(사실은 YACC의 입력형식)로 작성된 문법으로부터 C코드를 많이 생성했던거 같습니다. C#을 주요 타겟으로 한 Gold Parser라는 무료 툴 ( http://www.devincook.com/GOLDParser/ )을 이용하시면 좀 더 쉽게 BNF로 작성된 문법을 읽어 들여서 원하시는 작업을 가능케 하는 프로그램을 작성 하실 수 있습니다. CodeProject에 보시면 이 GOLD parser를 이용해서 간단한 프로그램 언어를 구현한 프로젝트 예제가 있습니다( http://www.codeproject.com/csharp/compiler.asp ). 이 예제에서는 간단한 언어 (Sharp)를 정의 하고 이 언어로 작성된 소스크도를 읽어들여 CLR에서 실제 동작하는 실행파일을 생성하는 것까지의 전 과정을 보실 수 있습니다. 


EBNF 예) 

RegularExp ::= LiteralExp | AndExp | OrExp | '(' RegularExp ')'

AndExp ::= RegularExp '&' RegularExp

OpExp ::= RegularExp '&' RegularExp

LiteralExp ::= 'A' | 'a' .................. { 'A',| 'a' |  ....}*

위와 같은 문법에 따라 문서를 분석하기위해서는 2가지 단계가 필요하다.

첫째.   "(love & like ) & baby  "  이런 문자열패턴을 분석하기위한 Parser 클래스 

둘째,    실제 문서를 적용하여 분석/체크 하는 클래스.

파서클래스를 만들기위해서는 LL 파싱이나 SLR,CLR,LALR 등 다양한 파싱 알고리즘을 적용해야하며, 도출된 구문트리를 또 분석클래스로 순회시키는것 또한 일이다. 

따라서 좀 더 간단하게 하려면  위의 두개의 클래스의 일을 함께 할수있는것을 만들어야하는데 구문트리 자체를 구성할수있는 클래스 구조를 만들고 해당 클래스로 만들어진 인스턴스에서 실행까지 가능하게 만드는 패턴이 인터프리터 패턴이다.  (http://brad2014.tistory.com/199

인터프리터 패턴와 별개로 어떤 문장을 구문트리로 만들기위해 Recursive-descent 법을 쓰는것 (http://brad2014.tistory.com/200)
자체도 어렵고 EBNF 로 내가 하고자하는걸 정의하는것도 어렵다. 

어쨋든 이런저런 어렵기만한 미니언어 만들기를 스칼라의 컴비네이터 파서를 이용하면 쪼금은 쉽게 할수있게 된다.

(그렇다고 엄청 쉬워지진 않는다. OTL )


Scala 컴비네이터 파싱

구문트리를 만들기위해 파싱하는 방법으로는 

첫째. 직접 파싱하는 방법
둘째. 도구를 이용하는 방법 ( lex , yacc 따위들) 
셋째. 컴비네이터 파서를 이용한벙법이있다.

스칼라에 있는 컴비네이터 파서를 이용하면 구문트리로 만드는 수고를 많이 덜어줄것이다.

expr ::= term { "+" term | "-" term|

term ::= factor {"*" factor | "/" factor}

factor ::= floatingPointNumber | "{" expr "}"

위의 EBNF 를 파싱하기위한 방법은 아래와 같이 어처구니 없게 간단하다(?) . 

import scala.util.parsing.combinator._


class Arith extends JavaTokenParsers {

def expr : Parser[Any] = term~rep("+"~term | "-"~term)

def term : Parser[Any] = factor~rep("*"~factor | "/"~factor)

def factor : Parser[Any] = floatingPointNumber | "("~expr~")"

}

1. 소개 

1.1  기본 노테이션

1.2   컴비네이터 VS  EBNF  와  정규표현식 

1.3   컴비네이터 VS  특별한 파싱 시스템

1.4   컴비네이터 in 스칼라  VS  다른 언어 


 2. 이론적 백그라운드 


 3. Usage 패턴


 4. 공통 문제들 


 5. 예제 프로젝트 


 6. 결론 


작성중..,,,,,,,,



레퍼런스 : 

http://labun.com/fh/ma.pdf

http://www.artima.com/shop/programming_in_scala_2ed 

'인터프리터 ' 카테고리의 다른 글

Recursive Descent vs Lex/Parse?  (0) 2015.05.19
Recursive Descent Parsing  (0) 2015.05.19
소형 SQL 인터프리터 만들기  (0) 2015.05.07
Comments