Малиновое автоматное решение с 5 состояниями:
ждать A ,
видел A ,
видел B ,
видел C и
видел ДД .
Анализ выполняется полностью одним способом. Существует один current узел, который является последним узлом, кроме NN. Узел имеет родительский узел, кроме корневого. В состоянии наблюдается (0) , узел current представляет (0) (например, в состоянии видно C , current может быть C1 в примере выше). Наибольшее беспокойство находится в состоянии , видимом DD , которое имеет самые исходящие края (B, C, DD и NN).
public final class Parser {
private final static class Token { /* represents A1 etc. */ }
public final static class Node implements Iterable<Node> {
/* One Token + Node children, knows its parent */
}
private enum State { ExpectA, SeenA, SeenB, SeenC, SeenDD, }
public Node parse(String text) {
return parse(Token.parseStream(text));
}
private Node parse(Iterable<Token> tokens) {
State currentState = State.ExpectA;
Node current = null, root = null;
while(there are tokens) {
Token t = iterator.next();
switch(currentState) {
/* do stuff for all states */
/* example snippet for SeenC */
case SeenC:
if(t.Prefix.equals("B")) {
current.PN.PN.AddChildNode(new Node(t, current.PN.PN));
currentState = State.SeenB;
} else if(t.Prefix.equals("C")) {
}
}
return root;
}
}
Меня не устраивают эти крушения поезда, чтобы подняться по иерархии, чтобы вставить Узел где-нибудь еще (current.PN.PN). В конце концов, явные классы состояний сделают приватный метод parse более читабельным. Затем решение становится более схожим с тем, которое предоставляет @AlekseyOtrubennikov. Возможно, прямой подход LL дает код, который более красив. Может быть, лучше просто перефразировать грамматику в BNF и делегировать создание парсера.
<Ч />
Простой анализатор LL, одно производственное правило:
// "B" ("NN" || C)*
private Node rule_2(TokenStream ts, Node parent) {
// Literal "B"
Node B = literal(ts, "B", parent);
if(B == null) {
// error
return null;
}
while(true) {
// check for "NN"
Node nnLit = literal(ts, "NN", B);
if(nnLit != null)
B.AddChildNode(nnLit);
// check for C
Node c = rule_3(ts, parent);
if(c != null)
B.AddChildNode(c);
// finished when both rules did not match anything
if(nnLit == null && c == null)
break;
}
return B;
}
TokenStream увеличивает Iterable<Token>, позволяя заглянуть в поток - LL(1), потому что парсер должен выбирать между буквальным NN или глубоким погружением в двух случаях (rule_2 является одним из них). Выглядит хорошо, однако, здесь отсутствуют некоторые функции C # ...