弱優先文法

弱優先文法

一個文法稱為“弱優先文法”,如果它沒有移動辨別衝突,並且由後綴產生的所有辨識問題可以通過下面的原理來解決的話。如果給定文法有形如:<A>→αyγ,<B>→γ的兩個產生式,其中α和γ是符號串,y是文法符號,並且如果y BELOW <B>不成立,那么當第一個產生式的右部在棧頂時,第二個產生式不可能是句柄產生式。這樣,基於給定文法的移動辨別機的辨別例行程式可這樣設計:當兩個右部都在棧頂時,不執行對應於第二個產生式的歸約操作。

一方面,簡單優先文法一定是弱優先文法,但反過來不一定成立;另一方面,弱優先文法無二義性。

基本介紹

  • 中文名:弱優先文法
  • 外文名:Weak precedence grammar
  • 性質:簡單優先文法必為弱優先文法
  • 重要性質:弱優先文法無二義性
  • 評定方法:定義中4個條件
  • 套用學科:編譯原理
定義,重要性質,簡單優先文法與弱優先文法的關係,弱優先文法無二義,注意事項,

定義

如果給定文法有形如:
的兩個產生式,其中α和γ是符號串,y是文法符號,並且如果y BELOW <B>不成立,那么當第一個產生式的右部在棧頂時,第二個產生式不可能是句柄產生式。這樣,基於給定文法的移動辨別機的辨別例行程式可這樣設計:當兩個右部都在棧頂時,不執行對應於第二個產生式的歸約操作。
一個文法稱為“弱優先文法”,如果它沒有移動辨別衝突,並且由後綴產生的所有辨識問題可以通過上面的原理來解決的話。具體地說,一個文法稱為弱優先文法,若且唯若下面四個條件成立:
(1)檔案沒有移動辨別衝突;
(2)任何兩個產生式沒有相同的右部;
(3)對於形如
的任何兩個產生式y BELOW <B>不成立,其中α和γ是符號串,y是文法符號。
(4)
不成立,其中<S>是開始符號。(加上這個條件是為了排除一種特殊的未必被其它條件排除文法二義性。在弱優先文法的定義中加上該條件之後,滿足這個定義的任何文法肯定是無二義性文法。)

重要性質

簡單優先文法與弱優先文法的關係

如果一個文法的產生式右部各不相同,且優先矩陣不含有衝突,那么該文法就是簡單優先文法。簡單優先文法所產生的語言可以由自底向上的下推自動機識別。這一自底向上的下推自動機的構造也並不複雜。
簡單優先文法一定是弱優先文法,但反過來不一定成立。

弱優先文法無二義

可對該性質進行簡單說明:
設G是弱優先文法,考察下推自動機是如何分析輸入符號串的:當棧頂符號R和當前輸入符號S之間存在弱優先關係R<S時,R不是任何短語的尾符號,這樣就可將當前輸入符號S移入到下推棧。當棧頂符號R和當前輸入符號S之間存在弱優先關係R>S時,R是句型的簡單短語的尾符號。由於掃描嚴格從左到右方式進行,此簡單短語一定是最左簡單短語,即它是柄短語。由於G是弱優先文法,G的任何兩個產生式的右部各不相同,而且若下推棧頂部是xSy,則應該用
進行歸約。否則,如果用產生式
進行歸約,下推棧頂部變成
,從而和弱優先文法的定義矛盾。既然G所產生的句子每次歸約時所用的產生式唯一,這意味著,對G的任何句子來說,其句法樹唯一,所以弱優先文法無二義

注意事項

1.對於給定的弱優先文法,可按與後綴無關SI文法一樣的方法來設計移動辨別機,但有一點例外,就是必須設計一些辨別例行程式來執行對應於頂最長右部的REDUCE操作。
2.由於把後綴無關SI文法的設計方法推廣到弱優先文法,所以我們得到任何弱優先文法可用作由該文法所確定的語言移動辨別識別器的基礎。
3.如果計算得到的弱優先矩陣中不存在弱優先衝突,還不能說該文法是弱優先文法。

相關詞條

熱門詞條

聯絡我們