如何選擇在CFG派生中使用哪個規則？

我對這本教科書很難接受，而且我的教授認爲回答問題對已經知道進入課堂的材料的學生是不公平的（從這個人獲得的反饋是一個數據挖掘過程本身）。無論如何，我的問題圍繞着CFG（正式語言/函數式編程類）的派生。如何選擇在CFG派生中使用哪個規則？

Given a context free grammar that looks like: 
S-> a|B 
B-> b|C 
C-> c

找到最左邊的推導。是簡單的嗎？因爲S-> a是S-> a | B中最左邊的規則。或者我只是斷定推導可以是a，b或c？我真的很困惑要選擇哪個規則，我一直在按照左右順序排列這些問題，以便對每個（最左邊）變量分析的規則進行選擇，但是這個規則沒有遞歸在它，所以我不知道該怎麼做。我非常感謝這方面的任何見解，我已經觀看了視頻並閱讀了這本書，但似乎沒有人會談論這種情況。謝謝。

此外，我們的書：http://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf

來源

2015-12-02 zodian

查找* what *的最左邊派生。 – rici

「語法的典型最左派生。」我知道如何做的一個例子就像是S-> aSc | b。解決方案是S => aSc => aaScc => aabcc - 然後我可以在LL解析/ PDA中使用aabcc作爲字符串。 – zodian

維基百科對「最左派生」的含義進行了合理解釋：https：//en.wikipedia.org/wiki/Context-free_grammar#Derivations_and_syntax_trees請注意，除非某些產品右手邊有多個非終端，在部分推導中將永遠不會有多個非終端，因此所有派生都將是最左邊*和最右邊。 – rici

你沒有串推導from.That就是爲什麼您在爲一個困難時期。你給我們的給定只是生產規則。

因此，例如，我們的語法看起來像這樣

S -> A + B | a | b A -> B + B | a | b B -> a | b | c

比方說，我們即將找到字符串a+b+c的最左邊，推導。

然後，這是我們要參考生產規則的時間。

讓我們開始推導與起始符號

S => A + B (S has been derived to A + B)

A + B => B + B + B (A, the leftmost variable has been derived to B + B)

B + B + B => a + B + B (B, the leftmost variable has been derived to a)

a + B + B => a + b + B (B, the leftmost variable has been derived to b)

a + b + B => a + b + c (the remaining B, and the leftmost B has been derived to c)

由於我們生成的最後一個字符串（a + b + c）與

相匹配，所以我們將導出字符串（a + b + c），然後我們使用最左邊的推導完成了推導。

來源

2016-01-10 09:11:15

如何選擇在CFG派生中使用哪個規則？

回答

相關問題