/*

Author: Ariel Ortiz

Complete C# simple expression language compiler.

LL(1) Grammar:

    (0) Prog ::= Expr "EOF"
    (1) Expr ::= Term ("+" Term)*
    (2) Term ::= PowTerm ("*" PowTerm)*
    (3) PowTerm ::= Fact ("**" PowTerm)?
    (4) Fact ::= "int" | "(" Expr ")"

*/

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Text.RegularExpressions;

public enum TokenCategory {
    INT, PLUS, TIMES, POW, OPEN_PAR, CLOSE_PAR, EOF, BAD_TOKEN
}

public class Token {
    public TokenCategory Category { get; }
    public String Lexeme { get; }

    public Token(TokenCategory category, String lexeme) {
        Category = category;
        Lexeme = lexeme;
    }

    public override String ToString() {
        return $"[{Category}, \"{Lexeme}\"]";
    }
}

public class Scanner {
    readonly String input;
    static readonly Regex regex = new Regex(
        @"(\d+)|([+])|([*][*])|([*])|([(])|([)])|(\s)|(.)");

    public Scanner(String input) {
        this.input = input;
    }

    public IEnumerable<Token> Scan() {
        var result = new LinkedList<Token>();

        foreach (Match m in regex.Matches(input)) {
            if (m.Groups[1].Success) {
                result.AddLast(new Token(TokenCategory.INT, m.Value));
            } else if (m.Groups[2].Success) {
                result.AddLast(new Token(TokenCategory.PLUS, m.Value));
            } else if (m.Groups[3].Success) {
                result.AddLast(new Token(TokenCategory.POW, m.Value));
            } else if (m.Groups[4].Success) {
                result.AddLast(new Token(TokenCategory.TIMES, m.Value));
            } else if (m.Groups[5].Success) {
                result.AddLast(new Token(TokenCategory.OPEN_PAR, m.Value));
            } else if (m.Groups[6].Success) {
                result.AddLast(new Token(TokenCategory.CLOSE_PAR, m.Value));
            } else if (m.Groups[7].Success) {
                // skip
            } else if (m.Groups[8].Success) {
                result.AddLast(new Token(TokenCategory.BAD_TOKEN, m.Value));
            }
        }
        result.AddLast(new Token(TokenCategory.EOF, null));

        return result;
    }
}

public class SyntaxError: Exception {}

public class SemanticError: Exception {}

public class Parser {
    IEnumerator<Token> tokenStream;

    public Parser(IEnumerator<Token> tokenStream) {
        this.tokenStream = tokenStream;
        this.tokenStream.MoveNext();
    }

    public TokenCategory Current {
        get {
            return tokenStream.Current.Category;
        }
    }

    public Token Expect(TokenCategory category) {
        if (Current == category) {
            Token current = tokenStream.Current;
            tokenStream.MoveNext();
            return current;
        } else {
            throw new SyntaxError();
        }
    }

    // (0)
    public Node Prog() {
        var result = Expr();
        Expect(TokenCategory.EOF);
        var newNode = new Prog();
        newNode.Add(result);
        return newNode;
    }

    // (1)
    public Node Expr() {
        var result = Term();
        while (Current == TokenCategory.PLUS) {
            var token = Expect(TokenCategory.PLUS);
            var newNode = new Plus();
            newNode.AnchorToken = token;
            newNode.Add(result);
            newNode.Add(Term());
            result = newNode;
        }
        return result;
    }

    // (2)
    public Node Term() {
        var result = PowTerm();
        while (Current == TokenCategory.TIMES) {
            var token = Expect(TokenCategory.TIMES);
            var newNode = new Times();
            newNode.AnchorToken = token;
            newNode.Add(result);
            newNode.Add(PowTerm());
            result = newNode;
        }
        return result;
    }

    // (3)
    public Node PowTerm() {
        var result = Fact();
        if (Current == TokenCategory.POW) {
            var token = Expect(TokenCategory.POW);
            var newNode = new Pow();
            newNode.AnchorToken = token;
            newNode.Add(result);
            newNode.Add(PowTerm());
            result = newNode;
        }
        return result;
    }

