如何实现简单的解析器树？

我已发布类似的问题here，但因为没有正确解释我自己而被关闭。我会试着再次解释我的问题。如何实现简单的解析器树？

我成功地写了LexicalAnalyzer，将以下标记为“public”，“class”，“A”，“{”，...，“if”，“（”，...，“}”

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

现在，我需要将其解析到树上。当我读到，这是更好地构建，将采取规则的方式解析器。同时我需要编写规则“if”语句”，这将是传递给解析器和最后将建立解析树。今后，我会添加规则“类”等。

要分析我的意思是，最终我会得到类似的树like here in the right

我的问题是如何实现规则和解析器？你能指导我或举个简单的例子吗？

我读过一些文章，但是我没有找到能够帮助我做我需要的东西。

P.S.如果还不清楚，请不要关闭帖子，但告诉我，我会改变它。

谢谢

来源

2011-09-03 theateist

[编译器：原理，技术和工具]（http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools） – jason

作为一个方面说明，如果你想有一个字符串看起来适当在代码中构造，您可以使用逐字字符串文字。基本上，把'@'放在'''之前，然后你可以编写一个包含新行的字符串。 – svick

http://stackoverflow.com/questions/1669/learning-to-write-a-compiler –

既然何时是RTFM的答案？无论如何。你所要做的并不容易，因为Java是无上下文的（类型2）。尝试为初学者编写3型语言（Chomsky Hierarchy）的语法分析器。但我会尽力向你解释你需要做什么。

您将不得不为Java定义规则（在我的示例中，我将在java类中定义一个函数，其中小写字母为终端，大写字母为非终端）。终端不能继续得到，而非终端可以。

X - > Y表示X导出到Y X - > Y | Z表示X派生到Y或Z.

f是任何名称。 t是一个类型，如果我试图一路走下去，这不会是一个终端，但是由于我将类型定义为非可声明的，以使我的生活减轻痛苦，所以它是一个终端。 '（'，'）'，'{'，'}'，'，'和''是终端。 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定义我的simplyfied的Java（当然不是，但至少我举了一个例子）。所以接下来我们要做的就是弄清楚如何从这些规则中得到一个语法树。

值得庆幸的是，这是比较容易的部分，因为所有你需要做的是改变线路是一棵树。所以S有孩子K t f（T）{N}。 K有孩子K和K ...大写意味着一个节点有孩子，小写则表示它没有孩子。

最后一个问题，你不是以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) ... 
...

这会从楼下搭建的树。

来源

2012-06-27 10:04:21

如何实现简单的解析器树？

回答

相关问题