计算机工程与设计
計算機工程與設計
계산궤공정여설계
COMPUTER ENGINEERING AND DESIGN
2012年
3期
1197-1202,1212
,共7页
XML类型检查%正规树文法%产生式%相交判定%正则表达式%自动机
XML類型檢查%正規樹文法%產生式%相交判定%正則錶達式%自動機
XML류형검사%정규수문법%산생식%상교판정%정칙표체식%자동궤
在针对产生式不相交的正规树文法的XML类型检查中,需要对正规树文法的产生式进行相交判定.基于正规树文法的产生式的构成特点,提出了基于自动机的相交判定算法.根据产生式的内容模型即正则表达式,构建相应自动机,判定两个自动机的交是否为空,该算法的时间复杂度为O( ‖ E1‖·‖ E2‖·|∑E1 ∪∑E2 |).实验结果表明,该算法运行正确且高效,可以应用到针对产生式不相交的正规树文法的XML类型检查中.
在針對產生式不相交的正規樹文法的XML類型檢查中,需要對正規樹文法的產生式進行相交判定.基于正規樹文法的產生式的構成特點,提齣瞭基于自動機的相交判定算法.根據產生式的內容模型即正則錶達式,構建相應自動機,判定兩箇自動機的交是否為空,該算法的時間複雜度為O( ‖ E1‖·‖ E2‖·|∑E1 ∪∑E2 |).實驗結果錶明,該算法運行正確且高效,可以應用到針對產生式不相交的正規樹文法的XML類型檢查中.
재침대산생식불상교적정규수문법적XML류형검사중,수요대정규수문법적산생식진행상교판정.기우정규수문법적산생식적구성특점,제출료기우자동궤적상교판정산법.근거산생식적내용모형즉정칙표체식,구건상응자동궤,판정량개자동궤적교시부위공,해산법적시간복잡도위O( ‖ E1‖·‖ E2‖·|∑E1 ∪∑E2 |).실험결과표명,해산법운행정학차고효,가이응용도침대산생식불상교적정규수문법적XML류형검사중.