    // (4)
    public Node Fact() {
        switch (Current) {
            case TokenCategory.INT:
            {
                var token = Expect(TokenCategory.INT);
                var result = new Int();
                result.AnchorToken = token;
                return result;
            }
            case TokenCategory.OPEN_PAR:
            {
                Expect(TokenCategory.OPEN_PAR);
                var result = Expr();
                Expect(TokenCategory.CLOSE_PAR);
                return result;
            }
            default:
                throw new SyntaxError();
        }
    }
}

public class Node: IEnumerable<Node> {

    IList<Node> children = new List<Node>();

    public Node this[int index] {
        get {
            return children[index];
        }
    }

    public Token AnchorToken { get; set; }

    public void Add(Node node) {
        children.Add(node);
    }

    public IEnumerator<Node> GetEnumerator() {
        return children.GetEnumerator();
    }

    System.Collections.IEnumerator
    System.Collections.IEnumerable.GetEnumerator() {
        throw new NotImplementedException();
    }

    public override string ToString() {
        return $"{GetType().Name} {AnchorToken}";
    }

    public string ToStringTree() {
        var sb = new StringBuilder();
        TreeTraversal(this, "", sb);
        return sb.ToString();
    }

    static void TreeTraversal(Node node, string indent, StringBuilder sb) {
        sb.Append(indent);
        sb.Append(node);
        sb.Append('\n');
        foreach (var child in node.children) {
            TreeTraversal(child, indent + "  ", sb);
        }
    }
}

public class Prog: Node {}
public class Plus: Node {}
public class Times: Node {}
public class Pow: Node {}
public class Int: Node {}

public class SemanticVisitor {

    public void Visit(Prog node) {
        Visit((dynamic) node[0]);
    }

    public void Visit(Plus node) {
        Visit((dynamic) node[0]);
        Visit((dynamic) node[1]);
    }

    public void Visit(Times node) {
        Visit((dynamic) node[0]);
        Visit((dynamic) node[1]);
    }

    public void Visit(Pow node) {
        Visit((dynamic) node[0]);
        Visit((dynamic) node[1]);
    }

    public void Visit(Int node) {
        int result;
        if (!Int32.TryParse(node.AnchorToken.Lexeme, out result)) {
            throw new SemanticError();
        }
    }
}

public class WATVisitor {

    public String Visit(Prog node) {
        return
            "(module\n"
            + "  (import \"math\" \"pow\" (func $pow (param i32 i32) (result i32)))\n"
            + "  (func\n"
            + "    (export \"start\")\n"
            + "    (result i32)\n"
            + Visit((dynamic) node[0])
            + "    return\n"
            + "  )\n"
            + ")\n";
    }

    public String Visit(Plus node) {
        return Visit((dynamic) node[0])
            + Visit((dynamic) node[1])
            + "    i32.add\n";
    }

    public String Visit(Times node) {
        return Visit((dynamic) node[0])
            + Visit((dynamic) node[1])
            + "    i32.mul\n";
    }

    public String Visit(Pow node) {
        return Visit((dynamic) node[0])
            + Visit((dynamic) node[1])
            + "    call $pow\n";
    }

    public String Visit(Int node) {
        return $"    i32.const {node.AnchorToken.Lexeme}\n";
    }
}

public class Driver {
    public static void Main() {
        Console.Write("> ");
        var line = Console.ReadLine();
        var parser = new Parser(new Scanner(line).Scan().GetEnumerator());
        try {
            var ast = parser.Prog();
            new SemanticVisitor().Visit((dynamic) ast);
            File.WriteAllText(
                "output.wat",
                new WATVisitor().Visit((dynamic) ast));

        } catch (SyntaxError) {
            Console.WriteLine("Bad syntax!");
        } catch (SemanticError) {
            Console.WriteLine("Bad semantics!");
        }
    }
}