/*
 * Copyright 2013 Yuichiro Moriguchi
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package net.morilib.awk.parser;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

import net.morilib.awk.AwkLocation;
import net.morilib.awk.AwkLvalueException;
import net.morilib.awk.AwkSyntaxException;
import net.morilib.awk.builtin.AwkSplit;
import net.morilib.awk.code.AwkAction;
import net.morilib.awk.code.AwkExecutable;
import net.morilib.awk.code.AwkProgram;
import net.morilib.awk.expr.AwkAdder;
import net.morilib.awk.expr.AwkApplier;
import net.morilib.awk.expr.AwkArrayReferrer;
import net.morilib.awk.expr.AwkAssigner;
import net.morilib.awk.expr.AwkCommaOp;
import net.morilib.awk.expr.AwkConcatenator;
import net.morilib.awk.expr.AwkConditionOp;
import net.morilib.awk.expr.AwkDeclementer;
import net.morilib.awk.expr.AwkDivider;
import net.morilib.awk.expr.AwkExpression;
import net.morilib.awk.expr.AwkFunctionPrototype;
import net.morilib.awk.expr.AwkFunctionReferrer;
import net.morilib.awk.expr.AwkInOp;
import net.morilib.awk.expr.AwkInclementer;
import net.morilib.awk.expr.AwkLiteralFloat;
import net.morilib.awk.expr.AwkLiteralInteger;
import net.morilib.awk.expr.AwkLiteralRegex;
import net.morilib.awk.expr.AwkLiteralString;
import net.morilib.awk.expr.AwkLogicalAndOp;
import net.morilib.awk.expr.AwkLogicalNotOp;
import net.morilib.awk.expr.AwkLogicalOrOp;
import net.morilib.awk.expr.AwkMatcher;
import net.morilib.awk.expr.AwkMultiArrayOp;
import net.morilib.awk.expr.AwkMultiplier;
import net.morilib.awk.expr.AwkNegater;
import net.morilib.awk.expr.AwkNotMatcher;
import net.morilib.awk.expr.AwkPowerOp;
import net.morilib.awk.expr.AwkReferField;
import net.morilib.awk.expr.AwkReferVariable;
import net.morilib.awk.expr.AwkRelationOp;
import net.morilib.awk.expr.AwkRemainderOp;
import net.morilib.awk.expr.AwkSubtracter;
import net.morilib.awk.io.AwkClose;
import net.morilib.awk.io.AwkGetline;
import net.morilib.awk.io.AwkPrint;
import net.morilib.awk.io.AwkPrintf;
import net.morilib.awk.namespace.AwkNamespace;
import net.morilib.awk.pattern.AwkAndPattern;
import net.morilib.awk.pattern.AwkBeginEnd;
import net.morilib.awk.pattern.AwkExpressionPattern;
import net.morilib.awk.pattern.AwkNotPattern;
import net.morilib.awk.pattern.AwkOrPattern;
import net.morilib.awk.pattern.AwkPattern;
import net.morilib.awk.pattern.AwkRangedPattern;
import net.morilib.awk.pattern.AwkRegexPattern;
import net.morilib.awk.statement.AwkBreak;
import net.morilib.awk.statement.AwkContinue;
import net.morilib.awk.statement.AwkDelete;
import net.morilib.awk.statement.AwkDoWhile;
import net.morilib.awk.statement.AwkExit;
import net.morilib.awk.statement.AwkFor;
import net.morilib.awk.statement.AwkForIn;
import net.morilib.awk.statement.AwkIf;
import net.morilib.awk.statement.AwkNext;
import net.morilib.awk.statement.AwkNop;
import net.morilib.awk.statement.AwkReturn;
import net.morilib.awk.statement.AwkSequence;
import net.morilib.awk.statement.AwkWhile;

/**
 * awkiumのパーサです。<br />
 * awkiumは再帰下降型のパーサです。つまり、LL(1)で記述されています。
 * 
 * @author MORIGUCHI, Yuichiro 2013/03
 */
public final class AwkParser {

	static final AwkToken BEGIN = AwkSymbol.getInstance("BEGIN");
	static final AwkToken END = AwkSymbol.getInstance("END");
	static final AwkToken SPLIT = AwkSymbol.getInstance("split");

	private AwkParser() {}

