VPGE（Visual Parser Generation Environment）是一個可視化語法分析器集成開發環境,
除了具有良好的界面和強大的調試功能,其LALR(1)分析器的生成速度達到并超過公認的分析器生成速度最快的LALR(1)分析器自動生成器Bison,所能處理的文法規模也優于Bison.本文在DeRemer 和Pennello 的LALR(1)分析器自動生成基本原理的基礎上,在設計數據結構和算法實現中采用了大量優化技術.
隨著計算機軟硬件技術的發展,語法分析越來越多地應用于計算機技術的各個領域,尤其在逆向工程、再工程和語言原型技術中得到廣泛的關注.語法分析器自動生成器(parser generator),也稱編譯器的編譯器(compiler’s compiler),是語法分析中主要的支持工具.眾所周知,美國貝爾實驗室開發的YACC [1]和自由軟件基金會90 年代研制的與YACC 兼容的Bison[2]是目前流行的分析器自動生成工具.然而由于上述工具采用簡單的命令1行交互方式,沒有統一的集成開發環境,不直接支持文法的診斷調試,因此易用性差,不能夠滿足現在技術的發展和應用領域的需求.
VPGE(Visual Parser Generation Environment)是北京航空航天大學軟件工程研究所歷時兩年自主研制的一個可視化LALR(1)分析器自動生成和交互式調試環境.針對傳統工具的不足,VPGE 進行了相應的改進,提供了可視化交互式的集成開發環境,用戶可直接在集成環境中進行詞法分析器的編輯、編譯,語法分析器的編輯、編譯和調試.VPGE 擁有強大的文法調試能力,可以指定測試文件進行LR 分析,在文法位置上插入斷點,可視化地展示LR 分析器的各種重要數據結構.由于文法的調試過程也就是分析器的自動生成過程,因此分析器自動生成的效率直接影響了文法調試的效果.本文的主要內容便是介紹我們在研制VPGE 的過程中采用的以DeRemer 和Pennello 的方法[3]為基礎的LALR(1)分析器自動生成優化算法.實驗結果顯示,VPGE 的LALR(1)分析器生成速度超過了當今公認的分析器生成速度最快的Bison.