通過有限狀態(tài)自動機發(fā)現(xiàn)正確的路徑，或者發(fā)現(xiàn)對于輸入的正確的轉(zhuǎn)錄，可以看成是一個搜索問題。例如，對于FSA來說，剖析就是在自動機中搜索一切可能的路徑空間。在句法剖析中，剖析可以看成是對于一個句子搜索一切可能的剖析樹空間并發(fā)現(xiàn)正確的剖析樹。搜索一切可能的路徑空間可以用FSA的結(jié)構(gòu)來定義，所以，搜索一切可能的剖析樹空間也可以用語法來定義。例如，我們來考慮如下的ATIS中的句子：

Book that flight.   （1）

可以使用圖2中的微型語法和詞表，其中包括英語CFG規(guī)則。指派給這個句子的正確的剖析樹如圖1所示。

怎樣使用圖2中的語法來給例句（1）指派圖1中的剖析樹呢？在這種情況下，只存在一個剖析樹，但是也可能存在一個以上的剖析樹。剖析搜索的目標(biāo)是發(fā)現(xiàn)以初始符號S為根并且恰好覆蓋整個輸入符號串的一切剖析樹。無論選擇什么搜索算法，這里明顯地存在著兩種約束有助于指導(dǎo)這種搜索。第一種約束來自數(shù)據(jù)，即輸入句子本身。如果最后的剖析樹是正確的，它必須有三個葉子，而且這三個葉子應(yīng)該分別是book，that和flight。第二種約束來自語法。如果最后的剖析樹是正確的，它必須有一個根，這個根就是初始符號S。

關(guān)于經(jīng)驗主義和理性主義的論戰(zhàn)，我們可以認(rèn)識到，這兩種約束同時也就產(chǎn)生了大多數(shù)剖析算法使用的兩種搜索策略：一種是自頂向下或目標(biāo)制導(dǎo)的搜索（goal-directed search）,一種是自底向上或數(shù)據(jù)制導(dǎo)的搜索（data-directed search）。

責(zé)任編輯：admin