Algorithms for Compiler Design: DATA STRUCTURES FOR REPRESENTING PARSING TABLES

Since there are only a few entries in the goto table, separate data structures must be used for the action table and the goto table. These data structures are described below.

Representing the Action Table

One of the simplest ways to represent the action table is to use a two-dimensional array. But since many rows of the action table are identical, we can save considerable space (and expend a negligible cost in processing time) by creating an array of pointers for each state. Then, pointers for states with the same actions will point to the same location, as shown in Figure 1.

Figure 1: States with actions in common point to the same location via an array.

To access information, we assign each terminal a number from zero to one less than the number of terminals. We use this integer as an offset from the pointer value for each state. Further reduction in the space is possible at the expense of speed by creating a list of actions for each state. Each node on a list will be comprised of a terminal symbol and the action for that terminal symbol. It is here that the most frequent actions, like error actions, can be appended at the end of the list.

Figure 2: List that incorporates the ability to append actions.

Representing the GOTO Table

An efficient way to represent the goto table is to make a list of pairs for each nonterminal A. Each pair is of the form:

• goto(current-state, A) = next-state

Since the error entries in the goto table are never consulted, we can replace each error entry by the most common nonerror entry in its column is represented by any in place of current-state.