解釋面試免費語法歧義面試

Question

我在面試時，這是他們問我的問題，

這兩個下面ambigous？如果是，請提供一個字符串。如果他們不是，證明他們爲什麼不是。

我無法解決它，並想知道答案和未來的原因。

問題1個

S-->XaaaX 
X-->aX | bX | e(epsilon) 

問題2

S-->aaS | aaaS | a 

再次，這是不HW。

謝謝。解釋會有所幫助。

Answer 1

我們記得，如果（且僅當）語法中的某些生成具有多個可能的派生，語法纔是不明確的。

在問題1中，符號S擴展爲XaaaX，然後擴展符號X的可用備選方案包括aX和ε（ε）。傳統上，符號epsilon表示空字符串。將x擴展爲aX中的epsilon會生成一個。所以至少有兩種方法可以獲得aaaa。理查德麥肯納，我會留給你找到他們。

在問題2中，符號S擴展爲aaS，aaaS或a。至少有兩種方法可以獲得aaaaaa。再次，我會留給你找到派生。

如果你願意，你可以在這個頁面上寫出你的派生詞。