Showing posts with label parser. Show all posts
Showing posts with label parser. Show all posts

Monday, May 12, 2008

Parser Generators

The practice of programming

在軟體開發過程,我們很可能得寫大量的程式碼來完成一些繁瑣、平凡的工作,避開這個窠臼的辦法就是「自動化」。誠如 Kernighan 和 Pike 在 The Practice of Programming 一書所闡述的,優秀的軟體設計運用幾個基本原則:簡單(simplicity)、清晰(clarity)、一般性(generality)、自動化(automation)。

舉個例子, IC designers 常會跟 f/w 人員一起關起門來,私下協調出各種用途的 registers (memory mapped I/O),這些開放給 f/w 人員使用的 register 介面,會有一份以 Verilog 形式存在,另一份則以 C code 的形式存在,在 IC 開發過程,這些 registers 會經歷多次的變更(例如改名字、改位址、添加 registers、刪減 registers 等)。可以想見,要手動讓這些 registers 在 Verilog 及 C 間維持一致,是件繁瑣、容易出錯的事。

電腦在處理這類格式轉換工作時,得有個 parser 來剖析源文件;偏偏要建構 parser 也有好些瑣碎的東西必須處理。幸好 Compiler 是門發展已久的學問,有許多 parser generators 可以讓這些繁瑣的建構過程自動化。

早期的 parser generators (例如: Yacc )幾乎都是 LR 系列的,一個主要的原因是,教科書告訴我們 LL parser 是不切實際的,只有 LR parsers 才能有高效的表現;另一個理由是, LR parsers 想要手寫,大概也很難 :)

好玩的是後來出現了幾個廣為流行的 parser generators (例如: JavaCC, ANTLR, Boost.Spirit),都走 LL 風。這勾起我的好奇心,細查下才發現 LL 風的 parser generators 在 90 年代有了新的技術突破,我該 update 一下之前教科書塞進我腦袋的資訊了 =.="

如果大家也想複習一下學校教的 Compiler 技術,可以不用翻箱子找課本了,因為維基百科對這方面的資料,紀錄還滿完整的。文末附上我為相關條目所作的分類,相信可以為大家省卻一些時間。

Tags: [] []

Saturday, January 21, 2006

Source Transformation

前幾天由 Tim 的來信,得知有個叫 TXL 的東西,好像很神奇,在好奇心趨使下也去一探究竟:

TXL is a unique programming language specifically designed to support computer software analysis and source transformation tasks. ...TXL is best at tasks that involve structural analysis and transformation of formal notations such as programming languages, specification languages, structured documents and so on.

這看起來不是跟 Lex/Yacc 或 XSL/T 這些軟體的目的很像嗎?應該是同一類的東西吧?但 Learning TXL 的內文第一段卻說:

TXL is a weird and wonderful language, with a new, rich and distinctly different programming paradigm. Once you get your mind around it, it can help you very rapidly achieve real magic. But because it is different, it takes some time to understand. Along the way you will probably mistake it several times for things it isn't (for example, Haskell, Awk, Yacc or XSL/T).

好吧,不是就不是吧,讓我再仔細瞧瞧,看看它葫蘆裡在賣啥藥……

~~

我們可以把程式語言的 Compiler 或 Interpreter 需要做的事情分成兩個任務:

  1. 讀進原始碼,並找出它的結構。
  2. 處理找出來的結構。

傳統的 Lex 和 Yacc 搭配起來剛好可以產生某個程式語言的程式(通常是 C),用來解決第一個任務。要找出原始碼結構,其實有兩件事要做:

  1. 把原始碼切割成一個個的 token 。負責這件子任務的,叫做 scanner 。
  2. 找出原始碼的階層結構。這是 parser 的責任。

而 scanner 及 parser 這兩項子任務,剛好可以分別由 Lex 和 Yacc 來職掌。詳細的用法,可以去 The Lex & Yacc Page 逛逛。裡面有提到 Flex 及 Bison ,它們分別是 Lex 和 Yacc 的後代。我也曾經利用它們來練習寫了個精簡版的 C compiler 。如果你嫌 Flex 及 Bison 功能太陽春的話,也許可以去試試 Antlr 。

~~

在 TXL About 中有提到每個 Txl 程式都包含兩部份:

  1. A Description of the Structures to be Transformed -- Specified as a directly interpreted BNF grammar, in context-free ambiguous form.
  2. A Set of Structural Transformation Rules -- Specified by example as pattern/replacement pairs combined using functional programming.

TXL 程式的第一部份剛好把 scanner 及 parser 的事情做掉了;第二部份把剩下的翻譯工作也完成了。以前做這些事情要分別動用到三套程式語言,現在 TXL 可以一手包辦,一次搞定!

此外,以 Yacc 這類的 parser generator 來說,都會要我們以類似 BNF 的語法,把要處理的語言的文法定出來。 Tex 除了跟別家一樣,支援 Context-Free 的文法外,它還允許訂出的文法可以有歧義或遞迴的情形發生。所以用它定義語法比傳統的 Yacc 方便,但也因此,理論上,它在 parsing 時,就不會快過 Yacc 這類工具。

更令人激賞的是,在 scanning 及 parsing 後,接下來要做的翻譯任務,由於 TXL 的語法混合了 functional / rule-based 語言的語法,所以可以很優雅的解決:

The TXL programming language is a hybrid functional / rule-based language with unification, implied iteration and deep pattern match.

The TXL programming language is unique in that it is has a pure functional superstructure that provides scoping, abstraction, parameterization and recursion, over Prolog-like structural rewriting rules providing pattern search, unification and implicit iteration.

The formal semantics and implementation of TXL are based on formal tree rewriting, but the trees are largely hidden from the user due to the by-example style of rule specification.

Prolog 這類 functional language 的優點,在此表露無遺!