# Intuitive Explanation on Converting BNF Grammar to LR(1)

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.

• Just follow the algorithm. It is really better if you understand the algorithm, but it won't necessarily make it easier to apply it. – Yuval Filmus Mar 6 '17 at 2:26
• @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? – Grant Miller Mar 6 '17 at 2:30
• If a computer can perform the algorithm, then a human should be able to. Make sure you understand the algorithm. – Yuval Filmus Mar 6 '17 at 3:09
• @YuvalFilmus Any suggestions on a source for an explanation of the algorithm? – Grant Miller Mar 6 '17 at 3:12
• 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 – rici Mar 6 '17 at 21:00