CODEWITHSUNDEEP
compiler-constructionparsing
talg
talg

Reputation: 1779

Building Predictive Parser and parsing table

I'm trying to build a parser for the following grammar (dragon book ex. 4.4.1 pg. 231):

S -> 0 S 1 | 0 1

So first I left factored the grammar and got:

S  -> 0 S'
S' -> S 1 | 1

And constructing the parsing table yielded:

     +-----------+---------+--------+
     |     0     |    1    |    $   |
-----+-----------+---------+--------+
  S  | S -> 0 S' |         |        |
-----+-----------+---------+--------+
  S' | S' -> S 1 | S' -> 1 |        |
-----+---------------------+--------+

Is it OK not to have any entries for the $ (end of the input) symbol? How is parsing performed by the predictive parser in that case?

Upvotes: 1

Views: 3369

Answers (1)

Renan Gomes
Renan Gomes

Reputation: 81

YES, because S and S'do not accept the empty symbol.

consider:

S->0S' 
S'->0S|1
S-> empty

your table will be:

---------------------------------
   | 0     | 1      | $         |
---------------------------------
S  | S->0S'|        | S-> empty |
---------------------------------
S' | S'->S1| S'->1  |           |
---------------------------------

You can watch this video: http://www.youtube.com/watch?v=E4to0HuZh3Q

Upvotes: 1

Related Questions