Как реализовать простое дерево парсера? - PullRequest
Новая
       29

Как реализовать простое дерево парсера?

0 голосов
/ 03 сентября 2011

Я отправил подобный вопрос здесь , но он был закрыт, потому что я не объяснил себя должным образом.Я попытаюсь объяснить мою проблему еще раз.

Мне удалось написать LexicalAnalyzer, который будет разбивать следующее на "public", "class", "A", "{", ..., "if", "(", ..., "}" 

string seq = "public class A " +
             "{ " +
                  "public A() " +
                  "{ " +
                       "if(1==2) " +
                       "{ " +
                       "} " +
                       "else " +
                       "{ " +
                       "} " +
                 "} " +
             "} "

Теперь мне нужно разобрать его в дереве. Пока я читаю, лучше построить синтаксический анализатор так, как он будет принимать правила. Тем временемМне нужно написать правила для оператора «if», которые будут переданы в синтаксический анализатор, а последний будет строить дерево разбора. В будущем я добавлю правила для «class» и др.

Для разбора Iзначит, в конце концов я получу похожее дерево как здесь справа

Мой вопрос заключается в том, как реализовать правила и синтаксический анализатор? Можете ли вы указать мне или привести простой пример, пожалуйста?

Я прочитал несколько постов, но не нашел чего-то, что помогло бы мне сделать то, что мне нужно.

PS Если все еще неясно, пожалуйста, не закрывайте пост, но скажите мнеи я его поменяю.

Спасибо

1 Ответ

1 голос
/ 27 июня 2012

С каких это пор RTFM является ответом? В любом случае. То, что вы пытаетесь сделать, совсем не просто, поскольку Java не зависит от контекста (тип 2). Попробуйте для начала написать синтаксический анализатор для языка типа 3 ( Иерархия Хомского ). Но я все равно попытаюсь объяснить вам, что вам нужно делать.

Вы должны будете определить правила для Java, которые выглядят так (в моем примере я определю функцию в классе java, где строчные буквы являются терминалами, а заглавные буквы не являются терминалами). Терминалы не могут быть получены дальше, в то время как нетерминалы могут.

X -> Y означает, что X наследуется от Y. X -> Y | Z означает, что X выводится из Y или Z.

f - любое имя. Это тип, это не было бы терминалом, если бы я попытался пройти весь путь, но так как я определяю типы как не подлежащие объявлению, чтобы сделать мою жизнь менее болезненной, это терминал. '(', ')', '{', '}', ',' и '' являются терминалами. Eps - это Epsilon и ничего не значит. 

S -> K t f(T) { N }
T -> t f | t f , T
F -> F, f | f
K -> k K | k
N -> L N | L
L -> f(F);

С этим я мог бы разобрать 

final boolean equals(Object obj) {
    compare(this, obj);
    compare(obj, this);
}

Что приведет к: 

S -> K t f(T) { N } 
     with K -> k
  -> k t f(T) { N }
     with T -> t f
  -> k t f(t f) { N }
     with N -> L N
  -> k t f(t f) { L N }
     with L -> f(F);
  -> k t f(t f) { f(F); N }
     with F -> f, F
  -> k t f(t f) { f(f, F); N }
     with F -> f
  -> k t f(t f) { f(f, f); N }
     with N -> L
  -> k t f(t f) { f(f, f); L }
     with L -> f(F)
  -> k t f(t f) { f(f, f); f(F) }
     ...
  -> k t f(t f) { f(f, f); f(f, f); }

  -> k (=final) t(=boolean) f(=equals) (t(=Object) f(=obj)) { ... }

Что доказывает, что S определяет мою простую Java (ну, это не так, но, по крайней мере, я привел пример). Итак, следующее, что нам нужно сделать, - это выяснить, как получить синтаксическое дерево из этих правил.

К счастью, это самая простая часть, потому что все, что вам нужно сделать, это изменить строки на дерево. Таким образом, у S есть дети K t f (T) {N}. K имеет детей K и k ... Прописные буквы означают, что у Node есть дети, а строчные - нет.

Последняя проблема, вы начинаете не с S, а с кода, который уже пишется. Что оставляет вас с 

K t f(T) { N } -> S
t f            -> T
t f , T        -> T
F, f           -> F
f              -> F
k K            -> K
k              -> K
L N            -> N
N              -> L
f(F);          -> L

Разбор в обратном направлении будет выглядеть так: 

final boolean equals(Object obj) {
   compare(this, obj);
   compare(obj, this);
}
final   -> k
boolean -> t
equals  -> f
Object  -> t
obj     -> f
compare -> f
this    -> f

k t f(t f) { f(f, f); f(f,f); }
with k -> K
K t f(t f) ...
with t f -> T
K t f(T) ...
...

Что бы построить дерево снизу.

...