如何选择在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派生中使用哪个规则？

回答

相关问题