使用遞歸正則表達式在Java中Lexing

我正在使用Java解析文本。我定義以下的語法：使用遞歸正則表達式在Java中Lexing

Start := "(\\<)" 
Stop := "(\\>)" 
Var = "(\\w*)"; 
Cons = "([0-9]*)"; 

Type1 := Start ((Var | Cons) | TypeParent) (Type1 ((Var | Cons) | TypeParent))* Stop 
Type2 := Start ((Var | Cons) | TypeParent) (Type2 ((Var | Cons) | TypeParent))* Stop 

TypeParent := Type1 | Type2 

... 
etc

我想所有的正則表達式組合成一個單一的字符串模式搭配的一次。我的問題是當我開始使用Type1和Type2行中的遞歸語法元素時。我顯然不能將遞歸定義提供給Java中的模式 - 它只是一個帶正則表達符號的字符串。

我想什麼是我可以在某種程度上有一臺邏輯交換機是說，如果在此塊：除了2型

(Type2 ((Var | Cons) | TypeParent)

所有的模式相匹配，我可以捕獲所有其他羣體，但然後提取應該是Type2標記的字符串，然後將其遞歸地再次送入regexer。最後，我會坐下來的基本情況：

(Var | Cons) | TypeParent)

我知道這是不是正則表達式的意思做 - 這現在是一個上下文無關文法，因爲它是遞歸的（？）。但是，對於一個超級聰明的解析器，我想這種方法是可以破解的。

想法？

來源

2012-10-04 lollercoaster

你是對的。這不是正則表達式所要做的。當你引入遞歸時，你已經離開了正則表達式，DFA的土地，並且進入了上下文無關語言，DPDA，解析器的領域。你需要一個堆棧來處理遞歸。不，它不可破解。

關於此語法的解析器沒有什麼「超級聰明」。它比迄今爲止所做的簡單得多。

來源

2012-10-04 00:37:45 EJP

真的嗎？似乎我需要一個相當複雜的狀態機...... – lollercoaster

@lollercoaster一個帶有三個產品的語法並不複雜。你根本不需要狀態機。你可以做遞歸下降。我建議你停止猜測，並開始瞭解這些技術的真正含義。 – EJP

你是對的。遞歸下降很容易。用分流碼算法實現 - > RPN - > AST樹完成了這個訣竅。謝謝！ – lollercoaster

使用正確的工具更容易。嘗試CUP，ANTLR或JavaCC。這是一個ANTLR example。

來源

2012-10-04 00:37:57

+1。我會將Jparsec添加到列表中：http://jparsec.codehaus.org/ – leonbloy

JParsec看起來很酷。純Java，不需要語法模板。謝謝！ –

使用遞歸正則表達式在Java中Lexing

回答

相關問題