지난 글 "파서 놀이 1 - 간단한 렉서 만들기(http://javacan.tistory.com/entry/파서놀이-1-간단렉서)"에서 정규 표현식을 이용해서 토큰을 만들어주는 간단한 렉서를 구현해봤는데, 이제 파서를 만들어 보자. 여기서 만들 파서는 재귀 하향 파서다.
파싱 결과로 만들 모델
모델은 아주 단순하다. 필터 기능을 제공할 IpFilter와 IP 범위를 담는 IpRanger가 출현한다. 두 클래스는 각각 다음과 같다.
public class IpFilter {
private boolean allowFirst;
private List<IpRange> allowIpRangeList = new ArrayList<>();
private List<IpRange> denyIpRangeList = new ArrayList<>();
public IpFilter() {
allowFirst = true;
}
public boolean allow(String ip) { ... }
public void setAllowFirst(boolean allowFirst) {
this.allowFirst = allowFirst;
}
public void addAllowIpRange(IpRange ipRange) {
allowIpRangeList.add(ipRange);
}
public void addAllowIpRanges(List<IpRange> allowIpRanges) {
allowIpRangeList.addAll(allowIpRanges);
}
public void addDenyIpRange(IpRange ipRange) {
denyIpRangeList.add(ipRange);
}
public void addDenyIpRanges(List<IpRange> denyIpRanges) {
denyIpRangeList.addAll(denyIpRanges);
}
...
}
public class IpRange {
public IpRange(String range) {
this.range = range;
}
public boolean ipIn(String ip) { ... }
앞선 글에서 렉서 구현에 사용한 설정 예는 다음과 같았다.
allow 172.20.0.128/25
allow 172.30.0.1-255
allow 172.30.1.1
deny 10.10.10.10
order deny, allow
이 글에서 만들 파서는 위 설정을 이용해서 다음과 같은 코드를 실행해서 IpFilter를 생성하는 것이 목표다.
IpFilter ipFilter = new IpFilter();
ipFilter.addAllowIpRange(new IpRange("172.20.0.128/25");
ipFilter.addAllowIpRange(new IpRange("172.30.0.1-255");
ipFilter.addAllowIpRange(new IpRange("172.30.1.1");
ipFilter.addDenyIpRange(new IpRange("10.10.10.10");
ipFilter.setAllowFirst(false); // order deny, allow
재귀 하향 파서(Recursive Descent Parser)
재귀 하향 파서. 이름이 어렵지만, 실제 구현을 보면 생각만큼 어렵지 않다. 문법에서 심볼에 해당하는 메서드를 구하고 각 메서드에서 토큰이 해당 문법을 충족하는지 확인하고 문법을 충족할 경우 필요한 작업(모델 객체 생성과 같은)을 구현하면 된다.
기억을 되살리는 의미에서 문법을 다시 보자.
config : allowOrDenyDeclList orderDecl?;
allowOrDenyDeclList : allowOrDenyDecl*;
allowOrDenyDecl : allowDecl | denyDecl;
allowDecl : ALLOW iprange;
denyDecl : DENY iprange;
orderDecl : ORDER allowDeny | denyAllow;
ORDER : 'order';
allowDeny : ALLOW ',' DENY;
denyAllow : DENY ',' ALLOW;
ALLOW : 'allow';
DENY : 'deny';
iprange : DIGIT+ '.' DIGIT+ '.' DIGIT+ '.' DIGIT+ ( ('/' | '-') DIGIT+)?;
이 문법의 심볼(config, allowOrDenyDeclList 등)은 각각 파서의 한 개 메서드와 대응한다.
파서 구현의 시작
파서는 파싱 결과로 객체를 생성할 때 필요한 객체를 담기 위한 필드를 갖는다. allowFirst, alloIpRanges, denyIpRanges가 이에 해당한다. 생성자로 TokenBuffer를 받으며, 각 파싱 메서드는 토큰버퍼로부터 토큰을 가져와 문법에 맞는지 확인하고 문법에 맞다면 필요한 작업을 수행한다.
public class IpFilterParser {
private TokenBuffer tokenBuffer;
private boolean allowFirst = true;
private List<IpRange> allowIpRanges = new ArrayList<>();
private List<IpRange> denyIpRanges = new ArrayList<>();
private Exception occuredException;
private IpFilter result;
public IpFilterParser(TokenBuffer tokenBuffer) {
this.tokenBuffer = tokenBuffer;
}
public void parse() {
try {
if (config()) {
createResult();
}
} catch (Exception e) {
occuredException = e;
}
}
config() 메서드는 문법의 최상위 심볼인 config를 처리하는 메서드다. config()가 정상적으로 동작하면 true를 리턴한다. config() 메서드가 true를 리턴하면, 정상적으로 파싱했다는 것을 의미하며 이는 결과적으로 파싱한 결과 값을 allowFirst, allowIpRanges, denyIpRanges에 값을 추가했다는 것을 뜻한다. createResult() 메서드는 이들 값을 이용해서 IpFilter 객체를 생성한다.
config() 실행 도중에 익셉션이 발생하면 occuredException 필드에 보관한다. 이는 뒤에서 파싱을 성공했는지 검사할 때 사용한다.
config 심볼: config() 메서드 구현
config 심볼의 문법은 다음과 같다.
config : allowOrDenyDeclList orderDecl?;
이 문법의 의미는 allowOrDenyDeclList가 오고 그 다음에 orderDecl()이 온다는 뜻이다. 즉, 파서를 구현할 때에는 allowOrDenyDeclList() 파싱에 성공해야 그 다음에 orderDecl() 파싱을 진행해야 한다. 이를 코드로는 다음과 같이 구현할 수 있다.
public boolean config() {
// config : allowOrDenyDeclList orderDecl?;
if (allowOrDenyDeclList()) {
if (optionalOrderDecl()) {
return true;
}
}
return false;
}
config() 메서드는 allowOrDenyDeclList()가 true를 리턴한 경우, 즉 파싱에 성공한 경우에만 그 다음 심볼인 orderDecl을 진행한다. orderDecl은 선택이므로 이를 표현하기 위해 해당 메서드 이름을 optionalOrderDecl()로 설정했다. config 심볼에 따라 config() 메서드는 allowOrDenyDeclList()와 optionalOrderDecl()이 모두 파싱에 성공한 경우 true를 리턴하고 그렇지 않으면 false를 리턴한다.
allowOrDenyDeclList 심볼: allowOrDenyDeclList() 메서드 구현
allowOrDenyDeclList 심볼은 다음과 같다.
allowOrDenyDeclList : allowOrDenyDecl*;
이 심볼은 allowOrDenyDecl이 존재하지 않거나 한 번 이상 존재할 수 있다. 즉, allowOrDenyDecl 문법에 일치하지 않아도 allowOrDenyDeclList()의 파싱은 실패하지 않는다. 단지 어떤 결과도 없을 뿐이다. allowOrDenyDeclList 심볼의 파싱 구현은 다음과 같다.
private boolean allowOrDenyDeclList() {
// allowOrDenyDeclList: allowOrDenyDecl*;
while (allowOrDenyDecl()) {
}
return true;
}
allowOrDenyDecl()이 false를 리턴할 때 까지 반복하는데, 중요한 점은 항상 true를 리턴한다는 점이다. 즉, allowOrDenyDecl()이 파싱을 한 번도 못해도 allowOrDenyDeclList는 파싱에 성공한 것으로 간주한다.
allowOrDenyDecl 심볼 : allowOrDeny() 메서드 및 관련 메서드 구현
allowOrDenyDecl 심볼 및 관련 심볼은 다음과 같다.
allowOrDenyDecl : allowDecl | denyDecl;
allowDecl : ALLOW iprange;
denyDecl : DENY iprange;
allowOrDenyDecl 심볼은 allowDecl이거나 denyDecl 이므로 다음과 같이 파싱 과정을 구현할 수 있다.
private boolean allowOrDenyDecl() {
// allowOrDenyDecl : allowDecl | denyDecl;
if (allowDecl()) {
return true;
} else if (denyDecl()) {
return true;
}
return false;
}
allowDecl()에 성공하면 true를 리턴하고 allowDecl()이 아니면 denyDecl()로 넘어간다. denyDecl()이 성공하면 true를 리턴한다. 둘 다 아니면 false를 리턴한다.
allowDecl 심볼의 파싱 구현이 다소 복잡하다. 실제 토큰을 이용해서 파싱하기 때문이다. allowDecl()의 구현은 다음과 같다.
private boolean allowDecl() {
// allowDecl : ALLOW iprange;
// 토큰 버퍼의 현재 위치 저장
int save = tokenBuffer.currentPosition();
boolean parseSuccess = false;
if (tokenBuffer.currentTokenAndMoveNext().getType() == TokenType.TT_ALLOW) {
Token token = tokenBuffer.currentTokenAndMoveNext();
if (token.getType() == TokenType.TT_IPRANGE) {
allowIpRanges.add(new IpRange(token.getValue())); // IpRange 객체 생성
parseSuccess = true;
} else {
fail("IpRange token expected, but " + token.toString(), token);
}
}
// allowDecl 심볼이 아니면 토큰 버퍼의 위치를 원래대도 되돌림
if (!parseSuccess) {
tokenBuffer.resetPosition(save);
}
return parseSuccess;
}
private void fail(String s, Token token) {
throw new ParseFailException(s, token);
}
alloDesc 심볼은 "ALLOW iprange"이므로 TT_ALLOW 타입 토큰과 TT_IPRANGE 타입 토큰이 차례대로 와야 한다. allowDesc() 메서드는 토큰 버퍼에서 토큰을 가져와 차례대로 TT_ALLOW, TT_IPRANGE 타입 토큰인지 확인한다. 두 토큰의 타입이 일치하면 TT_IPRANGE 타입 토큰의 값을 이용해서 IpRange 객체를 생성하고 allowIpRanges 리스트(필드)에 추가한다.
allowDesc() 메서드는 토큰 타입이 일치하지 않는 경우를 대비해 토큰을 가져오기 전 토큰버퍼의 위치를 저장한다. 파싱에 성공하지 않으면 토큰 버퍼를 원래 위치로 되돌린다. 파싱 성공 여부는 partSuccess 변수에 저장한다. 두 토큰이 차례대로 TT_ALLOW, TT_IPRANGE인 경우에만 partSuccess가 true가 되므로 첫 번째 토큰이 TT_ALLOW 타입이 아니면 토큰 버퍼는 원래 위치로 되돌아간다.
첫 번째 토큰이 TT_ALLOW 타입이었는데 두 번째 토큰 타입이 TT_IPRANGE가 아니면 문법에 어긋나는 것이다. 따라서 파싱을 더 이상 진행하지 않고 익셉션을 발생시킨다. 익셉션이 발생하면 최초의 메서드를 실행한 parse() 메서드의 catch 블록에서 익셉션을 처리한다. (앞의 parse() 구현을 보자.)
denyDecl 심볼의 파싱을 처리하는 denyDecl() 메서드는 allowDecl()과 거의 동일하다.
private boolean denyDecl() {
// denyDecl : DENY iprange;
int save = tokenBuffer.currentPosition();
boolean parseSuccess = false;
if (tokenBuffer.currentTokenAndMoveNext().getType() == TokenType.TT_DENY) {
Token token = tokenBuffer.currentTokenAndMoveNext();
if (token.getType() == TokenType.TT_IPRANGE) {
denyIpRanges.add(new IpRange(token.getValue()));
parseSuccess = true;
} else {
fail("IpRange token expected, but " + token.toString(), token);
}
}
if (!parseSuccess) {
tokenBuffer.resetPosition(save);
}
return parseSuccess;
}
흐름 한 판 정리
앞서 config() 메서드를 다시 보자.
public boolean config() {
// config : allowOrDenyDeclList orderDecl?;
if (allowOrDenyDeclList()) {
if (optionalOrderDecl()) {
return true;
}
}
return false;
}
지금까지 구현한 파싱 코드는 allowOrDenyDeclList 심볼과 관련된 내용이다. 메서드의 흐름을 보면 다음과 같음을 알 수 있다.
- config() // config : allowOrDenyDeclList orderDecl?
- allowOrDenyDeclList() // allowOrDenyDeclList : allowOrDenyDecl*
- while allowOrDenyDecl() // allowOrDenyDecl : allowDecl | denyDecl
- if allowDecl() else denyDecl()
- optionalOrderDecl()
allowDeny()가 파싱에 성공하면 allowFirst 필드 값을 true로 설정하고, denyAllow()가 파싱에 성공하면 allowFirst를 false로 설정한다.
파서의 결과 생성
최초의 parse() 메서드는 다음과 같았다.
public void parse() {
try {
if (config()) {
createResult();
}
} catch (Exception e) {
occuredException = e;
}
}
즉, 모든 파싱에 성공하면 createResult()로 파싱 결과를 생성한다. createResult()는 다음과 같이 IpFilter 객체를 생성한다.
private void createResult() {
IpFilter ipFilter = new IpFilter();
ipFilter.setAllowFirst(allowFirst);
ipFilter.addAllowIpRanges(allowIpRanges);
ipFilter.addDenyIpRanges(denyIpRanges);
this.result = ipFilter;
}
렉서와 파서 붙이기
앞서 구현한 렉서와 파서를 붙이는 건 어렵지 않다. Lexer로 TokenBuffer를 생성하고, 그 TokenBuffer를 파서에 전달한 뒤 파싱을 실행하면 된다. 그리고, 파싱 결과에 따라 결과를 구하면 끝이다.
Lexer lexer = new Lexer(someCode);
TokenBuffer tokens = lexer.tokenize();
IpFilterParser parser = new IpFilterParser(tokens);
parser.parse();
if (parser.isSuccess()) {
Optional<IpFilter> filterOpt = parser.getResult();
IpFilter ipFilter = filterOpt.get();
}
이번 글에서 간단한 재귀 하향 파서를 구현의 감을 익혔는데, 다음엔 파서를 조합해서 파서를 만드는 콤비네이터 파서를 구현해보자.