- Relational algebra – 관계대수
- Relational algebra – SQL Interpreter by Antlr
ANTLR
Antlr( ANother Tool for Language Recognition : 언어 인식을 위한 또 다른 도구?)은 구조화된 텍스트 또는 이진 파일을 읽고, 처리하고, 실행하거나 번역하기 위한 강력한 Parser를 생성해 주는 Tool이다. ANTLR은 생성한 문법을 사용하여 구문분석 트리(또는 추상 구문 트리 – abstract syntax tree , AST )를 작성하고 탐색할 수 있는 구문 분석기를 생성해준다.
https://github.com/antlr/antlr4/blob/master/doc/index.md
개발 환경
Intellij Antlr plugin
antlr plugin을 설치하면 IDE내에서 생성한 문법에 대한 syntax체크를 할 수 있으며 생성한 문법을 이용하여 텍스트를 파싱하고 구문분석 트리를 확인할 수 있다.
Gradle을 이용한 Antlr 프로젝트 설정
Gradle Java 프로젝트를 생성하고 다음과 같이 build.gradle에 antlr 관련 내용을 추가하고 문법 파일을 작성한 다음generateGrammarSource task를 실행하면 Parser를 생성할 수 있다.
build.gradle
plugins {
id 'java'
id 'antlr'
id 'idea'
}
group 'com.kakaopage.antlr'
version '1.0-SNAPSHOT'
repositories {
mavenCentral()
}
dependencies {
antlr "org.antlr:antlr4:4.8"
implementation "org.antlr:antlr4-runtime:4.8-1"
implementation 'org.apache.logging.log4j:log4j-slf4j-impl:2.13.3'
testImplementation group: 'junit', name: 'junit', version: '4.12'
}
generateGrammarSource {
maxHeapSize = "64m"
arguments += ["-visitor",
"-long-messages",
"-package", "com.kakaopage.antlr.generated"
]
doLast {
println "Copying generated grammar lexer/parser files to main directory."
copy {
from "${buildDir}/generated-src/antlr/main"
into "src/main/java/com/kakaopage/antlr/generated"
}
println "Deleting generated grammar lexer/parser files."
delete "${buildDir}/generated-src/"
}
}
clean.doLast {
file('generated-src').deleteDir()
}
개발 Flow
g4 문법 파일 작성
- g4파일은 ANTLR 4버전에서 Parser를 만들기 위해 개발자가 작성하는 문법 파일로서 두 가지 내용을 담고 있다.
- Lexer : Lexer는 구문을 구분하는 토큰 유형을 정의한다. Parser 규칙과 구별하기 위해 대문자로 시작해야 한다.
- Parser : Lexer를 이용하여 입력된 구문을 분석하기 위한 형식을 정의한다.
Calculator.g4 – 사칙 연산 계산기 예제
grammar Calculator;
expression :
expression op=(MUL | DIV) expression #mulDiv
| expression op=(ADD | SUB) expression #addSub
| number #num
| '(' expression ')' #parens
;
number :
NUMBER
;
MUL :
'*'
;
DIV :
'/'
;
ADD :
'+'
;
SUB :
'-'
;
NUMBER :
[0-9]+
;
WS :
[ \t\r\n]+ -> skip
;
구문 테스트 및 AST 확인
antlr plugin을 설치했다면 문법 파일에 대한 검증이 가능하다. IDE 하단의 ANTLR Preview 탭을 활성화시키고 작성한 Calculator.g4 파일을 더블 클릭한다. 아래와 같이 Calculator.g4 start rule:~~~~~ 과 같이 빨간색으로 활성화된 상태에서 g4파일의 expression을 선택 후 Test Rule Expression을 선택한다.
이제 아래와 같이 Text 박스에 사칙 연산 구문을 입력하면 오른쪽 화면에서 Parse Tree를 확인할 수 있다.
Parser는 정상인데 입력 구문이 잘못된 경우 잘못된 입력 내용이 빨간색으로 표시된다.
Parser가 구문분석에 실패한 문자가 있다면 왼쪽 입력 구문과 오른쪽 Tree에 빨간색으로 표시된다. 이때는 g4 파일을 수정하여 문자가 정상적으로 인식되도록 수정해야 한다.
Java Parser 생성
구문 테스트 진행 후 g4파일에 문제가 없다고 판단되면 gradle task를 실행하여 java 형태의 Parser를 생성한다. generateGrammarSource task를 실행하면 아래와 같은 파일들이 생성된다.
Interpreter 생성 및 테스트
Parser를 통해 만들어진 AST 트리의 데이터를 순회하며 연산을 수행하는 Interpreter를 작성한다. Gradle task 실행 후 생성된 파일에서 CalculatorVisitor를 열어보면 g4파일에서 #[이름]으로 작성한 내용이 visit[이름]으로 메서드가 생성되어 있는 것을 확인할 수 있다. 따라서 CalculatorVisitor를 상속받는 class를 작성하고 메서드를 오버라이딩 하여 로직을 작성하면 된다.
// Generated from Calculator.g4 by ANTLR 4.8
package com.kakaopage.antlr.generated;
import org.antlr.v4.runtime.tree.ParseTreeVisitor;
/**
* This interface defines a complete generic visitor for a parse tree produced
* by {@link CalculatorParser}.
*
* @param <T> The return type of the visit operation. Use {@link Void} for
* operations with no return type.
*/
public interface CalculatorVisitor<T> extends ParseTreeVisitor<T> {
/**
* Visit a parse tree produced by the {@code parens}
* labeled alternative in {@link CalculatorParser#expression}.
* @param ctx the parse tree
* @return the visitor result
*/
T visitParens(CalculatorParser.ParensContext ctx);
/**
* Visit a parse tree produced by the {@code num}
* labeled alternative in {@link CalculatorParser#expression}.
* @param ctx the parse tree
* @return the visitor result
*/
T visitNum(CalculatorParser.NumContext ctx);
/**
* Visit a parse tree produced by the {@code addSub}
* labeled alternative in {@link CalculatorParser#expression}.
* @param ctx the parse tree
* @return the visitor result
*/
T visitAddSub(CalculatorParser.AddSubContext ctx);
/**
* Visit a parse tree produced by the {@code mulDiv}
* labeled alternative in {@link CalculatorParser#expression}.
* @param ctx the parse tree
* @return the visitor result
*/
T visitMulDiv(CalculatorParser.MulDivContext ctx);
/**
* Visit a parse tree produced by {@link CalculatorParser#number}.
* @param ctx the parse tree
* @return the visitor result
*/
T visitNumber(CalculatorParser.NumberContext ctx);
}
CalculatorInterpreter
package com.kakaopage.antlr.calculator;
import com.kakaopage.antlr.generated.CalculatorBaseVisitor;
import com.kakaopage.antlr.generated.CalculatorParser;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
public class CalculatorInterpreter extends CalculatorBaseVisitor {
private static final Logger log = LoggerFactory.getLogger(CalculatorInterpreter.class);
@Override
public Object visitParens(CalculatorParser.ParensContext ctx) {
Object obj = visit(ctx.expression());
log.debug("괄호 {}", obj);
return obj;
}
@Override
public Integer visitNum(CalculatorParser.NumContext ctx) {
Integer num = Integer.parseInt(ctx.getText());
log.debug("숫자 {}", num);
return num;
}
@Override
public Integer visitAddSub(CalculatorParser.AddSubContext ctx) {
Integer left = (int) visit(ctx.expression(0));
Integer right = (int) visit(ctx.expression(1));
Integer result = ctx.op.getType() == CalculatorParser.ADD ? left + right : left - right;
log.debug("{} {} {} {} = {}", ctx.op.getType() == CalculatorParser.ADD ? "더하기" : "빼기", left, ctx.op.getText(), right, result);
return result;
}
@Override
public Integer visitMulDiv(CalculatorParser.MulDivContext ctx) {
Integer left = (int) visit(ctx.expression(0));
Integer right = (int) visit(ctx.expression(1));
Integer result = ctx.op.getType() == CalculatorParser.MUL ? left * right : left / right;
log.debug("{} {} {} {} = {}", ctx.op.getType() == CalculatorParser.MUL ? "곱하기" : "나누기", left, ctx.op.getText(), right, result);
return result;
}
}
CalculatorInterpreter를 적용하여 입력 데이터를 연산하는 flow는 다음과 같다.
유닛 테스트
package com.kakaopage.antlr.calculator;
import com.kakaopage.antlr.generated.CalculatorLexer;
import com.kakaopage.antlr.generated.CalculatorParser;
import org.antlr.v4.runtime.CharStreams;
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.tree.ParseTree;
import org.junit.Test;
import static org.junit.Assert.assertSame;
public class CalculatorVisitorTest {
@Test
public void addSubTest() throws Exception {
String ra = "1+2-4";
CalculatorLexer lexer = new CalculatorLexer(CharStreams.fromString(ra));
CommonTokenStream tokens = new CommonTokenStream(lexer);
CalculatorParser parser = new CalculatorParser(tokens);
ParseTree tree = parser.expression();
System.out.println(tree.toStringTree(parser));
CalculatorInterpreter interpreter = new CalculatorInterpreter();
Integer query = (Integer) interpreter.visit(tree);
assertSame(-1, query);
}
@Test
public void mulDivTest() throws Exception {
String ra = "1*2+3*(4+5)";
CalculatorLexer lexer = new CalculatorLexer(CharStreams.fromString(ra));
CommonTokenStream tokens = new CommonTokenStream(lexer);
CalculatorParser parser = new CalculatorParser(tokens);
ParseTree tree = parser.expression();
System.out.println(tree.toStringTree(parser));
CalculatorInterpreter interpreter = new CalculatorInterpreter();
Integer query = (Integer) interpreter.visit(tree);
assertSame(29, query);
}
@Test
public void compositeTest() throws Exception {
String ra = "(6-2)+8/4*(1+6)";
CalculatorLexer lexer = new CalculatorLexer(CharStreams.fromString(ra));
CommonTokenStream tokens = new CommonTokenStream(lexer);
CalculatorParser parser = new CalculatorParser(tokens);
ParseTree tree = parser.expression();
System.out.println(tree.toStringTree(parser));
CalculatorInterpreter interpreter = new CalculatorInterpreter();
Integer query = (Integer) interpreter.visit(tree);
assertSame(18, query);
}
}
Relation Algebra 구문 분석 및 Parser/Interpreter 개발
관계 대수는 모든 피연산자가 relation이고 연산의 결과도 relation이다. 다음 구문들은 모두 서로 다른 규칙을 담고 있는 것처럼 보이지만 큰 테두리에서 보면 모두 relation이라고 보면 된다.
- π R.a, R.b R
- σ R.a > 0 AND R.a < 10 OR R.c > 100 (R)
- π R.a, R.b, cnt, sum γ R.a, R.b; count(*)→cnt, sum(R.a)→sum σ R.a > 1 R
즉 relation은 단순히 String형태( ex. R )와 구문 형태( ex. π R.a, R.b R) 두 가지로 형태가 있다고 보면 된다. g4문법으로 큰 틀을 표현하면 다음과 같다.
grammar Ra;
expr :
LPAREN expr RPAREN #nestedRelation
STRING #simpleRelation
;
구문 (expr : expression)은 algebra 연산자에 따라 조금씩 형태가 틀리므로 해당 내용을 g4문법으로 표현하여 하나씩 적용하면 다음과 같이 된다. 구문은 계속 중첩될 수 있기 때문에 expr이 연산자 앞이나 뒤에 붙게 된다.
grammar Ra;
expr :
expr INTERSECTION expr #intersection
| expr UNION expr #union
| expr DIFFERENCE expr #setDifference
| expr NATURAL_JOIN condition? expr #naturalJoin
| expr LEFT_OUTER_JOIN condition expr #leftJoin
| expr RIGHT_OUTER_JOIN condition expr #rightJoin
| expr FULL_OUTER_JOIN condition expr #fullJoin
| expr CARTESIAN expr #catesianProduct
| selectionExpr #selection
| projectionExpr #projection
| groupbyExpr #groupby
| renameExpr #rename
| orderbyExpr #orderby
| LPAREN expr RPAREN #nestedRelation
| STRING #simpleRelation
;
selectionExpr :
SELECTION conditions expr
;
projectionExpr :
PROJECTION attributes expr
;
renameExpr :
RENAME STRING expr // relation rename
| RENAME renameAttrs expr
;
groupbyExpr :
GROUP_BY attributes SEMI groupByAttrs expr
;
// 생략
전체 소스
https://github.com/codej99/relation-algebra-antlr/blob/master/src/main/antlr/Ra.g4
작성한 문법을 토대로 relation algebra 구문을 분석하면 다음과 같다.
π R.a, R.b R
Interpreter 개발
사칙연산과 동일하게 visitor를 상속받아 로직을 작성한다. (소스 확인으로 대체)
Interpreter 유닛 테스트
GitHub src/test/java/org/antlr/study/algebra 하위에 항목별로 생성함.
ex) Projection Test
public class ProjectionTest {
private static final Logger log = LoggerFactory.getLogger(ProjectionTest.class);
@Test
public void 하나의_projection_구문테스트() {
String ra = "π R.a, R.b R";
RaLexer lexer = new RaLexer(CharStreams.fromString(ra));
CommonTokenStream tokens = new CommonTokenStream(lexer);
RaParser parser = new RaParser(tokens);
ParseTree tree = parser.expr();
log.info(tree.toStringTree(parser));
RaInterpreter interpreter = new RaInterpreter();
String query = (String) interpreter.visit(tree);
assertEquals("SELECT R.a,R.b FROM R", query);
}
@Test
public void projectionSelection_테스트() {
String ra = "π R.a, R.b σ R.a > 0 R";
RaLexer lexer = new RaLexer(CharStreams.fromString(ra));
CommonTokenStream tokens = new CommonTokenStream(lexer);
RaParser parser = new RaParser(tokens);
ParseTree tree = parser.expr();
log.info(tree.toStringTree(parser));
RaInterpreter interpreter = new RaInterpreter();
Object query = interpreter.visit(tree);
assertEquals("SELECT R.a,R.b FROM R WHERE R.a>0", query);
}
}
[실습소스]
https://github.com/codej99/relation-algebra-antlr.git
[참고]
https://www.antlr.org/
https://github.com/antlr/antlr4/blob/master/doc/index.md
https://datacadamia.com/antlr
https://tomassetti.me/antlr-mega-tutorial
https://dbis-uibk.github.io/relax/landing
https://ivanyu.me/blog/2014/09/13/creating-a-simple-parser-with-antlr
