一種基于邊的上下文相關圖文法形式化框架.pdf

1、形式語言理論對計算機科學的發(fā)展起了重大的作用，作為對傳統(tǒng)字符文法擴展的圖文法的形式化研究，其重要意義是不言而喻的。圖文法研究中最主要的幾個問題包括：嵌入問題的解決、文法類型的劃分、成員問題的判定和語法分析計算復雜性的降低。過去幾十年中已經有一些圖文法形式化方法及圖文法應用方面的成果問世，但它們大多是基于上下文無關圖文法的。而隨著圖文法研究的不斷深入，人們發(fā)現(xiàn)上下文相關圖文法具有更廣闊的應用前景。目前已經有一些上下文相關圖文法被提出，但它

2、們或者是過于繁瑣，既不直觀又不簡便，不方便使用；或者是計算復雜性太高，不實用。 本文首先對圖文法發(fā)展及其現(xiàn)狀進行了簡要介紹，并重點討論了圖文法研究中的幾個主要問題。在此基礎上，針對現(xiàn)有上下文相關圖文法的一些不足，圍繞解決圖文法中關鍵問題——嵌入問題提出了一個基于邊的上下文相關圖文法形式化框架，并對由此定義的文法的一些性質及相應的歸約算法進行了討論。接著，對所提出的圖文法與已有的文法進行了比較。然后，給出了一個該文法的應用實例：利