【No.3】ミニ構文解析器をつくる

ここでは、超簡単な構文解析器を作ります。

BNF

これから作ろうとしている「言語」のBNFは、以下のようなものでした。

<program> ::= program <command list>
<command list> ::= <command>* end
<command> ::= <repeat command> | <primitive command>
<repeat command> ::= repeat <number> <command list>
<primitive command> ::= go | right | left

（結城浩『Java言語で学ぶデザインパターン入門　第３版』SBクリエイティブ、p381）

結城本のBNFをそのまま流用します。

実装

上記のBNFをもとに、再帰下降構文解析を行います。

まずは、構文解析器の「インタフェース」（窓口）になるクラスから作成します。
conductメソッドに字句解析器を引数として渡すと、作成したASTのルート（最上位）のノードが返ってきます。

package parser;

import lexer.Lexer;

public class Parser {
	
	public AstNode conduct(Lexer lexer) {
		AstNode root = new ProgramNode().parse(lexer);
		return root;
	}
}

文法の要素ごとにクラスを作成しています。
AstNodeインタフェースを実装したクラスになっています。

AstNode

package parser;

import lexer.Lexer;

interface AstNode {
   
   AstNode parse(Lexer lexer);

}

ProgramNode

package parser;

import lexer.Lexer;

class ProgramNode implements AstNode{
   
   private AstNode child;
   
   @Override
   public AstNode parse(Lexer lexer) {
   	lexer.nextToken();
   	child = new CommandList().parse(lexer);		
   	return this;
   }
}

CommandList

package parser;

import lexer.Lexer;
import java.util.*;

public class CommandList implements AstNode{

	private List<AstNode> children = new ArrayList<>();
	
	@Override
	public AstNode parse(Lexer lexer) {
		while(! lexer.getToken().equals("END")) {			
			AstNode child = new Command().parse(lexer);
			children.add(child);
			lexer.nextToken();
		}
		return this;
	}
}

Command

package parser;

import lexer.Lexer;

public class Command implements AstNode {
	
	private AstNode child;

	@Override
	public AstNode parse(Lexer lexer) {
		if(lexer.getToken().equals("REPEAT")) {
			child = new RepeatCommand().parse(lexer);
		}
		else if(lexer.getToken().equals("GO")|
				lexer.getToken().equals("RIGHT")|
				lexer.getToken().equals("LEFT") 
				) {
			child = new PrimitiveCommand().parse(lexer);
		}
		return this;
	}
}

RepeatCommand

package parser;

import lexer.Lexer;

public class RepeatCommand  implements AstNode {

	private int number;
	private AstNode child;

	@Override
	public AstNode parse(Lexer lexer) {
		lexer.nextToken();
		number = Integer.parseInt(lexer.getToken());	
		lexer.nextToken();
		child = new CommandList().parse(lexer);
		return this;		    
	}
}

PrimitiveCommand

package parser;

import lexer.Lexer;

public class PrimitiveCommand implements AstNode {
	
	private String command;

	@Override
	public AstNode parse(Lexer lexer) {		
		command = lexer.getToken();	
		return this;
	}
}

以上です。

課題

lexer.getToken().equals("END")みたいに、べた書きでトークンの種類を判別しているのは良くなさそうです。
Commandクラスの

Command

else if(lexer.getToken().equals("GO")|
	lexer.getToken().equals("RIGHT")|
	lexer.getToken().equals("LEFT") ) {
		child = new PrimitiveCommand().parse(lexer);
	}

なんて、絶対に書いてはいけない系のコードですよね。
そのため、lexer.getToken().isPrimitiveToken()みたいに、メソッドでトークンの種類を判別できるようにしたいです。
字句解析器をリファクタする必要がありそうです。

それよりもヤバいのが、現状だと文法チェックを全く行っていないので、「間違った文法で書かれたコード」に対応できないところですね。

いろいろ（たくさん）課題はありますが、ゆっくり改善してゆくことにします。