Implementation of LR Parsing Tables

LR Parsing Tables are a two-dimensional array in which each entry represents an Action or goto entry. A programming language grammar having a large number of productions has a large number of states or items, i.e.,I₀, I₁ … … I_n.

So, due to more states, more Actions & goto entries will be filled, which requires a lot of memory. So, a two-dimensional array is not sufficient to store so many action entries, because each entry requires at least 8 bits to encode.

So, we have to use more efficient encoding than a two-dimensional array for encoding, Action & goto field.

For example, consider the Grammar.

E → E + T

E → T

T → T * F

T → (F)

F → (E)

F → id

Its Parsing Table will be

Encoding Action Field

Some rows of the Action Table are identical, i.e., they have the same action entries. Therefore, it can store multiple spaces by generating a pointer for each state into a one-dimensional array.

To access entries from an array, we can assign each terminal a sequence-wise number from 0 to n-1. This integer can be used as an offset to access a particular terminal. The space effectiveness can be managed by creating a list of pa_irs.

In the given Parsing Table, states 0, 4, 6, 7 have the same Action entries. They can be represented as

State 1 has the list.

In state 2, if it can replace error entries by r2. So, r2 will occur on all entries except on *.

State 3 − It has only r4 entries & error entries. If it can replace error entries by r4 also, then all entries will be represented by r4.

State 5, 10, 11 can be solved similarly.

State 8

State 9

Encoding goto Field

goto table can also be encoded by a list. List consist of a pa_ir (Current state, Next state)

∴ Goto [Current state, A] = Next State

Column F − Column F has 10 for state 7, and all other entries are either 3 or error. We can replace the error by 3.

Column T

In Column E, we can choose 1 or 8 to be the default.

So ma_inta_ining these lists will be obviously will save some space, i.e., almost 10 % less space will be taken as was taken earlier. These lists take a s_mall amount of memory. But list Representation is slower than matrix Representation.