關(guān)聯(lián)文法語法分析的并行處理研究.pdf

1、上下文無關(guān)文法是應(yīng)用最廣泛的一種形式語言,現(xiàn)今大多數(shù)程序設(shè)計(jì)語言的語法結(jié)構(gòu)都是用上下文無關(guān)文法來描述的。但上下文無關(guān)文法描述問題的能力是不充分的,不能很好的處理自然語言。因此,作為上下文無關(guān)文法的改進(jìn)或擴(kuò)充,人們定義了一些特定文法,用于處理不同環(huán)境的語法分析。加拿大的Okhotin引入的關(guān)聯(lián)文法屬于這一類。關(guān)聯(lián)文法是上下文無關(guān)文法的擴(kuò)展,它是在上下文無關(guān)文法的基礎(chǔ)上對(duì)文法產(chǎn)生式規(guī)則加入集合的交運(yùn)算形成的。關(guān)聯(lián)文法仍然保留了上下文無關(guān)文法

2、一些重要特性,但比上下文無關(guān)文法具有更強(qiáng)的生成能力,能夠更好的描述語言的語法結(jié)構(gòu),更好的描述自然語言。對(duì)于關(guān)聯(lián)文法和上下文無關(guān)文法的語法分析和識(shí)別算法通常有LR(k)和LL(k)算法等。 本文對(duì)關(guān)聯(lián)文法進(jìn)行了比較系統(tǒng)的分析與研究,重點(diǎn)討論了并行處理環(huán)境中的并行語法分析問題。由于傳統(tǒng)的CKY并行算法和Earley并行算法只能處理上下文無關(guān)文法的語法分析,針對(duì)這種情況,本文對(duì)關(guān)聯(lián)文法中的交運(yùn)算進(jìn)行特殊處理,在CYK算法和Earley

3、算法中分別引入了f(RE)函數(shù)和finished(R)的集合,并在此基礎(chǔ)上設(shè)計(jì)了關(guān)聯(lián)文法在并行環(huán)境下的語法分析和識(shí)別算法,通過實(shí)例詳細(xì)描述了這兩種算法并行處理的過程,驗(yàn)證算法的可行性和正確性。本文中關(guān)聯(lián)文法語法推導(dǎo)樹采用壓縮樹的形式,與普通推導(dǎo)樹相比,它所占用的存儲(chǔ)空間較少。壓縮推導(dǎo)樹不僅可以共享終結(jié)符葉子,也可以共享具有相同后繼終結(jié)符的子樹。根據(jù)這個(gè)特點(diǎn),推導(dǎo)出相同終結(jié)符的子樹可以同時(shí)被構(gòu)造,文中也提出了并行構(gòu)造關(guān)聯(lián)文法壓縮推導(dǎo)樹的算