	static AwkPattern patid(AwkLexer rd) throws IOException {
		AwkPattern p;
		AwkToken t;
		String v;

		if((t = rd.getToken()).equals(AwkOperator.LPAREN)) {
			rd.nextToken();
			p = patterm(rd);
			rd.eatToken(AwkOperator.RPAREN);
			return p;
		} else if(t.equals(AwkOperator.DIV)) {   // regex
			v = rd.getPattern();
			rd.nextToken();
			return new AwkRegexPattern(v);
		} else if(t.equals(AwkAssignop.A_DIV)) {   // regex
			v = rd.getPattern();
			rd.nextToken();
			return new AwkRegexPattern("=" + v);
		} else {
			return new AwkExpressionPattern(parseExpression(rd));
		}
	}

	static AwkPattern patnot(AwkLexer rd) throws IOException {
		if(rd.getToken().equals(AwkOperator.L_NOT)) {
			rd.nextToken();
			return new AwkNotPattern(patid(rd));
		} else {
			return patid(rd);
		}
	}

	static AwkPattern patfactor(AwkLexer rd) throws IOException {
		AwkPattern p;

		p = patnot(rd);
		if(rd.getToken().equals(AwkOperator.L_AND)) {
			rd.nextToken();
			return new AwkAndPattern(p, patfactor(rd));
		} else {
			return p;
		}
	}

	static AwkPattern patterm(AwkLexer rd) throws IOException {
		AwkPattern p;

		p = patfactor(rd);
		if(rd.getToken().equals(AwkOperator.L_OR)) {
			rd.nextToken();
			return new AwkOrPattern(p, patterm(rd));
		} else {
			return p;
		}
	}

	/**
	 * awkiumパターンをコンパイルします。
	 * 
	 * @param rd lexer
	 * @return パターンの中間表現
	 * @throws IOException
	 */
	public static AwkPattern parsePattern(
			AwkLexer rd) throws IOException {
		AwkPattern p1, p2;
		AwkToken t = rd.getToken();

		if(t.equals(BEGIN)) {
			rd.nextToken();
			return AwkBeginEnd.BEGIN;
		} else if(t.equals(END)) {
			rd.nextToken();
			return AwkBeginEnd.END;
		} else {
			p1 = patterm(rd);
			if((t = rd.getToken()).equals(AwkOperator.COMMA)) {
				rd.nextToken();
				p2 = patterm(rd);
				return new AwkRangedPattern(p1, p2);
			} else {
				return p1;
			}
		}
	}

	static AwkExpression funcall0(AwkLexer rd,
			AwkExpression s) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		AwkToken t;
		boolean fi = true;

