algorithm - LR(0)/ SLR / LR(1)解析-如何选择产品?

我试图用语法分析器理论来概括我的思想,并且我不断地在不同的源代码中找到相同的例子语法大致类似于(简化):

E = T
E = E + T
T = 0..9

因此,假设一个字符串2 + 2将被解析为这样的字符串(将堆栈与提醒分开)
|2 + 2 <-can't reduce, shift
2|+ 2  <-reduce by T = 0..9
T|+ 2  <-reduce by E = T
E|+ 2  <-can't reduce, shift
E +|2  <-can't reduce, shift
E + 2| <-reduce by T = 0..9
E + T| <-reduction by E = E + T here?
E|     <-done

问题是,atE + T步骤解析器可以对堆栈的最右边部分应用两种不同的缩减:E = T(导致E + E)和E = E + T(导致E)。我找不到一个清晰而精确的解释,它是如何选择一个而不是另一个的。
我错过了什么?

最佳答案

可能的状态是什么?

0: Beginning
1: Just shifted 0..9 after State 0, recognize a T
2: Reduce State 1 to an E.
3: Just shifted + after State 2 or 5, looking for T
4: Just shifted 0..9 after State 3, recognize a T giving us E + T.
5: Reduce state 4 to an E
6: Reach the end of the stack after state 2 or 5.

所以我们从状态0开始。移动a2。我们现在处于状态1过渡到状态2。移动a+。我们现在处于状态3。我们移动a2我们在4号州。我们减少到第五状态我们到达堆栈的末尾,得到一个表达式树,如下所示:
  E
  |
E + T
|   |
T   2
|
2

本文翻译自 https://stackoverflow.com/questions/53495330/

网站遵循 CC BY-SA 4.0 协议,转载或引用请注明出处。

标签 algorithm parsing lr


相关文章:

java - 单链列表添加/删除

c++ - ACM图像压缩算法C ++

algorithm - kNN是统计分类器吗?

arrays - 如何确定整数数组已排序到的程度/级别

algorithm - 解析上下文无关文法

python - Python,如何在整个文本文件中两次在两个标记之间提取文本?

c# - 大型XML有效解析

ios - 快速下载URL并填充uiimageview

c++ - LR(1)语法的状态,符号和规则数量的合理上限是多少?