簡単な再帰下降構文解析プログラムを書いてみた

java

programming

再帰下降構文解析のアルゴリズムを調べたので、理解を深めるために自分で簡単なParserを書いてみました。

通常はパーサージェネレーターを使えば一撃で終わる話なんですが、たまにこういうの作ってみるとおもしろいですね。ネット上には、中置記法を逆ポーランド記法に変換したり、四則演算の計算をするものはいくつもあるのですが、抽象構文木を作ってくれている例がなかったので、内部的には抽象構文木もどきを作ってから、それをトラバースして結果を得るようになっています。昔、勉強したときにはLL(1)の１は1つ先読みが必要ということと言われて、よく意味が分からなかったのですが、時を越えてそのあたりがやっと分かるようになりました。

† 四則演算Parser

四則演算の式から抽象構文木もどきを得るプログラムです。

2 * ( 3 + 4 )
pre: * 2 + 3 4 
in: 2 * 3 + 4 
post: 2 3 4 + * 
breadthFirst: * 2 + 3 4 
depthFirst: * 2 + 3 4 

Lexerを書くのが面倒だったので、入力される中置記法の式はスペースで区切られているという前提にしています。
内部的にはNodeを使ったASTもどきを作り、それをトラバースして結果を出力します。単項演算子には対応してません。
エラーチェックもところどころ甘いのですが、ひとまずこれでOKかなと。

Driver.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Driver {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Parser p = new Parser(br.readLine().split(" "));
		Node root = p.parse();

		System.out.print("pre: ");
		preOrder(root);
		System.out.println();

		System.out.print("in: ");
		inOrder(root);
		System.out.println();

		System.out.print("post: ");
		postOrder(root);
		System.out.println();

		System.out.print("breadthFirst: ");
		breadthFirst(root);
		System.out.println();

		System.out.print("depthFirst: ");
		depthFirst(root);
		System.out.println();
	}

	public static void preOrder(Node n){
		System.out.print(n.value+" ");
		if( n.left != null ){
			preOrder(n.left);
		}
		if( n.right != null ){
			preOrder(n.right);
		}
	}

	public static void inOrder(Node n){
		if( n.left != null ){
			inOrder(n.left);
		}
		System.out.print(n.value+" ");
		if( n.right != null ){
			inOrder(n.right);
		}
	}

	public static void postOrder(Node n){
		if( n.left != null ){
			postOrder(n.left);
		}
		if( n.right != null ){
			postOrder(n.right);
		}
		System.out.print(n.value+" ");
	}

	public static void breadthFirst(Node n){
		Queue<Node> q = new LinkedList<Node>();
		q.offer(n);
		while( !q.isEmpty() ){
			Node current = q.poll();
			System.out.print(current.value+" ");
			if( current.left != null )
				q.offer(current.left);
			if( current.right != null )
				q.offer(current.right);
		}
	}

	public static void depthFirst(Node n){
		Stack<Node> s = new Stack<Node>();
		s.push(n);
		while( !s.isEmpty() ){
			Node current = s.pop();
			System.out.print(current.value+" ");
			if( current.right != null )
				s.push(current.right);
			if( current.left != null )
				s.push(current.left);
		}
	}
}

class Node {
	public Node left;
	public Node right;
	public String value;

	public Node(String value, Node left, Node right){
		this.left = left;
		this.right = right;
		this.value = value;
	}
}

class Parser {
	private String[] tokens;
	private int pos;

	public Parser(String[] tokens){
		this.tokens = tokens;
		pos = 0;
	}

	private String peek(){
		if(pos < tokens.length)
			return tokens[pos];
		return null;
	}

	private String poll(){
		return tokens[pos++];
	}

	public Node parse(){
		return expression();
	}

	// <expression> := <term> + <expression> | <term> - <expression> | <term>
	private Node expression() {
		Node n = term();
		while ( "+".equals(peek()) || "-".equals(peek()) ){
			n = new Node(poll(), n, term());
		}
		return n;
	}

	// <term> := <factor> * <term> | <factor> / <term> | <factor>
	private Node term() {
		Node n = factor();
		while ( "*".equals( peek()) || "/".equals( peek())) {
			n = new Node(poll(), n, factor());
		}
		return n;
	}

	//<factor> := ( <expression> ) | number
	private Node factor() {
		if ( "(".equals( peek() ) ) {
			poll(); // delete "("
			Node n = expression();
			poll(); // delete ")"
			return n;
		} else {
			return new Node(poll(), null, null);
		}
	}
}