2
$\begingroup$

Consider the following BNF Grammar G:

object-expression   ::=     id | id ( object-expression ) | object-expression . id
                            | object-expression [ object-expression ]
                            | object-expression . id ( object-expression )

I am attempting to construct a set of LR(1) items based on G.

Attempt:

Let's represent Grammar G as:

O -> id
O -> id ( O )
O -> O . id
O -> O [ O ]
O -> O . id ( O )

Item Set 1:

O' -> • O, $
O -> • id, $
O -> • id ( O ), $
O -> • O . id, $
O -> • O [ O ], $
O -> • O . id ( O ), $

Can someone provide an intuitive explanation in simple language on how to finish obtaining a set of LR(1) items given a BNF Grammar such as G?

Please let me know if I can provide any more information.

$\endgroup$
  • $\begingroup$ Just follow the algorithm. It is really better if you understand the algorithm, but it won't necessarily make it easier to apply it. $\endgroup$ – Yuval Filmus Mar 6 '17 at 2:26
  • $\begingroup$ @YuvalFilmus I've seen the algorithm, but I am unable to find a source that gives an example like the one mentioned. For example, I do not know if id needs to be in the item set, and if the lookahead needs to be determined for id. Any suggestions? $\endgroup$ – Grant Miller Mar 6 '17 at 2:30
  • $\begingroup$ If a computer can perform the algorithm, then a human should be able to. Make sure you understand the algorithm. $\endgroup$ – Yuval Filmus Mar 6 '17 at 3:09
  • $\begingroup$ @YuvalFilmus Any suggestions on a source for an explanation of the algorithm? $\endgroup$ – Grant Miller Mar 6 '17 at 3:12
  • 1
    $\begingroup$ You can find a very nice and easy-to-understand (IMHO) explanation of LALR(1) table construction in Dick Grune & Ceriel Jacobs, A Practical Guide to Parsing Techniques, Chapter 9. While I would definitely recommend the second edition of that book, the first edition is available for free download $\endgroup$ – rici Mar 6 '17 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.