Created
February 16, 2018 02:37
-
-
Save vilaca/f8fff329a25e3f81847ec5e2371f233f to your computer and use it in GitHub Desktop.
lispy parser
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package eu.vilaca.lispy; | |
import java.util.AbstractList; | |
import java.util.ArrayDeque; | |
import java.util.ArrayList; | |
import java.util.Deque; | |
import java.util.List; | |
public class Parser { | |
private static final Parser PARSER = new Parser(); | |
public static void main(String[] args) { | |
final Deque<Token> tokens = PARSER | |
.tokenizer("(add (2) (add (4) (sub (0) (100))) (94) (200) (sub (200) (1000)) sub (1800))"); | |
final Deque<Token> tokens2 = new ArrayDeque<>(tokens.size()); | |
// reverse stack | |
for (Token t : tokens) { | |
tokens2.push(t); | |
} | |
final Node nodes = PARSER.parser(tokens2); | |
Node n = PARSER.transformer(nodes); | |
System.out.println(((NumberNode) n).get()); | |
} | |
private Node transformer(Node node) { | |
if (!(node instanceof CallNode)) { | |
throw new RuntimeException("unexpected type"); | |
} | |
final List<Node> inner = ((CallNode) node).get(); | |
StringNode op = null; | |
NumberNode accum = null; | |
for (int i = 0; i < inner.size(); i++) { | |
Node n = inner.get(i); | |
if (n instanceof StringNode) { | |
op = (StringNode) n; | |
continue; | |
} | |
if (n instanceof CallNode) { | |
n = transformer(n); | |
} | |
if (n instanceof NumberNode) { | |
if (accum == null) { | |
accum = (NumberNode) n; | |
continue; | |
} else { | |
if (op == null) { | |
throw new RuntimeException("Wrong operation."); | |
} | |
switch (op.get()) { | |
case "add": | |
final int left = Integer.parseInt(accum.get()); | |
final int right = Integer.parseInt(((NumberNode) n) | |
.get()); | |
accum = new NumberNode(String.valueOf(left + right)); | |
System.out.println(left + "+" + right + "=" | |
+ accum.get()); | |
break; | |
case "sub": | |
final int sleft = Integer.parseInt(accum.get()); | |
final int sright = Integer.parseInt(((NumberNode) n) | |
.get()); | |
accum = new NumberNode(String.valueOf(sleft - sright)); | |
System.out.println(sleft + "+" + sright + "=" | |
+ accum.get()); | |
break; | |
default: | |
throw new RuntimeException("Wrong operation."); | |
} | |
continue; | |
} | |
} | |
throw new RuntimeException("Nothing to do."); | |
} | |
return accum; | |
} | |
private interface Node { | |
}; | |
private static class NumberNode implements Node { | |
final String inner; | |
NumberNode(String v) { | |
inner = v; | |
} | |
String get() { | |
return inner; | |
} | |
}; | |
private static class StringNode implements Node { | |
final String inner; | |
StringNode(String v) { | |
inner = v; | |
} | |
String get() { | |
return inner; | |
} | |
}; | |
private static class CallNode implements Node { | |
final List<Node> inner = new ArrayList<>(); | |
List<Node> get() { | |
return inner; | |
} | |
}; | |
private Node parser(Deque<Token> tokens) { | |
System.out.print("\n("); | |
Token token = tokens.pop(); | |
if (token instanceof NumberToken) { | |
System.out.print(((NumberToken) token).value()); | |
System.out.println(")"); | |
return new NumberNode(((NumberToken) token).value()); | |
} | |
if (token instanceof StringToken) { | |
System.out.print(((StringToken) token).value()); | |
System.out.println(")"); | |
return new StringNode(((StringToken) token).value()); | |
} | |
if (token instanceof Paren && ((Paren) token) == Paren.OPEN) { | |
CallNode ct = new CallNode(); | |
token = tokens.peek(); | |
while (!(token instanceof Paren && ((Paren) token) == Paren.CLOSED)) { | |
Node w = parser(tokens); | |
ct.get().add(w); | |
token = tokens.peek(); | |
} | |
tokens.pop(); | |
System.out.println(")"); | |
return ct; | |
} | |
throw new RuntimeException("Can't parse."); | |
} | |
private interface Token { | |
}; | |
private enum Paren implements Token { | |
OPEN, CLOSED; | |
} | |
private static abstract class ContainerToken implements Token { | |
private final StringBuilder value = new StringBuilder(); | |
public ContainerToken(char c) { | |
append(c); | |
} | |
void append(char c) { | |
value.append(c); | |
} | |
public String value() { | |
return value.toString(); | |
} | |
}; | |
private static class StringToken extends ContainerToken { | |
public StringToken(char c) { | |
super(c); | |
} | |
}; | |
private static class NumberToken extends ContainerToken { | |
public NumberToken(char c) { | |
super(c); | |
} | |
}; | |
private static class Matcher { | |
private final List<Character> lst; | |
Matcher(final String pattern) { | |
lst = new AbstractList<Character>() { | |
public int size() { | |
return pattern.length(); | |
} | |
public Character get(int index) { | |
return pattern.charAt(index); | |
} | |
}; | |
} | |
public boolean contains(char c) { | |
return lst.contains(c); | |
} | |
}; | |
private static final Matcher WHITESPACE = new Matcher(" \t\n\r"); | |
private static final Matcher NUMBER = new Matcher("0123456789"); | |
private static final Matcher WORD = new Matcher( | |
"abcdefghijklmnopqrstuvxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"); | |
private Deque<Token> tokenizer(String str) { | |
final Deque<Token> tokens = new ArrayDeque<>(); | |
for (char c : str.toCharArray()) { | |
if (c == '(') { | |
tokens.push(Paren.OPEN); | |
continue; | |
} | |
if (c == ')') { | |
tokens.push(Paren.CLOSED); | |
continue; | |
} | |
if (WHITESPACE.contains(c)) { | |
continue; | |
} | |
if (NUMBER.contains(c)) { | |
Token last = tokens.peek(); | |
if (last instanceof NumberToken) { | |
((NumberToken) last).append(c); | |
} else { | |
tokens.push(new NumberToken(c)); | |
} | |
continue; | |
} | |
if (WORD.contains(c)) { | |
Token last = tokens.peek(); | |
if (last instanceof StringToken) { | |
((StringToken) last).append(c); | |
} else { | |
tokens.push(new StringToken(c)); | |
} | |
continue; | |
} | |
throw new RuntimeException("I don't know what this is."); | |
} | |
return tokens; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment