基于單向點(diǎn)格自動機(jī)的UPG文法識別并行算法

李玉萍

（商丘師范學(xué)院 計(jì)算機(jī)與信息技術(shù)學(xué)院，河南 商丘 476000）

基于單向點(diǎn)格自動機(jī)的UPG文法識別并行算法

李玉萍

（商丘師范學(xué)院 計(jì)算機(jī)與信息技術(shù)學(xué)院，河南 商丘 476000）

UPG文法是一種特殊的生成文法，在分析的過程中可以沒有回溯。該文法能夠更好地描述自然語言中特殊的語法結(jié)構(gòu)。單向點(diǎn)格自動機(jī)是進(jìn)行語言并行識別的模型。通過對該文法和點(diǎn)格自動機(jī)深入的分析，提出了一種在并行環(huán)境下基于點(diǎn)格自動機(jī)的無回溯的語法分析和識別算法。文章通過實(shí)例詳細(xì)描述了算法并行處理的過程，驗(yàn)證算法的正確性和可行性。

UPD文法；單向點(diǎn)格自動機(jī)；語法分析

點(diǎn)格自動機(jī)是一種數(shù)學(xué)模型，由J.von Neumann在40年代提出，最初用它來模擬生物系統(tǒng)中某些自組織現(xiàn)象。隨著計(jì)算機(jī)技術(shù)的發(fā)展，它已成為分析復(fù)雜現(xiàn)象的一種有效工具。

目前，大多數(shù)程序設(shè)計(jì)語言采用上下文無關(guān)文法進(jìn)行描述，但上下無關(guān)文法描述問題的能力有限，因此對上下文無關(guān)文法進(jìn)行擴(kuò)充，形成了一種特殊的UPG文法。UPG文法作為一種特殊的生成文法，具有重要特性，在進(jìn)行語法分析的時(shí)可以沒有回溯，能夠更好地描述自然語言中特定的語法結(jié)構(gòu)。

隨著計(jì)算機(jī)的發(fā)展趨向于并行化，多處理機(jī)并行處理是不可逆轉(zhuǎn)的時(shí)代，因此對UPD文法在并行環(huán)境下處理過程的分析和研究有其理論和實(shí)踐意義。根據(jù)點(diǎn)格自動機(jī)和UPD文法的特殊的屬性，文章提出了利用單向點(diǎn)格自動機(jī)模型對UPD文法進(jìn)行并行轉(zhuǎn)換和并行語言識別的算法，通過實(shí)例進(jìn)行分析，說明了算法的正確性和可行性。

1 基本概念

定義1UPG文法是一個(gè)五元組 G=(N,T,P,S,$)，N是一個(gè)非空的非終結(jié)符的有窮字母集；T是一個(gè)非空的終結(jié)符的有窮字母集，T和N的交集為空；S為開始符號，$是一個(gè)特殊的結(jié)束符號，$既不屬于終結(jié)符集合也不屬于非終結(jié)符集合，P是語法規(guī)則的有限集合，該規(guī)則形式如：

α→β,α→$β,α$→β$,$α$→$β$或者$A$→$$

其中α,β∈(N?T)+,A∈N，α至少包含一個(gè)非終結(jié)符，$A$→$$為一個(gè)空規(guī)則，這些規(guī)則必學(xué)滿足下列條件

（1）每一個(gè)規(guī)則右邊不能出現(xiàn)S,$S,S$,$S$

（b）如果 β1=γβ2γ',其中γ，γ'∈（N?T?$）+，則R1=R2

定義2對于一個(gè)UPG文法，如果α→β,η=γαδ,可以得到 ξ=γβδ，則稱 ξ是η的直接推導(dǎo)，即η?ξ。定義?*為傳遞閉包，經(jīng)過n步推導(dǎo)可表示為η?nξ。如果 $S$?*η，則稱η為一個(gè)句型，該文法的語言可以定義為 L(G)={ω∈T*|$S$?*$ω$}。

定義3對于一個(gè)UPG文法，η=γβδ，其中γ，δ∈（N?T?$）*，|γ|=j-1（表示γ的長度），如果α→β，ξ=γαδ，則對任意的[α→β,j]為η的反向有效項(xiàng)目，對ξ可以直接規(guī)約為 η[α→β,j]ξ，因此?*，?的定義和?*，?的定義類似。

定理1G=(N,T,P,S,$)是一個(gè)UPG文法，對于串η，如果η?n$S$，其中η∈（N?T?$）+，η?ξ，則η?ξ?n-1$S$。

定義4假設(shè)l，r為非負(fù)整數(shù)，α=γα'δ,β→γβ'δ,|γ|=l,|δ|=r，則R=[α→β,(l,r)]為上下文索引規(guī)則，γ、δ為左右上下文，（l，r）為上下文索引。

定義5對于一個(gè)UPG文法，根據(jù)定義4可以該文法的規(guī)則集P可以被改寫為 [α→β,(l,r)]，[α$→β$,(l,r)]，[$α→$β,(l,r)]，或者 [$A$→$$,(1,1)]，其中α∈((N?T)+-T+)，β∈(N?T)+，α≠β,A∈N

定義6G=(N,T,P,S,$)是一個(gè)UPG文法，ξ∈（N?T?$）+，{I 1…Ik}為ξ所有的反向有效項(xiàng)目集，Ii=[αi→βi,(li,ri)]叫直接最大并行約簡，則

定理2UPG文法，如果 ξ?m$S$，對于定義5的任意的反向有效項(xiàng)目集則有

定義7一個(gè)單向點(diǎn)格自動機(jī)（OCA）是一個(gè)五元組C=(Q,Q0,Qf,#,fC)，這里Q是非空的有限狀態(tài)集，Q0是一個(gè)非空輸入狀態(tài)集合，Qf為接收狀態(tài)（Q0?Q,Qf?Q），fC為（(Q?{#})2→Q）的局部轉(zhuǎn)換函數(shù)，該函數(shù)滿足：f（Ca,b）=#，當(dāng)且僅當(dāng)b=#。

全局變量 F(a1a2…an)=fC(#,a1)fC(a1,a2)…fC(an-1,an)

當(dāng)n=1,F(a1)=fC(#,a1)。

定理3令L?Q+0為單向點(diǎn)格自動機(jī)可以實(shí)時(shí)識別的語言，則存在一個(gè)具有反向有效項(xiàng)目集的UPG文法G，使得L(G)=L。對于每一個(gè)字符串ω∈L可以通過反向有效項(xiàng)目集約簡得到。

定理4令L可以被OCA所識別，則一定存在一個(gè)UPG文法，使得L(G)=L。

2 基于單向點(diǎn)格自動機(jī)的UPG文法并行識別算法

2.1 利用點(diǎn)格自動機(jī)并行構(gòu)造U?PG文法的反向有效項(xiàng)目集算法

算法1：給定 C=(Q,Q0,Qf,#,fC)為點(diǎn)格自動機(jī)，Q=(a1a2…am)；UPG文法 G=(N,T,P,S,$)，這里N={S,S',S"}?{A1,…Am}?{*}。根據(jù)點(diǎn)格自動機(jī)對文法G的反向有效項(xiàng)目集的并行構(gòu)造如下：

（a）對于每一個(gè)狀態(tài)ai∈Qf，則對應(yīng)的反向項(xiàng)目集為[S→S'AiS",(0,0)]；

（b）對于ai,aj,ah∈Q,fC(ai,aj)=ah，則對應(yīng)的反向項(xiàng)目集為[Ah*Ah→AiAj*,(0,0)]；

（c）對于ai,aj,ah∈Q,fC(#,ai)=aj，則對應(yīng)的項(xiàng)目集為[$S'Aj→$Ai*,(1,0)],[S'→S'Ah*(1,0)]；

（d）對于ai∈Q-Qf,則對應(yīng)的項(xiàng)目集為[S"$→Ai$,(0,1)],[S"→AiS",(0,1)]；

（e）對于每一個(gè)狀態(tài)ai∈Q0,，則對應(yīng)的項(xiàng)目集為[Ai*Aj→ai,(0,0)]；

2.2 UPG文法的并行識別算法

算法2：輸入字符串$b1b2…bn$

輸出：如果b1b2…bn是L（G）中某個(gè)長度為n的句子，那么返回真；否則返回假。

（i）對于輸入串中每個(gè)字符b1，b2，…，bn利用算法1（e）中的最大反向規(guī)約項(xiàng)目集并行規(guī)約；（ii）對于由（i）得到的字符串利用算法1（b）中的最大反向規(guī)約項(xiàng)目集并行規(guī)約；

（iii）對于由（ii）得到的字符串利用算法1中的（c），（d）中的最大反向規(guī)約項(xiàng)目集并行規(guī)約；

（iv）經(jīng)過n+2步得到的字符串S'AiS"利用算法1中的（a）中的最大反向規(guī)約項(xiàng)目集進(jìn)行規(guī)約，得到字符串$S$，

從而可以得出$b1b2…bn$?n+2$S$，則該字符串可以被文法UPG文法識別。

3 實(shí)例分析

假設(shè)L={a2k|k=1，2，…}，L可以被點(diǎn)格自動機(jī)（OCA）所識別，點(diǎn)格自動機(jī)OCA C=({a,b,c},{a},{c},#,fC)，fC的定義如下：

fC（b,a）=c，fC（c,a）=c，fC（a,a）=a，fC（c,b）=b，fC（b,c）=c，fC（#,a）=b，fC（#,b）=b。

根據(jù)算法1，并行構(gòu)UPG G=({A,B,C,S,S',S",*},a,P,S,$)的反向有效項(xiàng)目集，可得

[S→S'CS",(0,0)]，[C*C→BA*,(0,0)]，[B*B→CA*,(0,0)]

[A*A→AA*,(0,0)]，[B*B→CB*,(0,0)][C*C→BC*,(0,0)]

[$S'B→$A*,(1,0)]，[S'→S'A*,(1,0)]

[$S'B→$B*,(1,0)][S'→S'B*,(1,0)]

[S'→S'C*,(1,0)]，[S''$→B$,(0,1)]

[S''$→A$,(0,1)]，[S''→AS'',(0,1)]

[S''→BS'',(0,1)][A*A→a,(0,0)]

給定輸入字符串為$aaaa$

根據(jù)算法2對輸入字符串分步并行規(guī)約可得

則字符串a(chǎn)aaa可以被該文法識別。

4 結(jié)束語

UPG文法是一種特殊的文法，可以利用單向點(diǎn)格自動機(jī)構(gòu)造并行UPD文法的反向有效項(xiàng)目集。對于給定字符串的語法識別的過程中，根據(jù)UPD文法并行分析算法，對字符串找最大規(guī)約項(xiàng)，如果可以規(guī)約到開始符號，則該字符串符合該文法。但算法的性能以及處理器內(nèi)部通信，負(fù)載分布等問題還需要進(jìn)一步的研究。?

參考文獻(xiàn)：

［1］J.Lee，K.Morita.Uniquely parallelparsableunification grammars［J］.Leice Transaction on Information and Systems，2001，84（1）：21-27.［2］羅莎.一種高效的自然語言理解語法分析算法［J］.科技通報(bào)，2013，（12）：91-93.

［3］W.Bucher，K.Culik II.On real timeand linear time cellularautomata［J］.Iform.Theory，1995：307-325.

［4］Gibbons A，RytterW.Efficientparallelparsingalgorithms［M］.Cambridge University Press，1990.

［5］周勇.基于并行計(jì)算的數(shù)據(jù)流處理方法研究［D］.大連理工大學(xué)，2013.

［6］陳國良.并行計(jì)算.北京：高等教育出版社［M］，2011.

［7］段曉東.元胞自動機(jī)理論研究及其仿真應(yīng)用［M］.北京：科學(xué)出版社，2012.

Parallel Processing of Syntax Parsing Algorithm for UPD Grammar Based on One-way Cell Automata

LIYu-ping
（DepartmentofComputerand Information Technology,Shangqiu Normal College, Shangqiu,Henan,476000,China）

A uniquely parsable grammar（UPD）is a special kind ofgenerative grammarwhere parsing can be performed withoutbacktracking.UPD grammars have greater generative power than the context-free grammars.This family ofgrammarsand one-way cellautomata is deeply analyzed.A recognition and parsing algorithm under Parallelenvironment ispresented.The processofparallelprocessing is described by instance and the validity of the algorithm is verified.

UPD grammars;One-way cellautomata;Syntax Analysis

TP301

A

1008-9659（2016）02-0071-04

2016-03-25

河南省科技廳基礎(chǔ)與前沿技術(shù)研究計(jì)劃項(xiàng)目（142300410395）。

李玉萍（1982-），女，河南開封人，講師，碩士，主要從事并行編譯技術(shù)研究。