4.7.6 Compaction of LR Parsing Tables

A typical programming language grammar with 50 to 100 terminals and 100 productions may have an LALR parsing table with several hundred states. The action function may easily have 20,000 entries, each requiring at least 8 bits to encode. On small devices, a more efficient encoding than a two-dimensional array may be important. We shall mention briefly a few techniques that have been used to compress the ACTION and GOTO fields of an LR parsing table.

One useful technique for compacting the action field is to recognize that usually many rows of the action table are identical. For example, in Fig. 4.42, states 0 and 3 have identical action entries, and so do 2 and 6. We can therefore save considerable space, at little cost in time, if we create a pointer for each state into a one-dimensional array. Pointers for states with the same actions point to the same location. To access information from this array, we assign each terminal a number from zero to one less than the number of terminals, and we use this integer as an offset from the pointer value for each state. In a given state, the parsing action for the ith terminal will be found i locations past the pointer value for that state.

Further space efficiency can be achieved at the expense of a somewhat slower parser by creating a list for the actions of each state. The list consists of (terminal-symbol, action) pairs. The most frequent action for a state can be placed at the end of the list, and in place of a terminal we may use the notation “any,” meaning that if the current input symbol has not been found so far on the list, we should do that action no matter what the input is. Moreover, error entries can safely be replaced by reduce actions, for further uniformity along a row. The errors will be detected later, before a shift move.

Example 4.65: Consider the parsing table of Fig. 4.37. First, note that the actions for states 0, 4, 6, and 7 agree. We can represent them all by the list

SYMBOL

ACTION

id

s5

(

s4

any

error

State 1 has a similar list:

SYMBOL

ACTION

+

s6

$

acc

any

error

In state 2, we can replace the error entries by r2, so reduction by production 2 will occur on any input but *. Thus the list for state 2 is

SYMBOL

ACTION

*

s7

any

r2

State 3 has only error and r4 entries. We can replace the former by the latter, so the list for state 3 consists of only the pair (any, r4). States 5, 10, and 11 can be treated similarly. The list for state 8 is

SYMBOL

ACTION

+

s6

)

s11

any

error

and for state 9

SYMBOL

ACTION

*

S7

any

R1

We can also encode the GOTO table by a list, but here it app ears more efficient to make a list of pairs for each nonterminal A. Each pair on the list for A is of the form (currentState, nextState), indicating

GOTO [currentState, A] = nextState

This technique is useful because there tend to be rather few states in any one column of the GOTO table. The reason is that the GOTO on nonterminal A can only be a state derivable from a set of items in which some items have A immediately to the left of a dot. No set has items with X and Y immediately to the left of a dot if X ≠ Y. Thus, each state app ears in at most one GOTO column.

For more space reduction, we note that the error entries in the goto table are never consulted. We can therefore replace each error entry by the most common non-error entry in its column. This entry becomes the default; it is represented in the list for each column by one pair with any in place of currentState.

Example 4.66: Consider Fig. 4.37 again. The column for F has entry 10 for state 7, and all other entries are either 3 or error. We may replace error by 3 and create for column F the list

CURRENTSTATE

NEXTSTATE

7

10

any

3

Similarly, a suitable list for column T is

CURRENTSTATE

NEXTSTATE

6

9

any

2

For column E we may choose either 1 or 8 to be the default; two entries are necessary in either case. For example, we might create for column E the list

CURRENTSTATE

NEXTSTATE

4

8

any

1

This space savings in these small examples may be misleading, because the total number of entries in the lists created in this example and the previous one together with the pointers from states to action lists and from nonterminals to next-state lists, result in unimpressive space savings over the matrix implementation of Fig. 4.37. For practical grammars, the space needed for the list representation is typically less than ten percent of that needed for the matrix representation. The table-compression methods for finite automata that were discussed in Section 3.9.8 can also be used to represent LR parsing tables.

最新文章

  1. 白皮 Chapter 2
  2. .net String.Format数字格式化输出
  3. 连接mysql遇到的问题
  4. Spring @PostConstruct and @PreDestroy example
  5. 光环国际的PRINCE2培训时间
  6. python中的printf:%号拼接字符串和format函数
  7. Openstack: change endpoint IP addresses after installation
  8. 2018-2019-2 网络对抗技术 20165321 Exp3 免杀原理与实践
  9. 爬微信好友签名和QQ好友签名
  10. .net Core使用Orcle官方驱动连接数据库
  11. centos7 mongodb安装
  12. 关于react-native项目在MacBookPro环境下打包成IPA
  13. 将python代码打包成一个app/exe
  14. EntityFramework Code-First 简易教程(十一)-------从已存在的数据库中映射出表
  15. 收藏:Win32消息机制
  16. JAVA-JSP隐式对象
  17. jq 监听input值的变化
  18. 让你看不懂的swift语法
  19. iOS开发小技巧--定义宏和pch文件的使用
  20. 78、WebClient实现上传下载 System.Net、System.Uri类

热门文章

  1. nodejs学习(一) ---- nodejs + express应用生成器 快速创建应用
  2. 零基础入门Python数据分析,只需要看懂这一张图,附下载链接!
  3. dsu+树链剖分+树分治
  4. 下载Spring4.1.x源码并用IntelliJ IDEA打开-----
  5. JavaEE JDBC 可滚动和可更新的结果集ResultSet
  6. table 设置自动宽度后 td 的固定宽度 在 谷歌浏览器自动拉伸
  7. [K3Cloud] QueryService使用注意事项
  8. 关于android系统启动不同activity默认过渡动画不同的一些认识
  9. 真--可并堆模板--BZOJ2333: [SCOI2011]棘手的操作
  10. linux ftp服务器搭建