如何實現簡單的解析器樹？

我已發佈類似的問題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

如何實現簡單的解析器樹？

回答

相關問題