소형 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();
}
}