[發(fā)明專利]用于線性廣義LL識(shí)別和上下文感知解析的方法和系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201580037492.4
• 申請(qǐng)日: 2015-07-10
• 公開（公告）號(hào): CN106663094B
• 公開（公告）日: 2020-03-27
• 發(fā)明（設(shè)計(jì)）人: 洛林·G·克雷默三世
• 申請(qǐng)（專利權(quán)）人: 洛林·G·克雷默三世
• 主分類號(hào): G06F40/211
• 分類號(hào): G06F40/211
• 代理公司: 北京天昊聯(lián)合知識(shí)產(chǎn)權(quán)代理有限公司 11112
• 代理人: 顧麗波;井杰

1.一種計(jì)算機(jī)實(shí)現(xiàn)的文法分析方法，其生成用于運(yùn)行時(shí)識(shí)別的代碼，以產(chǎn)生在隨后的解析期間給定的句子要遵循的方向的列表或多個(gè)列表的圖形表示，所述方法包括步驟：

解析文法以創(chuàng)建抽象語(yǔ)法樹(AST)表示；

構(gòu)造用于分析的表示文法的所有特征的圖形，所述特征包括遞歸、交替、備選項(xiàng)的分組和循環(huán)；

處理所述圖形中的每個(gè)決策點(diǎn)，用以生成中間表示，所述決策點(diǎn)是具有多個(gè)輸出邊的頂點(diǎn)；

生成識(shí)別函數(shù)的代碼，所述識(shí)別函數(shù)返回在運(yùn)行時(shí)解析決策中使用的方向列表；并且

修補(bǔ)每個(gè)決策點(diǎn)標(biāo)記以引用或內(nèi)聯(lián)每個(gè)決策點(diǎn)的頂層識(shí)別代碼。

2.根據(jù)權(quán)利要求1所述的計(jì)算機(jī)實(shí)現(xiàn)的方法，其中，所述方法還包含：文法的圖形表示與用于生成解析器的所述文法的抽象語(yǔ)法樹或其它內(nèi)部表示的同步化。

3.根據(jù)權(quán)利要求1所述的計(jì)算機(jī)實(shí)現(xiàn)的方法，其中，所述文法特征被表示為包含所述圖形中的特殊標(biāo)記類型的節(jié)點(diǎn)、或包含在源文法中表示終結(jié)符的文法特定標(biāo)記類型的節(jié)點(diǎn)，所述包含所述圖形中的特殊標(biāo)記類型的節(jié)點(diǎn)包括：用于表示用于遞歸管理的堆棧操縱的POP_CONTEXT或PUSH_CONTEXT節(jié)點(diǎn)中的任何一個(gè)，其中，POP_CONTEXT是決策節(jié)點(diǎn)；用于表示備選項(xiàng)的分組的BLOCK或EOB節(jié)點(diǎn)中的任何一個(gè)，其中所述節(jié)點(diǎn)是也存在于所述抽象語(yǔ)法樹中的決策點(diǎn)；也存在于抽象語(yǔ)法樹中的用于實(shí)現(xiàn)上下文感知識(shí)別和解析的語(yǔ)義謂詞的SEMPRED節(jié)點(diǎn)。

4.根據(jù)權(quán)利要求1所述的計(jì)算機(jī)實(shí)現(xiàn)的方法，其中，決策點(diǎn)分析包括步驟：

初始化方法的中間表示或內(nèi)聯(lián)代碼；

構(gòu)建從所述決策點(diǎn)處開始的備選路徑的列表；

生成用于單例的代碼并且從所述列表中移除終止的路徑；

將路徑列表添加至工作隊(duì)列；

處理所述路徑列表，以生成運(yùn)行時(shí)識(shí)別代碼并生成所述工作隊(duì)列中的其他條目；以及

處理所述工作隊(duì)列中的路徑列表，直到所述工作隊(duì)列清空為止。

5.根據(jù)權(quán)利要求4所述的計(jì)算機(jī)實(shí)現(xiàn)的方法，其中，處理所述路徑列表包括步驟：

從工作隊(duì)列獲得路徑列表；

逐步處理所述工作列表，其中，每一步包括對(duì)特殊標(biāo)記類型和/或文法特定標(biāo)記類型的處理；

隨著節(jié)點(diǎn)被處理，在所述路徑列表中從當(dāng)前節(jié)點(diǎn)推進(jìn)至下一個(gè)節(jié)點(diǎn)；

當(dāng)創(chuàng)建了新的路徑列表且將其添加至所述工作隊(duì)列，或者由其先前遇到的等同物替代時(shí)，終止路徑列表處理，以及

將初始路徑列表值保存在列表處理表中。

6.根據(jù)權(quán)利要求4所述的計(jì)算機(jī)實(shí)現(xiàn)的方法，其中，處理所述路徑列表還包括步驟：

檢查所述路徑列表是否具有PUSH_CONTEXT節(jié)點(diǎn)；以及

推進(jìn)PUSH_CONTEXT節(jié)點(diǎn)，將索引值添加至路徑本地堆棧。

7.根據(jù)權(quán)利要求4所述的計(jì)算機(jī)實(shí)現(xiàn)的方法，其中，處理所述路徑列表還包括步驟：

檢查所述路徑列表是否具有POP_CONTEXT節(jié)點(diǎn)；以及

復(fù)制所述路徑列表，并且在所述路徑列表包括POP_CONTEXT節(jié)點(diǎn)時(shí)執(zhí)行POP_CONTEXT處理。

8.根據(jù)權(quán)利要求4所述的計(jì)算機(jī)實(shí)現(xiàn)的方法，其中，處理所述路徑列表還包括步驟：

檢查所述路徑列表是否具有多個(gè)標(biāo)記類型和/或決策點(diǎn)；以及

將決策點(diǎn)精化以創(chuàng)建新的路徑列表，并且在表示了多個(gè)文法特定標(biāo)記類型時(shí)拆分該路徑列表。

9.根據(jù)權(quán)利要求4所述的計(jì)算機(jī)實(shí)現(xiàn)的方法，其中，處理所述路徑列表還包括步驟：

檢查表示運(yùn)行時(shí)、上下文感知識(shí)別和解析的語(yǔ)義謂詞的SEMPRED標(biāo)記；以及

處理所述路徑列表以生成用于運(yùn)行時(shí)面向SEMPRED的運(yùn)行時(shí)決策的代碼。

10.根據(jù)權(quán)利要求4所述的計(jì)算機(jī)實(shí)現(xiàn)的方法，其中，處理所述路徑列表還包括步驟：

檢查所有標(biāo)記類型是否匹配；以及

生成每種標(biāo)記類型的匹配代碼。