目錄
- 1 等價(形式語言)
等價(形式語言)
編輯在形式語言理論中,兩個語法的弱等價意味著它們生成相同的字符串集,也就是說,它們生成的形式語言是相同的。在編譯器理論中,這個概念與強等價(或結構性)區分開來,強等價另外意味著兩個解析樹是合理相似的,即同樣的語義解釋可以被分配給兩者。Vijay-Shanker和Weir(1994)證明了線性索引語法、組合分類語法、樹狀連接語法和頭部語法是弱等價的形式主義,因為它們都定義相同的字符串語言。另一方面,如果兩個語法產生相同的派生樹集(或更一般的,相同的抽象句法對象集),那么這兩個語法就是強等價的。
然而,第二種語法的具體語法樹總是反映通常的運算順序,而xxx種語法的樹則不需要。以后綴順序評估該樹將產生正確的值7。相反,左邊圖片部分顯示了xxx種語法對該字符串的一個解析樹;以后綴順序評估將產生9。生成能力在語言學中,一個語法的弱生成能力被定義為由它生成的所有字符串的集合,而一個語法的強生成能力是指由它生成的結構描述的集合。因此,如果兩個語法的弱生成能力相吻合,則被認為是弱等價的;對于強等價也是如此。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/163878/