歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Unix知識 >> 關於Unix

可愛的Python:了解DParserforPython

首先初步了解 DParser 這一由 J. Plevyak 編寫的簡單而強大的解析工具。然後了解用於 Python 的 DParser,它為 Python 程序員 提供了一個訪問 DParser 的無縫接口,並看看它與上一期中介紹的解析器的比較。語法規則以類似於 Spark 或 PLY 的方式通過 Python
  首先初步了解 DParser 這一由 J. Plevyak 編寫的簡單而強大的解析工具。然後了解用於 Python 的 DParser,它為 Python 程序員提供了一個訪問 DParser 的無縫接口,並看看它與上一期中介紹的解析器的比較。語法規則以類似於 Spark 或 PLY 的方式通過 Python 函數文檔字符串加入到 DParser 中。
  
  有很多可用的 Python 解析器程序庫。我已經在本專欄中討論過 mx.TextTools、SimpleParse 和 SPARK,並在我的書中介紹了 PLY(請參閱 參考資料,獲得這些文檔的鏈接)。無需考慮,我也知道有 PyGgy、Yapps、PLEX、PyLR、PyParsing 和 TPG,而且我還模糊地記得讀過半打其他解析器的聲明。用戶可能會對此門類感到失落,不是因為缺少高質量程序庫,而是太多了。
  
  DParser 與所有其他解析器的不同之處是什麼?是這樣,類似於 PLY 和 Spark,用於 Python 的 DParser 使用函數文檔字符串來表示其結果(productions)。這種風格使得您可以將動作代碼直接插入到一個結果中,以處理當一個特定的語法規則得到滿足時將發生的事件。與 PLY 或 Spark 相反,DParser 本身是用 C 編寫的,因而可能會比純粹的 Python 解析器快得多。用於 Python 的 DParser 是底層的 C 程序庫之外的一個非常精簡的包裝器(wrapper) —— 對 Python 的回調需要一些額外的時間,但是基本的解析是以 C 語言的速度來進行的。不過,就本文而言,我沒有嘗試進行任何具體的基准測試。所以,相對於其他解析器來說,DParser 到底有多快或多慢不是我所能直接評論的。
  
  就我自己而言,我仍是非常喜歡 SimpleParse 的方法。SimpleParse 是快速的 mx.TextTools 程序庫(也是用 C 所編寫的)的一個包裝器,可以將 EBNF 語法語言從 Python 代碼中完全分離出來。一般來說,使用 SimpleParse 就意味著在一個函數調用中生成一個解析樹,然後在分開的代碼中遍歷這個樹。對於特別大的被解析的文檔來說,這種兩步方法可能是低效的,但是我發現這樣更容易理解編寫的代碼。
  
  盡管如此,還是有很多讀者推薦說用於 Python DParaser 值得關注,雖然我更喜歡單獨的 EBNF 定義。順便提一句,如您將在示例中所看到的,DParser 不使用任何單獨的標記傳遞,而只是直接解析。您可以通過定義保留的 d_whitespace() 函數來控制空格的識別(它分離解析符號);這樣就使得您可以隨意使用標記。
  
  找到最長的結果
  作為用於 Python 的 DParser 程序的第一個示例,我創建了一個查找幾個模式的語法,這些模式依次為另一個的子結果。這個語法處理的問題類似於很多解析器遇到的“dangling else”問題。具體說,也就是您如何才能知道什麼時候停止查找更長的結果?(例如,“if”後是否跟有“else”?)我的語法會去分析的短語可能按次序包括有以“a”、“b”和“c” 結尾的單詞。所有沒有被包括進來的單詞只是短語的“head”或“tail”的部分。這需要一些例子來展示。首先,程序本身:
  
  清單 1. 解析器 abc.py
  
  #!/usr/bin/env python2.3
  "Identify sequence of a-, b-, c- words"
  #
  #-- The grammar
  def d_phrase(t, s):
    'phrase : words ( ABC | AB | A ) words'
    print "Head:", '.join(s[0])
    print t[1][0]+":", '.join(s[1])
    print "Tail:", '.join(s[2])
  def d_words(t):
    'words : word*'
  def d_word(t):
    'word : "[a-z]+" '
  def d_A(t):
    ''A : "a[a-z]*" ''
    return 'A'
  def d_AB(t):
    ''AB : A "b[a-z]*" ''
    return 'AB'
  def d_ABC(t):
    ''ABC : AB "c[a-z]*" ''
    return 'ABC'
  #
  #-- Parse STDIN
  from dparser import Parser
  from sys import argv, stdin
  phrase, arg = stdin.read(), argv[-1]
  Parser().parse(phrase,
          print_debug_info=(arg=='--debug'))
  
  讓我們給出一些短語來運行這個解析器,如下:
  
  清單 2. 簡單地解析短語
  
  $ echo -n "alpha" | ./abc.py
  Head:
  A: alpha
  Tail:
  echo -n "xavier alpha beta charlie will" | ./abc.py
  Head: xavier
  ABC: alpha beta charlie
  Tail: will
  $ echo -n "mable delta xavier bruce" | ./abc.py
  Traceback (most recent call last): [...]
  dparser.SyntaxError:
  syntax error, line:1
  mable delta xavier bruce[syntax error]
  
  顯然,到目前為止,一切都沒問題。我的語法當其條件允許時找到了一個 ABC,但是當只能找到 A 或者 AB 時,也能滿足於此。
  
  不過說實話,當遇到含糊的短語時,我的語法會有很多問題。在大部分情況下,當 DParser 不能確定如何解析一個短語時,它會陷入一個無限循環(可能是最壞的結果;至少回溯或者報告的錯誤可以告訴您哪裡出現了問題)。有時(至少在我的 Mac OSX 機器上),它會轉而生成一個“Bus error”。那些情形我哪個都不喜歡。
  
  處理含糊的短語
  由於所有的最終結果都有相同的優先級,所以解析器不能確定如何解析類似如下的內容:
  
  清單 3. 嘗試解析一個含糊的短語
  
  $ echo -n "alex bruce alice benny carl" | ./abc.py
  
  AB 在前然後是單詞?單詞在前然後是 ABC?對於那個問題來說,它是全部都是單詞嗎(包括五個單詞結果),它是不是應該引發一個 dparser.SyntaxError?我最後會得到一個“Bus error” 或停止了的任務,而不是一個解析。在先前的例子中,含糊的短語碰巧被解析出來的原因在於每個結果的急切性(eagerness);一旦找到一個 ABC,則先導和結尾單詞就都各就其位。
  
  實際上,在先前的語法可以生效的情況下,要確切地理解為什麼能夠生效很令人迷惑 —— 在某種程度上,比理解為什麼它有時不能生效更令人迷惑。
  
  讓我們假定我們希望解析一個短語,並當存在 ABC 結果時找它,即便在從左到右的遍歷過程中,有一些其他的結果(也就是 AB)得到了滿足。我可以通過提高 ABC 最終結果的優先級來完成:
  
  清單 4. abc2.py 中修訂的 d_ABC() 結果函數
  
  def d_ABC(t):
    'ABC : AB "c[a-z]*" $term 1'
    return 'ABC'
  
  如果沒有指定優先級,則結果的優先級是 0。否則,任何正整數或負整數都可以用來對結果排序。現在我們可以運行:
  
  清單 5. 成功地找到後面的 ABC
  
  $ echo -n "alex bruce alice benny carl" | ./abc2.py
  Head: alex bruce
  ABC: alice benny carl
  Tail:
  
  注意,在解析器尋找末尾的單詞之前,會嘗試(ABC|AB|A)系列中的全部可選項。所以這樣不需要任何優先級規范就可以成功。
  
  清單 6. A 與 AB 之間不存在含糊短語問題
  
  $ echo -n "alex alice benny" | ./abc.py  Head: alex
  AB: alice benny
  Tail:
  
  在處理含糊短語時 DParser 的行為中,我發現了一些難以解釋的異常現象。例如,添加一個絕對不是 A 的末尾單詞,解析器可以工作 —— 但 只能 在有調試信息的條件下運行!
  
  清單 7. 處理含糊短語時的不穩定行為
  
  $ echo -n "alex bruce alice benny carl dave" | ./abc.py
  [...process freezes...]
  $ echo -n "alex bruce alice benny carl dave" | ./abc.py --debug
  [...debugging trace of speculative and final productions...]
  Head: alex bruce
  ABC: alice benny carl
  Tail: dave
  
  abc2.py 中的優先級規范會完成任意一種情況下的解析。
  
  含糊短語的解析相當難以捉摸,難以確切理解。基本上,結果的生成是按遍歷的順序從左到右執行的,每一個結果都嘗試去從左到右獲取盡可能多的單詞。只有當向前查找過程中發生明顯錯誤時,才會進行回溯。總之,這只是大概。
  
  調試簡介
  DParser 可以顯示調試信息的選項,這是我所喜歡的它的一個方面。觀察這些信息並不是直觀地創建正確語法所必需的,但是至少可以通過它洞察當處理特定的短語時解析器所采取的動作。例如:
  
  清單 8. 展示對不確定結果的追蹤
  
  #------- Showing a trace of speculative productions
  $ echo -n "alex alice benny carl dave" | ./abc2.py --debug
          d_words ???:
            d_A ???:   alex
          d_word ???:   alex
          d_words ???:
         d_phrase ???:   alex
          d_words ???:   alex
            d_A ???:   alice
          d_word ???:   alice
          d_words ???:
          d_words ???:   alice
         d_phrase ???:   alex alice
         d_phrase ???:   alex alice
          d_words ???:   alex alice
          d_word ???:   benny
           d_AB ???:   alice benny
          d_words ???:   benny
          d_words ???:   alice benny
          d_words ???:
         d_phrase ???:   alex alice benny
         d_phrase ???:   alex alice benny
         d_phrase ???:   alex alice benny
          d_words ???:   alex alice benny
          d_word  :   alex
          d_words  :   alex
            d_A  :   alice
           d_AB  :   alice benny
           d_ABC ???:   alice benny carl
          d_words ???:
         d_phrase ???:   alex alice benny carl
           d_ABC  :   alice benny carl
          d_word ???:   dave
          d_words ???:   dave
         d_phrase ???:   alex alice benny carl dave
          d_word  :   dave
          d_words  :   dave
         d_phrase  :   alex alice benny carl dave
  Head: alex
  ABC: alice benny carl
  Tail: dave
  
  後面跟有問號的結果是推測性的嘗試;那些後面其實沒有最終的結果。與此相關, DParser 讓您有能力當結果成為推測的或者是最終解析時采取不同的動作。默認情況下,函數體中的動作只作用於最終解析。不過,您可以向結果指定兩個額外參數中的一個來處理推測性解析。(還有很多本文中沒有討論的選項參數。)
  
  清單 9. 推測性解析過程中的動作
  
  def d_prod1(t, spec_only):
    'prod1 : this that+ other?'
    print "Speculative parse of prod1"
  def d_prod2(t, spec):
    'prod2: spam* eggs toast'
    if spec:
      print "Speculative parse of prod2"
    else:
      print "Final parse of prod2"
  
  當然,通過指定 dparser.Parser.parse() 的 print_debug_info 參數,我的推測性解析所顯示的所有信息也都顯示出來(以稍微不同的格式)。不過您也可以決定采取其他動作 —— 比如觸發外部事件。
  
  深入探討優先級
  我承認,前面 ABC 結果所使用的指定優先級有些不太正統。但是假如是簡單含糊短語,則微調結束優先級是一個非常好的工具。讓我來給出另一個關於簡單含糊短語的語法:
  
  清單 10. 逐項的二義性語法,ibm.py
  
  def d_phrase(t, s):
    'phrase : word ( vowel | caps | threeletter ) word'
    print "Head:", '.join(s[0])
    print t[1][0]+":", '.join(s[1])
    print "Tail:", '.join(s[2])
  def d_word(t): 'word : "[A-Za-z]+" '
  def d_vowel(t):
    'vowel : "[AEIOUaeiou][A-Za-z]*"'
    return 'VOWEL'
  def d_caps(t):
    'caps : "[A-Z]+"'
    return 'CAPS'
  def d_threeletter(t):
    'threeletter : "[A-Za-z][A-Za-z][A-Za-z]"'
    return '3LETT'
  #-- Parse STDIN
  from dparser import Parser
  from sys import stdin
  Parser().parse(stdin.read())
  
  vowel、caps 和 threeletter 的結果不需要是確切的;它們全部都可以獲取彼此有重疊的單詞集合。例如:
  
  清單 11. 當 DParser 得體地檢測到含糊短語
  
  $ echo -n "Read IBM developerWorks" | ./ibm.py
  Traceback (most recent call last): [...]
  dparser.AmbiguityException: [...]
  
  當然,您可能幸運地使用了特定的短語:
  
  清單 12. 幸運地避免了含糊短語的解析
  
  $ echo -n "Read GNOSIS website" | ./ibm.py
  Head: Read
  CAPS: GNOSIS
  Tail: website
  
  不要滿足於祈禱好運,讓我們來顯式地指定結果之間的優先級:
  
  清單 13. 判定含糊的條件,ibm2.py
  
  def d_vowel(t):
    'vowel : "[AEIOUaeiou][A-Za-z]*" $term 3'
    return 'VOWEL'
  def d_caps(t):
    'caps : "[A-Z]+" $term 2'
    return 'CAPS'
  def d_threeletter(t):
    'threeletter : "[A-Za-z][A-Za-z][A-Za-z]" $term 1'
    return '3LETT'
  
  現在,每一個短語都將以特定的順序識別出中間單詞的類型(當然只是可能的那些):
  
  清單 14. 無歧義的解析結果
  
  $ echo -n "Read IBM developerWorks" | ./ibm2.py
  Head: Read
  VOWEL: IBM
  Tail: developerWorks
  $ echo -n "Read XYZ journal" | ./ibm2.py
  Head: Read
  CAPS: XYZ
  Tail: journal
  
  做出決定
  盡管得到了一些讀者的建議,我還是不太看重 DParser。它有很多可以作用於結果的強大的開關和選項,我還沒有討論到 —— 比如指定關聯性。大體上,DParser 語言非常健壯,我非常懷疑用於 Python 的 DParser 是否會比純粹的 Python 解析器運行速度快得非常多。
  
  無論如何,我仍然不能對函數文檔字符串風格的解析器具有太多熱情。顯然,關於這一點,很多優秀的 Python 程序員不會贊同我。此外我還發現一些解析結果有些令人不解:為什麼調試模式下可以成功,而標准模式下卻不能成功?含糊問題確切是什麼時候發生的?使用任何解析工具開發語法都會有類似的意外,但是我發現 DParser 不知何故尤其出乎意料;例如 SimpleParse,就不會讓我那麼感到驚訝。可能,如果我了解了底層算法的更多復雜細節,它將會更具意義;不過,就我相對淺薄的學識而言,我可能與 95% 以上的讀者差不多。有人比我更加熟悉解析;但是實際上大部分程序員懂得更少。

Copyright © Linux教程網 All Rights Reserved