字組分析的預看問題之研究

Abstract

今日的程式語言,大都使用規則表式(Regular expression)規定基本字組.這些規則表式可以自動 轉換成最小自動機,最小自動機是傳統的字組 分析器的核心.但是我們發現最小自動機無法 解決預看字元的問題.製作字組分析器的程式 師,不但要用規則表式定義字組的組成規則,並 且須要仔細分析規則表式,找出可能需要預看 字元的地方,撰寫程式,處理預看問題.這是非常 瑣碎煩雜的工作,我們計畫將這些瑣碎繁雜的工作,完全自動化.為了解決預看的問題,我們找 出了一類"有限預看自動機",有限預看自動機, 就是這些最多只須預看有限數目的輸入字元, 就能決定字組的自動.我們發現,一般程式語言 的字組分析器,均是有限預看自動機,所以我們 只考慮有限預看自動機,這並不是嚴重的限制. 接著,我們將有限預看自動機轉換成尾同式自 動機(Suffix automata).我們的字組分析器,就是以 尾同式自動機為基礎,我們除了利用傳統的狀態變化表之外,另有三個表(持續表、行動表及 輸出表)也從尾同式自動機裡產生出來.我們的 自組分析器,利用這四個表,判別字組,它有三項 特色:(1)它能解決預看問題;(2)每一個輸入字元 只被分析一次;(3)錯誤的字組能夠在最早的時 刻被察覺出來.新的字組產生器所付出額外的 代價,是較大的狀態變化表及三個新的表,預看 問題也會影響漸進式的字組分析.所謂漸進式 分析,就是將已分析的輸入字串,略做修改,如何 重新做字組分析.一個簡單的方法,就是全部重 做分析,這個方法並非最好尤其是當只有很小 的部分被修改時,這個方法非常無效率.我們找 到一個更佳的方法,來做漸進式字組分析.