形式语言jflap操作生成SLR.docx

1、形式语言jflap操作生成SLR生成SLR（1）分析表 内容 定义如何建立SLR（1）分析表 构建DFA 构建分析表 SLR（1）分析 定义 在JFLAP中LR分析的类型是SLR（1）分析。 S代表简单的LR。 L是指像LL（1）解析一样对输入字符串从左至右处理。 R指推导将是一个最右推导（在每个步骤中的最右边的变量被替换）。 1表示用输入字符串中的一个符号来帮助指导解析的。 如何建立SLR（1）分析表 我们将通过加载语法开始，这个语法和建立LL（1）分析表是相同的。你可以输入文法（在下面显示）或者加载文件grammarToLL.jff。在加载语法后，点击Input后在点击BuildSLR(1

2、)ParseTable。新规则是自动添加到语法，“S-S”,导致一个新的开始变量“S”，它并不出现在任何产生式的右侧。进入SLR（1）分析模式后你的窗口看起来应该像这样： 和LL(1)分析一样，我们不得不输入FIRST集和FOLLOW集。如果你还没有准备好的话，请阅读在生成LL（1）分析表教程中的FIRST和FOLLOW集的内容。在输入FIRST和FOLLOW集后点击Next。你应该从JFLAP中得到消息和你的窗口应该是这样的： 注意：你可以点击两次DoStep按钮，让JFLAP自动构建FIRST和FOLLOW集。 构建DFA 我们现在建立一个DFA模拟SLR（1）过程。每个状态将有一个带有标

3、志产生式的标签称为项。该标记显示为“.”。一个项目中标记的左侧的那些符号已经解析堆栈上了，而标记的右侧的那些符号将被推进解析堆栈。对于一个状态的所有项被称为项集。 JFLAP现在会询问您是否要定义的初始设置。如果你点击“Yes”，JFLAP会弹出一个小窗口在这里你可以定义的初始集。如果你点击“No”，JFLAP会自动为你创建的初始集。假设你点击“Yes”，然后你会看到像这样的一个窗口： 当您单击产生式，你会发现所有可能从该产生式导出的所有可能的项出现。由于还没有添加任何东西到堆栈中，单击产生式“S-.S”。由于标记是在变量“S”的前面，带有“.”的所有的S项作为最左符号被添加到项集中。在我们的

4、语法中只有产生式“S-.aABb”满足规则。 注意：你可以点击Finish让JFLAP为该状态创建项。当你完成了,你的窗口应该像这样： 现在你让你的第一个状态“q0”按以下图片所示创建： 注意：你可以通过点击和移动窗口中的水平条和垂直条使在面板中的状态变大。你可能还想扩大窗口到全屏。 我们应该增加更多的状态和转换来完成这个图。首先单击在图面板“转到符号”按钮，它是在“箭头”按钮旁边的按钮。从我们的初始状态q0开始，我们知道只有两种转换可能。一个是与变量S，另一种是终结符“a”，因为这些符号在项集中都在标志的后面。 在点击“去设置符号”按钮后，点击我们的初始状态后拖拽鼠标到达我们想建立新状态的点

5、。接下来JFLAP要求您输入转换的符号。我们假定是变量“S”。当你输入变量S，你会在窗口中看到“去设置S”。现在点击生产的“S-S”，由于我们已经使用输入“S”从我们的初始状态移动，变量“S”不再在标志的后面了。他现在在标记的左侧。由于在标记左侧不存在变量，从新的状态不存在转换传出去了。我们完成“S上”后看起来应该像这样： 我们还可以使用终结符“a”来添加来自状态q0的其它转换。遵循同样的步骤，我们将“Gotoona”窗口结束。我们添加产生式“S-a.ABb”，由于我们使用终结符“a”来到这个新状态（它模拟了在SLR（1）解析过程中“a”被推进解析堆栈中）。现在我们必须检查变量“A”，因为标记

6、是在它的前面。我们从变量“A”添加产生式，它是以标记“.”开始。有两个产生式需要添加，产生式“A-.”和A-.aAc”。 现在在创建这两个新的状态后，我们的图是这样的： 如果它的项之一拥有标记作为产生是右侧的最后一个符号，那么这个状态是最终状态。因为我们现在知道q1是我们的一个最终状态，我们可以单击属性按钮（“箭头”按钮），然后右键单击q1。我们可以选择“终结”以使状态q1变成最终状态。尝试添加其他的状态和他们的项集。 在添加所有的状态（或点击DoStep），你最终的图表看起来应该像这样： 注意：语法窗口的子面板调整大小以显示图。 注意：您可以点击在DFA中的状态并移动他们到一个更好的图片。

7、构建分析表 DFA是用来构建解析表的。DFA中的每一个转换导致两种情况：一个终结符的转变条目或者一个变量的goto条目。在最右端标记的每个标记规则(在最终状态被发现)导致规则减少。 现在有时间在解析表中添加项。我们可以从解析表中的第0行开始填充，其对应于状态q0。从状态q0开始，有两个转换导致两个操作。在“S”的转换涉及到“转到”状态1（q1）和“a”的转换涉及到“移动”终结符“a”及进入状态2（q2）。因此，在分析表第0行把s2（“s代表“移动”）放在“a”列，并把1（指刚刚进入状态q1）放在S列。现在，我们已经完成了分析表中状态q0的部分。下一步是为状态q1填写解析表，这对应于第1行。当我

8、们到达状态q1。由于开始变量“S”被弹出堆栈我们已经完成了解析。因此在状态q1我们应该接受字符串。通过打印“acc”来填写条目，代表在列“$上已被接受，这意味着没有符号留下继续处理。填满SLR分析表中的前两行后你的窗口应该是这样的： 有两个从状态q2转出的转换，让我们填写第2行。对于“a”转换，我们可以把“s4”放在第2行“a”列中。对于“A”转换，我们可以把数字3放在第2行“A”列中。由于q2是终结状态，它至少有一个减少规则（在规则的右侧的最右端有一个标志的规则），这个减少规则是“A-lambda”，在JFLAP中显示为“A-.”，在JFLAP中被编号为规则3号。我们可以把减少规则“r3”放

9、在第二行和在FOLLOW(A)中所有符号的列中，即“b”和“c。现在我们完成了第2行。 注意：现在我们有有4个操作来使用填写解析表：“s”（移位）和“r”（减少）跟随终点行号，“acc”接受，只是一个终点行号来表示转换使用变量。 试着为每个剩余的行填写项。当完成时SLR分析表看起来像这样： SLR（1）分析 我们已经完成了SLR(1)分析表。然后点击Parse和在SLR（1）分析窗口，输入“aacbbcb”作为输入字符串。再点击Start和按Step。你的窗口应该像现在这样： 请注意我们在树状面板中有一个带有终结符“A”的节点。我们已经获得第一个“a”,所以我们会从从输入剩余中删除这个“a”。现在堆栈里有“2a0”，这意味着我们使用转换终结符“A”从状态0到状态2。您还会注意到应用于输入字符串的操作在分析表中会突出显示。“s2”“a”列中。每当一个减少施加时解析表中的条目和实际执行减少的产生式将会被突出显示。点击Step几次后，观察会发生什么事直到字符串被接受。最后的窗口应该像其中的一个： 我们就这样结束简短的关于建立SLR（1）分析表的教程。感谢您的阅读！