소형 SQL 인터프리터 만들기

* 작성되는글은 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();

}

}