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

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

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

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