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.

Improve this question
$\endgroup$
6
  • $\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, 2017 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, 2017 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, 2017 at 3:09
  • $\begingroup$ @YuvalFilmus Any suggestions on a source for an explanation of the algorithm? $\endgroup$
    – Grant Miller
    Mar 6, 2017 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, 2017 at 21:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.