Search code examples
parsingtreegrammarparse-tree

Trace of parse for input string using parse table

Our professor never got around to teaching us this material in class, and now we have homework on it. Google seems to be leading me in the right direction, but I want to make sure I get it right (of course).

We were given the following grammar and asked to make a parse table based on it:

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

My parse table:

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

Now we're instructed:

"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."

On my internet search, I was able to find this example: enter image description here

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

It looks as if you go through each possibility given in the grammar until you match with the string.

Here's what I came up with:

enter image description here

How's this? Am I understanding it right? I made this by only referencing the grammar; not my parse table..How would I use my parse table to make a trace?

I'm still unsure what this means:

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

Solution

  • This is the gist of what he was looking for (excluding the output; he didn't care about that one):

    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