		while(true) {
			if((t = rd.getToken()).equals(AwkOperator.RPAREN)) {
				rd.nextToken();
				return new AwkApplier(s, l);
			} else if(fi) {
				l.add(assignop(rd));
				fi = false;
			} else if(t.equals(AwkOperator.COMMA)) {
				rd.nextToken();
				l.add(assignop(rd));
			} else {
				throw new AwkSyntaxException(
						rd.getLineNumber(), AwkOperator.RPAREN, t);
			}
		}
	}

	static AwkExpression printp(AwkLexer rd,
			AwkToken t) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		List<AwkToken> m = new ArrayList<AwkToken>();
		AwkExpression e, f;
		boolean first = true;
		int a = AwkPrint.OVERWRITE;

		while(!rd.isEos() &&
				!rd.getToken().equals(AwkOperator.RPAREN)) {
			if(!first)  rd.eatToken(AwkOperator.COMMA);
			m.add(rd.getToken());
			l.add(assignop(rd));
			first = false;
		}

		if(t.equals(AwkOperator.LPAREN)) {
			rd.eatToken(AwkOperator.RPAREN);
			f = null;
			if(rd.getToken().equals(AwkRelop.GT)) {
				rd.nextToken();  f = parseExpression(rd);
				a = AwkPrint.OVERWRITE;
			} else if(rd.getToken().equals(AwkReserved.APNDOUT)) {
				rd.nextToken();  f = parseExpression(rd);
				a = AwkPrint.APPEND;
			} else if(rd.getToken().equals(AwkReserved.PIPE)) {
				rd.nextToken();  f = parseExpression(rd);
				a = AwkPrint.PIPE;
			}
			return new AwkPrint(f, l, a);
		} else if(rd.getToken().equals(AwkReserved.APNDOUT)) {
			rd.nextToken();
			f = parseExpression(rd);
			return new AwkPrint(f, l, AwkPrint.APPEND);
		} else if(rd.getToken().equals(AwkReserved.PIPE)) {
			rd.nextToken();
			f = parseExpression(rd);
			return new AwkPrint(f, l, AwkPrint.PIPE);
		} else if(m.size() > 0 &&
				!m.get(m.size() - 1).equals(AwkOperator.LPAREN) &&
				(e = l.get(l.size() - 1)).maybeOutputRedirect()) {
			f = ((AwkRelationOp)e).getRight();
			e = ((AwkRelationOp)e).getLeft();
			l.set(l.size() - 1, e);
			return new AwkPrint(f, l, AwkPrint.OVERWRITE);
		} else {
			return new AwkPrint(null, l, AwkPrint.APPEND);
		}
	}

	static AwkExpression printfp(AwkLexer rd,
			AwkToken t) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		List<AwkToken> m = new ArrayList<AwkToken>();
		AwkExpression e, f, g;
		boolean first = true;
		int a = AwkPrint.OVERWRITE;

		while(!rd.isEos() &&
				!rd.getToken().equals(AwkOperator.RPAREN)) {
			if(!first)  rd.eatToken(AwkOperator.COMMA);
			m.add(rd.getToken());
			l.add(assignop(rd));
			first = false;
		}

		if(m.size() < 1) {
			throw new AwkSyntaxException(
					rd.getLineNumber(), "format required");
		} else if(t.equals(AwkOperator.LPAREN)) {
			rd.eatToken(AwkOperator.RPAREN);
			f = null;
			if(rd.getToken().equals(AwkRelop.GT)) {
				rd.nextToken();  f = parseExpression(rd);
				a = AwkPrint.OVERWRITE;
			} else if(rd.getToken().equals(AwkReserved.APNDOUT)) {
				rd.nextToken();  f = parseExpression(rd);
				a = AwkPrint.APPEND;
			} else if(rd.getToken().equals(AwkReserved.PIPE)) {
				rd.nextToken();  f = parseExpression(rd);
				a = AwkPrint.PIPE;
			}
			g = l.remove(0);
			return new AwkPrintf(f, g, l, a);
		} else if(rd.getToken().equals(AwkReserved.APNDOUT)) {
			rd.nextToken();
			f = parseExpression(rd);
			g = l.remove(0);
			return new AwkPrintf(f, g, l, AwkPrint.APPEND);
		} else if(rd.getToken().equals(AwkReserved.PIPE)) {
			rd.nextToken();
			f = parseExpression(rd);
			g = l.remove(0);
			return new AwkPrintf(f, g, l, AwkPrint.PIPE);
		} else if(m.size() > 0 &&
				!m.get(m.size() - 1).equals(AwkOperator.LPAREN) &&
				(e = l.get(l.size() - 1)).maybeOutputRedirect()) {
			f = ((AwkRelationOp)e).getRight();
			e = ((AwkRelationOp)e).getLeft();
			l.set(l.size() - 1, e);
			g = l.remove(0);
			return new AwkPrintf(f, g, l, AwkPrint.OVERWRITE);
		} else {
			g = l.remove(0);
			return new AwkPrintf(null, g, l, AwkPrint.APPEND);
		}
	}

	static AwkFunctionPrototype funcq(AwkLexer rd) throws IOException {
		AwkExpression e;
		List<String> l = new ArrayList<String>();
		AwkToken t;
		boolean fi = true;

		rd.eatToken(AwkOperator.LPAREN);
		while(!(t = rd.getToken()).equals(AwkOperator.RPAREN)) {
			if(!fi)  rd.eatToken(AwkOperator.COMMA);
			if((t = rd.getToken()) instanceof AwkSymbol) {
				l.add(t.getString());  rd.nextToken();
				fi = false;
			} else {
				throw new AwkSyntaxException(
						rd.getLineNumber(), "symbol", t);
			}
		}

		rd.nextToken();
		if(!rd.getToken().equals(AwkReserved.BLOCK_B)) {
			throw new AwkSyntaxException(
					rd.getLineNumber(), AwkReserved.BLOCK_B, t);
		}
		e = parseStatement(rd);
		return new AwkFunctionPrototype(e, l);
	}

	static AwkExpression arrlist2(AwkLexer rd,
			AwkExpression e) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		AwkToken t;

		l.add(e);
		t = rd.getToken();
		while(!t.equals(AwkOperator.RPAREN)) {
			l.add(assignop(rd));
			if((t = rd.getToken()).equals(AwkOperator.COMMA)) {
				t = rd.nextToken();
			}
		}
		return new AwkMultiArrayOp(l);
	}

	static AwkExpression identifier(AwkLexer rd) throws IOException {
		AwkExpression e, f, g;
		AwkToken t = rd.getToken();
		String v = null;

		if(t instanceof AwkIntegerToken) {
			rd.nextToken();
			return new AwkLiteralInteger(t.getInteger());
		} else if(t instanceof AwkStringToken) {
			rd.nextToken();
			return new AwkLiteralString(t.getString());
		} else if(t instanceof AwkFloatToken) {
			rd.nextToken();
			return new AwkLiteralFloat(t.getFloat());
		} else if(t.equals(SPLIT)) {
			rd.nextToken();  rd.eatToken(AwkOperator.LPAREN);
			e = assignop(rd);
			rd.eatToken(AwkOperator.COMMA);
			f = assignop(rd);
			if(!f.isLvalue()) {
				throw new AwkLvalueException(
						"assignment to non-lvalue");
			}
			rd.eatToken(AwkOperator.COMMA);
			g = parseExpression(rd);
			rd.eatToken(AwkOperator.RPAREN);
			return new AwkSplit(e, f, g);
		} else if(t instanceof AwkSymbol) {
			return new AwkReferVariable(loc1(rd));
		} else if(t.equals(AwkOperator.DIV)) {   // regex
			v = rd.getPattern();
			rd.nextToken();
			return new AwkLiteralRegex(v);
		} else if(t.equals(AwkAssignop.A_DIV)) {   // regex
			v = rd.getPattern();
			rd.nextToken();
			return new AwkLiteralRegex("=" + v);
		} else if(t.equals(AwkOperator.LPAREN)) {
			rd.nextToken();
			e = assignop(rd);
			if(rd.getToken().equals(AwkOperator.COMMA)) {
				rd.nextToken();
				e = arrlist2(rd, e);
			}
			rd.eatToken(AwkOperator.RPAREN);
			return e;
		} else if(t.equals(AwkReserved.GETLINE)) {
			if((t = rd.nextToken()) instanceof AwkSymbol) {
				v = t.getString();
				t = rd.nextToken();
			}

			if(t.equals(AwkRelop.LT)) {
				rd.nextToken();
				e = parseExpression(rd);
			} else {
				e = null;
			}
			return new AwkGetline(v, e, null);
		} else if(t.equals(AwkReserved.PRINT)) {
			if((t = rd.nextToken()).equals(AwkOperator.LPAREN)) {
				rd.nextToken();
			}
			e = printp(rd, t);
			return e;
		} else if(t.equals(AwkReserved.PRINTF)) {
			if((t = rd.nextToken()).equals(AwkOperator.LPAREN)) {
				rd.nextToken();
			}
			e = printfp(rd, t);
			return e;
		} else if(t.equals(AwkReserved.FUNC)) {
			rd.nextToken();
			return funcq(rd);
		} else if(t.equals(AwkOperator.REFFN)) {
			if((t = rd.nextToken()) instanceof AwkSymbol) {
				rd.nextToken();
				return new AwkFunctionReferrer(t.getString());
			} else {
				throw new AwkSyntaxException(
						rd.getLineNumber(), "<symbol>", t);
			}
		} else if(t.equals(AwkReserved.SEMICL)) {
			return new AwkNop();
		} else {
			throw new AwkSyntaxException(
					rd.getLineNumber(), "identifier", t);
		}
	}

	static AwkExpression funcall(AwkLexer rd) throws IOException {
		AwkExpression e, f;

		e = identifier(rd);
		if(rd.getToken().equals(AwkOperator.LPAREN)) {
			rd.nextToken();
			f = funcall0(rd, e);
			return f;
		} else {
			return e;
		}
	}

	static AwkExpression arrlist(AwkLexer rd) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		AwkToken t;

		t = rd.getToken();
		while(!t.equals(AwkOperator.RBRAKET)) {
			l.add(assignop(rd));
			if((t = rd.getToken()).equals(AwkOperator.COMMA)) {
				t = rd.nextToken();
			}
		}
		return new AwkMultiArrayOp(l);
	}

	static AwkExpression refarray(AwkLexer rd) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		AwkExpression e;
		AwkToken t;

		l.add(funcall(rd));
		t = rd.getToken();
		while(t.equals(AwkOperator.LBRAKET)) {
			rd.nextToken();
			l.add(arrlist(rd));
			if(rd.getToken().equals(AwkOperator.RBRAKET)) {
				t = rd.nextToken();
			}
		}
		e = l.get(0);
		for(int i = 1; i < l.size(); i++) {
			e = new AwkArrayReferrer(e, l.get(i));
		}
		return e;
	}

	static AwkExpression field(AwkLexer rd) throws IOException {
		AwkToken t = rd.getToken();

		if(t.equals(AwkOperator.FIELD)) {
			t = rd.nextToken();
			return new AwkReferField(refarray(rd));
		} else {
			return refarray(rd);
		}
	}

	static AwkExpression incdec(AwkLexer rd) throws IOException {
		AwkExpression e;
		AwkToken t;

		if((t = rd.getToken()).equals(AwkOperator.INC)) {
			t = rd.nextToken();
			return new AwkInclementer(field(rd), true);
		} else if(t.equals(AwkOperator.DEC)) {
			t = rd.nextToken();
			return new AwkDeclementer(field(rd), true);
		} else {
			e = field(rd);
			if((t = rd.getToken()).equals(AwkOperator.INC)) {
				t = rd.nextToken();
				return new AwkInclementer(e, false);
			} else if(t.equals(AwkOperator.DEC)) {
				t = rd.nextToken();
				return new AwkDeclementer(e, false);
			} else {
				return e;
			}
		}
	}

	static AwkExpression pow(AwkLexer rd) throws IOException {
		AwkExpression e;

		e = incdec(rd);
		if(rd.getToken().equals(AwkOperator.POW)) {
			rd.nextToken();
			return new AwkPowerOp(e, pow(rd));
		} else {
			return e;
		}
	}

	static AwkExpression unaries(AwkLexer rd) throws IOException {
		AwkToken t = rd.getToken();

		if(t.equals(AwkOperator.ADD)) {
			t = rd.nextToken();
			return pow(rd);
		} else if(t.equals(AwkOperator.SUB)) {
			t = rd.nextToken();
			return new AwkNegater(pow(rd));
		} else if(t.equals(AwkOperator.L_NOT)) {
			t = rd.nextToken();
			return new AwkLogicalNotOp(pow(rd));
		} else {
			return pow(rd);
		}
	}

	static AwkExpression factor(AwkLexer rd) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		List<AwkToken> m = new ArrayList<AwkToken>();
		AwkExpression e;
		AwkToken t;

		l.add(unaries(rd));
		m.add(null);
		while((t = rd.getToken()).equals(AwkOperator.MUL) ||
				t.equals(AwkOperator.DIV) ||
				t.equals(AwkOperator.MOD)) {
			m.add(t);  rd.nextToken();
			l.add(unaries(rd));
		}
		e = l.get(0);
		for(int i = 1; i < l.size(); i++) {
			if(m.get(i).equals(AwkOperator.MUL)) {
				e = new AwkMultiplier(e, l.get(i));
			} else if(m.get(i).equals(AwkOperator.DIV)) {
				e = new AwkDivider(e, l.get(i));
			} else if(m.get(i).equals(AwkOperator.MOD)) {
				e = new AwkRemainderOp(e, l.get(i));
			}
		}
		return e;
	}

	static AwkExpression term(AwkLexer rd) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		List<AwkToken> m = new ArrayList<AwkToken>();
		AwkExpression e;
		AwkToken t;

		l.add(factor(rd));
		m.add(null);
		while((t = rd.getToken()).equals(AwkOperator.ADD) ||
				t.equals(AwkOperator.SUB)) {
			m.add(t);  rd.nextToken();
			l.add(factor(rd));
		}
		e = l.get(0);
		for(int i = 1; i < l.size(); i++) {
			if(m.get(i).equals(AwkOperator.ADD)) {
				e = new AwkAdder(e, l.get(i));
			} else if(m.get(i).equals(AwkOperator.SUB)) {
				e = new AwkSubtracter(e, l.get(i));
			}
		}
		return e;
	}

	static AwkExpression concat(AwkLexer rd) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		AwkExpression e;

		l.add(term(rd));
		while(!(rd.getToken() instanceof AwkOperator || rd.isEos()) ||
				rd.getToken().equals(AwkOperator.FIELD) ||
				rd.getToken().equals(AwkOperator.L_NOT)) {
			l.add(term(rd));
		}
		e = l.get(0);
		for(int i = 1; i < l.size(); i++) {
			e = new AwkConcatenator(e, l.get(i));
		}
		return e;
	}

	static AwkExpression relop(AwkLexer rd) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		List<AwkRelop.Operator> m = new ArrayList<AwkRelop.Operator>();
		AwkExpression e;
		AwkToken t;

		l.add(concat(rd));
		m.add(null);
		while((t = rd.getToken()) instanceof AwkRelop) {
			m.add(t.getRelation());  rd.nextToken();
			l.add(concat(rd));
		}
		e = l.get(0);
		for(int i = 1; i < l.size(); i++) {
			e = new AwkRelationOp(e, l.get(i), m.get(i));
		}
		return e;
	}

	static AwkExpression matchop(AwkLexer rd) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		List<AwkToken> m = new ArrayList<AwkToken>();
		AwkExpression e;
		AwkToken t;

		l.add(relop(rd));
		m.add(null);
		while((t = rd.getToken()).equals(AwkOperator.MATCH) ||
				t.equals(AwkOperator.NMATCH)) {
			m.add(t);  rd.nextToken();
			l.add(relop(rd));
		}
		e = l.get(0);
		for(int i = 1; i < l.size(); i++) {
			if(m.get(i).equals(AwkOperator.MATCH)) {
				e = new AwkMatcher(e, l.get(i));
			} else if(m.get(i).equals(AwkOperator.NMATCH)) {
				e = new AwkNotMatcher(e, l.get(i));
			}
		}
		return e;
	}

	static AwkExpression pin(AwkLexer rd) throws IOException {
		AwkExpression e;

		e = matchop(rd);
		if(rd.getToken().equals(AwkOperator.IN)) {
			rd.nextToken();
			return new AwkInOp(e, matchop(rd));
		} else {
			return e;
		}
	}

	static AwkExpression logand(AwkLexer rd) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		AwkExpression e;

		l.add(pin(rd));
		while(rd.getToken().equals(AwkOperator.L_AND)) {
			rd.nextToken();  l.add(pin(rd));
		}
		e = l.get(0);
		for(int i = 1; i < l.size(); i++) {
			e = new AwkLogicalAndOp(e, l.get(i));
		}
		return e;
	}

	static AwkExpression logor(AwkLexer rd) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		AwkExpression e;

		l.add(logand(rd));
		while(rd.getToken().equals(AwkOperator.L_OR)) {
			rd.nextToken();  l.add(logand(rd));
		}
		e = l.get(0);
		for(int i = 1; i < l.size(); i++) {
			e = new AwkLogicalOrOp(e, l.get(i));
		}
		return e;
	}

	static AwkExpression cond(AwkLexer rd) throws IOException {
		AwkExpression e, f, g;

		e = logor(rd);
		if(rd.getToken().equals(AwkOperator.TRI1)) {
			rd.nextToken();
			f = parseExpression(rd);
			rd.eatToken(AwkOperator.TRI2);
			g = parseExpression(rd);
			return new AwkConditionOp(e, f, g);
		} else {
			return e;
		}
	}

	static AwkExpression assignop(AwkLexer rd) throws IOException {
		AwkExpression e, f;
		AwkToken t;

		e = cond(rd);
		if((t = rd.getToken()).equals(AwkAssignop.ASSIGN)) {
			rd.nextToken();
			return new AwkAssigner(e, assignop(rd), null);
		} else if(t.equals(AwkAssignop.A_ADD)) {
			rd.nextToken();
			f = assignop(rd);
			return new AwkAssigner(e, f, new AwkAdder(e, f));
		} else if(t.equals(AwkAssignop.A_SUB)) {
			rd.nextToken();
			f = assignop(rd);
			return new AwkAssigner(e, f, new AwkSubtracter(e, f));
		} else if(t.equals(AwkAssignop.A_MUL)) {
			rd.nextToken();
			f = assignop(rd);
			return new AwkAssigner(e, f, new AwkMultiplier(e, f));
		} else if(t.equals(AwkAssignop.A_DIV)) {
			rd.nextToken();
			f = assignop(rd);
			return new AwkAssigner(e, f, new AwkDivider(e, f));
		} else if(t.equals(AwkAssignop.A_MOD)) {
			rd.nextToken();
			f = assignop(rd);
			return new AwkAssigner(e, f, new AwkRemainderOp(e, f));
		} else if(t.equals(AwkAssignop.A_POW)) {
			rd.nextToken();
			f = assignop(rd);
			return new AwkAssigner(e, f, new AwkPowerOp(e, f));
		} else {
			return e;
		}
	}

	static AwkExpression commaop(AwkLexer rd) throws IOException {
		AwkExpression e;

		e = assignop(rd);
		if(rd.getToken().equals(AwkOperator.COMMA)) {
			rd.nextToken();
			return new AwkCommaOp(e, commaop(rd));
		} else {
			return e;
		}
	}

	/**
	 * awkium式をコンパイルします。
	 * 
	 * @param rd lexer
	 * @return 式の中間表現
	 * @throws IOException
	 */
	public static AwkExpression parseExpression(
			AwkLexer rd) throws IOException {
		return commaop(rd);
	}

	private static void checkEos(AwkLexer rd) throws IOException {
		if(!rd.eatEos()) {
			throw new AwkSyntaxException(
					rd.getLineNumber(),
					"end of statement", rd.getToken());
		}
	}

	static AwkExpression stmt(AwkLexer rd) throws IOException {
		AwkExpression e;
		AwkToken t;
		String v = null;

		if((t = rd.getToken()).equals(AwkReserved.BREAK)) {
			rd.nextToken();
			checkEos(rd);
			return new AwkBreak();
		} else if(t.equals(AwkReserved.CONT)) {
			rd.nextToken();
			checkEos(rd);
			return new AwkContinue();
		} else if(t.equals(AwkReserved.DELETE)) {
			rd.nextToken();
			e = parseExpression(rd);
			if(!(e instanceof AwkArrayReferrer)) {
				throw new AwkSyntaxException(
						rd.getLineNumber(), "array[index] required");
			}
			checkEos(rd);
			return new AwkDelete(
					((AwkArrayReferrer)e).getArray(),
					((AwkArrayReferrer)e).getIndex());
		} else if(t.equals(AwkReserved.NEXT)) {
			rd.nextToken();
			checkEos(rd);
			return new AwkNext();
		} else if(t.equals(AwkReserved.EXIT)) {
			rd.nextToken();
			e = rd.isEos() ?
					AwkLiteralInteger.FALSE : parseExpression(rd);
			checkEos(rd);
			return new AwkExit(e);
		} else if(t.equals(AwkReserved.RETURN)) {
			rd.nextToken();
			e = parseExpression(rd);
			checkEos(rd);
			return new AwkReturn(e);
		} else if(t.equals(AwkReserved.CLOSE)) {
			rd.nextToken();
			e = parseExpression(rd);
			checkEos(rd);
			return new AwkClose(e);
		} else {
			e = parseExpression(rd);
			if(rd.getToken().equals(AwkReserved.PIPE)) {
				rd.nextToken();
				rd.eatToken(AwkReserved.GETLINE);
				if((t = rd.nextToken()) instanceof AwkSymbol) {
					v = t.getString();
					t = rd.nextToken();
				}
				return new AwkGetline(v, null, e);
			}
			checkEos(rd);
			return e;
		}
	}

	private static AwkExpression forsem(
			AwkLexer rd, AwkToken t) throws IOException {
		AwkExpression e;

		if(rd.getToken().equals(t)) {
			return AwkLiteralInteger.TRUE;
		} else {
			e = parseExpression(rd);
			return e;
		}
	}

	/**
	 * awkium文をコンパイルします。
	 * 
	 * @param rd lexer
	 * @return 文の中間表現
	 * @throws IOException
	 */
	public static AwkExpression parseStatement(
			AwkLexer rd) throws IOException {
		List<AwkExpression> l = new ArrayList<AwkExpression>();
		AwkExpression e, f, g, h;
		AwkLocation z;
		AwkToken t, s;

		if((t = rd.getToken()).equals(AwkReserved.BLOCK_B)) {
			rd.nextTokenBegin();
			while(!(t = rd.getToken()).equals(AwkReserved.BLOCK_E)) {
				if(t.equals(AwkReserved.ENDMARKER)) {
					throw new AwkSyntaxException(
							rd.getLineNumber(),
							AwkReserved.BLOCK_E, t);
				}
				l.add(parseStatement(rd));
			}
			rd.eatTokenEnd(AwkReserved.BLOCK_E);
			return new AwkSequence(l);
		} else if(t.equals(AwkReserved.IF)) {
			rd.nextToken();
			rd.eatToken(AwkOperator.LPAREN);
			e = parseExpression(rd);
			rd.eatToken(AwkOperator.RPAREN);
			f = parseStatement(rd);
			if(rd.getToken().equals(AwkReserved.ELSE)) {
				rd.nextToken();
				g = parseStatement(rd);
				return new AwkIf(e, f, g);
			} else {
				return new AwkIf(e, f, null);
			}
		} else if(t.equals(AwkReserved.WHILE)) {
			rd.nextToken();
			rd.eatToken(AwkOperator.LPAREN);
			e = parseExpression(rd);
			rd.eatToken(AwkOperator.RPAREN);
			f = parseStatement(rd);
			return new AwkWhile(e, f);
		} else if(t.equals(AwkReserved.DO)) {
			if(!(t = rd.nextToken()).equals(AwkReserved.BLOCK_B)) {
				throw new AwkSyntaxException(
						rd.getLineNumber(), AwkReserved.BLOCK_B, t);
			}
			e = parseStatement(rd);
			rd.eatToken(AwkReserved.WHILE);
			rd.eatToken(AwkOperator.LPAREN);
			f = parseExpression(rd);
			rd.eatToken(AwkOperator.RPAREN);
			checkEos(rd);
			return new AwkDoWhile(f, e);
		} else if(t.equals(AwkReserved.FOR)) {
			s = rd.nextToken();
			rd.eatToken(AwkOperator.LPAREN);
			e = rd.getToken().equals(AwkReserved.SEMICL) ?
					AwkLiteralInteger.TRUE : parseExpression(rd);
			if((t = rd.getToken()).equals(AwkReserved.SEMICL)) {
				rd.nextToken();
				f = forsem(rd, AwkReserved.SEMICL);  rd.nextToken();
				g = forsem(rd, AwkOperator.RPAREN);  rd.nextToken();
				h = parseStatement(rd);
				return new AwkFor(e, f, g, h);
			} else if(e instanceof AwkInOp) {
				f = ((AwkInOp)e).getArray();
				e = ((AwkInOp)e).getElement();
				rd.eatToken(AwkOperator.RPAREN);
				h = parseStatement(rd);

				if(!(e instanceof AwkReferVariable)) {
					throw new AwkSyntaxException(
							rd.getLineNumber(), "symbol", s);
				}
				z = ((AwkReferVariable)e).getLocation();
				if(!z.isSimpleName()) {
					throw new AwkSyntaxException(
							rd.getLineNumber(),
							"namespace is not allowed");
				}
				return new AwkForIn(f, h, z.getName());
			} else {
				throw new AwkSyntaxException(
						rd.getLineNumber(), ";/in", t);
			}
		} else {
			return stmt(rd);
		}
	}

	static AwkLocation loc1(AwkLexer rd) throws IOException {
		List<String> l = new ArrayList<String>();
		AwkToken t = AwkOperator.NAME, f, g;
		boolean rt;

		g = rd.getToken();
		if(rt = g.equals(AwkOperator.NAME))  rd.nextToken();
		while(t.equals(AwkOperator.NAME)) {
			if(rd.getToken().equals(AwkOperator.NAME))  rd.nextToken();
			if(!((f = rd.getToken()) instanceof AwkSymbol)) {
				throw new AwkSyntaxException(
						rd.getLineNumber(), "symbol", f);
			}
			l.add(f.getString());
			t = rd.nextToken();
		}
		return new AwkLocation(rt, l);
	}

	static AwkFunctionPrototype funcp(AwkLexer rd) throws IOException {
		AwkExpression e;
		List<String> l = new ArrayList<String>();
		AwkLocation lc;
		AwkToken t;
		boolean fi = true;

		lc = loc1(rd);
		rd.eatToken(AwkOperator.LPAREN);
		while(!(t = rd.getToken()).equals(AwkOperator.RPAREN)) {
			if(!fi)  rd.eatToken(AwkOperator.COMMA);
			if((t = rd.getToken()) instanceof AwkSymbol) {
				l.add(t.getString());  rd.nextToken();
				fi = false;
			} else {
				throw new AwkSyntaxException(
						rd.getLineNumber(), "symbol", t);
			}
		}

		rd.nextToken();
		if(!rd.getToken().equals(AwkReserved.BLOCK_B)) {
			throw new AwkSyntaxException(
					rd.getLineNumber(), AwkReserved.BLOCK_B, t);
		}
		e = parseStatement(rd);
		return new AwkFunctionPrototype(lc, e, l);
	}

	static AwkExecutable actionp(AwkNamespace ns,
			AwkLexer rd) throws IOException {
		AwkFunctionPrototype f;
		AwkExpression e = null;
		AwkPattern p;
		AwkToken t;
		boolean cl;

		if((t = rd.getToken()).equals(AwkReserved.BLOCK_B)) {
			e = parseStatement(rd);
			rd.eatTokenOpt(AwkReserved.SEMICL);
			return new AwkAction(null, e);
		} else if(t.equals(AwkReserved.FUNC)) {
			if((t = rd.nextToken()).equals(AwkOperator.FIELD)) {
				// function$ { ... } -> closure
				cl = true;  rd.nextToken();
			} else {
				cl = false;
			}
			f = funcp(rd);
			f.defun(ns, cl);
			rd.eatTokenOpt(AwkReserved.SEMICL);
			return null;
		} else {
			p = parsePattern(rd);
			if(rd.getToken().equals(AwkReserved.BLOCK_B)) {
				e = parseStatement(rd);
			}
			rd.eatTokenOpt(AwkReserved.SEMICL);
			return new AwkAction(p, e);
		}
	}

	/**
	 * awkiumプログラムをコンパイルします。
	 * 
	 * @param ns 名前空間
	 * @param rd lexer
	 * @return プログラムの中間表現
	 * @throws IOException
	 */
	public static AwkProgram parse(AwkNamespace ns,
			AwkLexer rd) throws IOException {
		List<AwkExecutable> l = new ArrayList<AwkExecutable>();
		AwkExecutable e;

		while(!rd.getToken().equals(AwkReserved.ENDMARKER)) {
			if((e = actionp(ns, rd)) != null)  l.add(e);
		}
		return new AwkProgram(l);
	}

}
