관리 메뉴

HAMA 블로그

소형 SQL 인터프리터 만들기 본문

인터프리터

소형 SQL 인터프리터 만들기

[하마] 이승현 (wowlsh93@gmail.com) 2015. 5. 7. 09:38

* 작성되는글은 Holub on Pattern 을 보고 정리한것입니다.


먼저 BNF



statement  ::= INSERT INTO INDENTIFIER [LP idList RP] VALUES LP exprList RP 

| CREATE DATABASE IDENTIFIER

| CREATE TABLE IDENTIFIER LP declarations RP

| DROP TABLE IDENTIFIER

| BEGIN | WORK | TRAN[SACTION]]

| COMMIT | WORK | TRAN[SACTION]]

| ROLLBACK [WORK | TRAN[SACTION]]

| DUMP

| USE DATABASE IDENTIFIER

| UPDATE IDENTIFIER SET IDENTIFIER EQUAL expr WHERE expr

| DELETE FROM IDENTIFIER WHERE expr

| SELECT [INTO identifier idList FROM idList [WHERE expr]


 

idList       ::= IDENTIFIER idList' | STAR

idList'       ::= COMMA IDENTIFIER idList' |  ε


declarations  ::= IDENTIFIER [type] [NOT [NULL]] declarations'

declarations'  ::= COMMA IDENTIFIER [type] declarations' 

  | COMMA PRIMARY KEY LP IDENTIFER RP  |  ε


type        ::= INTEGER [ LP expr RP ]

|  CHAR [ LP expr RP ]

| NUMERIC [ LP expr COMMA expr RP ]

| DATE


exprList     ::= expr exprList'

exprList'    ::= COMMA expr exprList'  |  ε


expr        ::= andExpr expr'

expr'       ::= OR andExpr expr'


andExpr    ::= relationalExpr andExpr'

andExpr'   ::= AND relationalExpr andExpr''


relationalExpr    ::= additiveExpr relationalExpr'

relationalExpr'    ::= RELOP additiveExpr relationalExpr'

|   EQUAL additiveExpr relationalExpr'

|  LIKE    additiveExpr relationalExpr'

|  ε



addtiveExpr     ::=  multiplicativeExpr additiveExpr'

additiveexpr'    ::= ADDITIVE multiplictiveExpr additiveExpr'


multiplicativExpr    ::= term multiplicativeExpr'

multiplicativeExpr   ::= STAR term multiplicativeExpr'

| SLASH term multiplicativeExpr'

|  ε


term             ::=  NOT factor

|     LP expr RP

|     factor


factor            ::= compoundId | STRING | NUMBER | NULL


compoundId     ::= IDENTIFIER compoundId'

compoundId'    ::= DOT IDENTIFIER

|  ε




위의 BNF 를 기준으로  이터레이터패턴을 적용하여 클래스를 만든후에 






SELECT     first, last 

FROM       people, zip 

WHERE     people.last = 'Flintstone' 

AND    people.first = 'Fred' 

OR     people.zip > (94700 + zip.margin) 


이 문장을 파싱(Recursive-descent 법으로) 해서 구문트리(추상문법트리) 를 만들어보면 아래와 같다. 



좀 구체적인 물리적 클래스에 의한 추상 문법 트리는 아래와 같다.




* 위에 그림에서 AND, OR 로 연결된 부분은  LogicalExpression 이다. (RelationalExpression 이 아님 ) 


결국 순서는 BNF 구성 ->  클래스 설계 -> 실제 구문 파싱 -> 추상문법트리 구성 -> 실제 구문 평가 



실제 작동하는 소스를 보면 


전체적 순서는 


else if( in.matchAdvance(SELECT) != null )      // SELECT 로 시작될때

{ List columns = idList();            // 컬럼들을 리스트로 얻어옴.


String into = null;

if( in.matchAdvance(INTO) != null )    // INTO 가 있다면 

into = in.required(IDENTIFIER);


in.required( FROM );                         // FROM 이 있어야한다.

List requestedTableNames = idList(); // 조인될 테이블들 리스트로 얻어옴.


  //파싱후 추상구문트리 완성

Expression where = (in.matchAdvance(WHERE) == null)  ? null : expr();

 

        // 추상구문트리를 이용하여 실제 테이블들을 평가해서 새 테이블을 만듬.

Table result = doSelect(columns, into, requestedTableNames, where );

return result;

}



파싱 


private Expression expr() throws ParseFailure

{ Expression left = andExpr();

while( in.matchAdvance(OR) != null )

left = new LogicalExpression( left, OR, andExpr());

return left;

}


private Expression andExpr() throws ParseFailure

{ Expression left = relationalExpr();

while( in.matchAdvance(AND) != null )

left = new LogicalExpression( left, AND, relationalExpr() );

return left;

}


......



평가


private Table doSelect( List columns, String into,

List requestedTableNames,

final Expression where )

throws ParseFailure

{


Iterator tableNames = requestedTableNames.iterator();


assert tableNames.hasNext() : "No tables to use in select!" ;


// The primary table is the first one listed in the

// FROM clause. The participantsInJoin are the other

// tables listed in the FROM clause. We're passed in the

// table names; use these names to get the actual Table

// objects.


Table primary = (Table) tables.get( (String) tableNames.next() );


List participantsInJoin = new ArrayList();

while( tableNames.hasNext() )

{ String participant = (String) tableNames.next();

participantsInJoin.add( tables.get(participant) );

}


// Now do the select operation. First create a Strategy

// object that picks the correct rows, then pass that

// object through to the primary table's select() method.


Selector selector = (where == null) ? Selector.ALL : //{=Database.selector}

new Selector.Adapter()

{ public boolean approve(Cursor[] tables)

{ try

{

Value result = where.evaluate(tables);


verify( result instanceof BooleanValue,

"WHERE clause must yield boolean result" );

return ((BooleanValue)result).value();

}

catch( ParseFailure e )

{ throw new ThrowableContainer(e);

}

}

};


try

{ Table result = primary.select(selector, columns, participantsInJoin);


// If this is a "SELECT INTO <table>" request, remove the 

// returned table from the UnmodifiableTable wrapper, give

// it a name, and put it into the tables Map.


if( into != null )

{ result = ((UnmodifiableTable)result).extract();

result.rename(into);

tables.put( into, result );

}

return result;

}

catch( ThrowableContainer container )

{ throw (ParseFailure) container.contents();

}

}


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

Scala 언어를 이용한 미니언어 만들기  (0) 2015.06.06
Recursive Descent vs Lex/Parse?  (0) 2015.05.19
Recursive Descent Parsing  (0) 2015.05.19
Comments