使用 parse table 跟踪输入字符串的解析

Question

我们的教授从来没有抽空在 class 中教我们这个 material，现在我们有关于它的作业。 Google 似乎在引导我朝着正确的方向前进，但我想确保我做对了（当然）。

我们得到了以下语法，并要求我们根据它进行解析 table：

1.  S -> ABe
2.  A -> dB
3.  A -> aS
4.  A -> c
5.  B -> AS
6.  B -> b

我的解析table:

_| a | b | c | d | e | #
S|ABe|   |ABe|ABe|   |
A|aS |   | c |dB |   |
B|AS | b |AS |AS |   |

现在我们得到指示：

"Using your parse table, give a trace of the parse for the input string dbbe. Give the unused input string, stack, and output (sequence of rule numbers) at the beginning of each iteration."

在我的互联网搜索中，我找到了这个例子：

来源：http://what-when-how.com/compiler-writing/top-down-parsing-compiler-writing-part-1/

看起来好像您遍历了语法中给出的每种可能性，直到与字符串匹配。

这是我想出的：

这个怎么样？我理解对吗？我只是通过参考语法来做到这一点；不是我的解析 table..我如何使用我的解析 table 进行跟踪？

我仍然不确定这意味着什么：

Give the unused input string, stack, and output (sequence of rule numbers) at the beginning of each iteration

Answer 1

这是他正在寻找的要点（不包括输出；他不关心那个）：

Stack:     Input String:
S#         dbbe#          <- S->ABe
ABe#       dbbe#          <- A->db
dbBe#      dbbe#          <- Pop off matching 'd' at beginning of stack and string
bBe#       bbe#           <- Pop off the matching 'b's...
Be#        be#            <- B->b
be#        be#            <- Pop off 'b's...
e#         e#             <- Pop off 'e's...
#          #              <- Reaching this point on both the stack and input means the input was valid

使用 parse table 跟踪输入字符串的解析

Trace of parse for input string using parse table

tree

grammar

parsing

parse-tree