2013-06-27 78 views
1

假設存在這樣的格式的字符串:解析字符串轉換成類層次結構

"2 + 3 * (5 + 2) * -1 - 2" 

(只是一個例子,它並沒有成爲一個算術語法)

要解析爲基於類的層次結構

add(2,sub(mul(mul(3,add(5,2)),-1),2)) 

我正在尋找一種有效的方法來完成此分析。目前的問題是我不確定這種解析是什麼。因此我無法找到正確的來源/參考。有什麼建議麼?

+0

來源/參考從這裏開始:https://en.wikipedia.org/wiki/Parsing#Overview_of_process – georg

+0

你可能也看看http://en.wikipedia.org/wiki/Shunting-yard_algorithm – kindall

回答

1

如果您想爲自定義語言(通常稱爲DSL域特定語言)構建高效的解析器,那麼您需要查看解析器生成器。這些典型的工作如下:

  • 您需要爲您的語言以特定格式(語法代表您的語言的規則)放在一起的語法。
  • 解析器生成器提供了一個工具,它將讀取您的語法並生成您​​需要解析語句的解析器代碼的詞法分析器代碼。
  • 生成的詞法分析程序將能夠讀取一個字符串,並且如果該字符串符合您指定的語法,則構造一個AST(抽象語法樹),它表示所分析的邏輯結構。
  • 然後,您通常會將詞法分析器&解析器集成到您自己的工具中,該工具實際上會對生成的AST執行某些操作。

這裏有一個很好的參考parser generators in Python。我有經驗的唯一一個是ANTLR,我可以推薦它是非常有能力和強大的。

值得注意的是,如果您沒有這方面的經驗,構建語言語法和生成解析器可能是一個相當費力的過程,而且對於非常簡單的示例(如提供過濾器的示例)也是如此。然而,如果你想爲一個非平凡的語言構建一個高效的解析器,那麼解析器生成器可能是一條可行的路。

+0

謝謝!我會研究它。 – Erwin

2

如果這是一個合法的Python表達式可以使用ast module,具體ast.parse

>>> import ast 
>>> s = ast.parse("2 + 3 * (5 + 2) * -1 - 2") 
>>> ast.dump(s) 
'Module(body=[Expr(value=BinOp(left=BinOp(left=Num(n=2), op=Add(), right=BinOp(l 
eft=BinOp(left=Num(n=3), op=Mult(), right=BinOp(left=Num(n=5), op=Add(), right=N 
um(n=2))), op=Mult(), right=Num(n=-1))), op=Sub(), right=Num(n=2)))])' 

使用ast.Visitor您可以通過此樹行走。