HAMA 블로그

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' |  ....}*

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

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

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

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~")"

}

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

|  ε

SELECT     first, last 

FROM       people, zip 

WHERE     people.last = 'Flintstone' 

AND    people.first = 'Fred' 

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

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();

}

}