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

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

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