注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

中吴南顾惟一笑

成功法则就是那19个字

 
 
 

日志

 
 

LEMON语法分析生成器(LALR(1)类型)源代码情景分析  

2011-01-27 11:41:32|  分类: R&D |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
作    者 虞森林
出 版 社 浙江大学出版社
出版时间 2006年7月

LEMON由Richard Hipp开发,源代码全由C语言编写,只有4000多行,短小精悍。LEMON的执行文件"块头"也很小,只有124K。阅读完它,可以透彻地理解LALR(1)语法分析的工作机理。
LEMON应用于著名的SQLite嵌入式数据库的设计中。正是由于SQLite嵌入式数据库的巨大成功以及源代码的完全开放,Richard Hipp于2005年获得国际IT界著名的Google&O'Reilly开放源码奖
本书的结构安排,以LEMON在main()主函数中执行流为串联主线,在分析过程中,按遇见的顺序,逐个分析阐述每个函数的工作机制,相关的数据结构,以及它们互相之间发生的有机联系。通过介绍函数的逻辑流程及其物理背景乃至代码作者的某些技巧,让读者和笔者一起完成必要的理解和抽象过程,达到全面深入理解LALR(1)语法分析机理的目的。同时,LEMON又是一个工业级的应用软件,用它可以生成精致的LALR(1)类型的语法分析器。


第1章对LEMON进行概略性的介绍,大致相当于LEMON的应用说明书.
第2章通过一个带有变量功能。具有可重载函数的桌面计算器的开发实例,介绍如何应用LEMON来开发应用程序。
第3章分析LEMON如何对命令行中输入的参数进行处理。
第4章阐述LEMON中的各种数据结构以及它们的初始化过程。
第5章为LEMON对语法文件内容进行词法扫描过程的说明,并介绍如何将磁盘上的语法文件转换为机器内存里的各种数据结构。
第6章讲述LEMON为各个语法符号寻得它们的First集并建立优先级的过程。
第7章讨论以何种途径形成LR(0)分析器的各个状态,详细介绍如何建立基本项目(核心项目),如何通过闭包运算获取全部项目,如何通过移进符号的操作来转移状态,和建立各项目的传播链表。
第8章讨论如何通过传播链表寻找各个语法符号的Follow集元素。
第9章阐述LEMON在已有LR(0)分析器的基础上,添加先行符建立LALR(1)分析器的机理和过程。
第10章是本书最重要的部分,讨论了LEMON如何与精心设计的lempar.c模板文件互相配合,最终生成LALR(1)类型语法分析器的C语言版文件。由于LEMON本身是为SQLite嵌入式数据库服务的,而嵌入式软件又要求体积尽可能小,故而LEMON在生成语法分析器时,采取了一系列有助于缩小软件体积的措施和算法。这样得到的语法分析器不仅体积小巧,而且运行速度极快。
第11章非常简要地介绍了由LEMON生成完毕的语法分析器内部的函数调用与数组之间的关系,它们的良好封装性,以及如何删除调试排错功能以获得更小的体积。


详细目录

第1章介绍LEMON
1.1编译原理的由来和发展
1.2LEMON简介
1.3命令行中各个选项
1.4语法分析器的界面和工作过程
1.5与YACC和BISON的不同之处
1.6语法文件的语法
1.7特殊申明符
1.8语法分析过程的错误恢复策略
第2章设计计算器
2.1最简陋计算器
2.2使用自定义的数据类型——结构
2.3语法分析器的状态和动作
2.4语法分析的动作记录
2.5比较完善的计算器
2.6如何释放符号占用的内存空间
2.7具有变量功能的计算器
2.8具有函数功能的计算器
2.9添加带两个参数的函数功能以及让函数能够重载
2.10计算器的全部源代码
第3章处理命令行输入
3.1函数调用关系
3.2内容概述
3.3如何阅读分析LEMON源程序
3.4与命令行有关变量.数组的申明和赋值
3.5命令行选项错误输入时的处理
3.6命令行带参数选项的处理
3.7提示正确参数输入形式
第4章初始化LEMON
4.1函数调用关系
4.2内容概述
4.3LEMON程序的“全局”变量
4.4启用“符号之家”的Strsafe_init函数
4.5启用符号表的Symbol_init函数
4.6符号(symbol)结构
4.7启用状态表的State_init函数
4.8状态(state)数据结构
4.9项目(config)数据结构
4.10产生式(role)数据结构
4.11动作(action)数据结构
4.12一些变量的初始化
4.13装配和安置符号
4.14检测符号的安置
第5章词法扫描和语法要素内部表示
5.1数调用关系
5.2内容概述
5.3词法处理的主角
5.4词法分析专用的数据结构(pstate)
5.5读入整个语法文件
5.6打印出错信息函数
5.7处理条件编译
5.8分析字符流和裁成记号流
5.9记号的语法分析
5.10文法符号计数排序
5.11重现语法文件
第6章符号的First集
6.1函数调用关系
6.2内容概述
6.3计算优先级
6.4找出符号的First集
第7章计算LR(0)分析器
7.1函数调用关系
7.2内容概述
7.3计算LR(0)分析器的主角
7.4项目表的初始化
7.5确认开始符号
7.6计算第一状态的基本项目集
7.7寻找LR(0)分析器第一个状态
7.8基本项目的闭包运算
7.9项目传播链表
7.10建立第一状态
7.11寻找LR(0)的所有状疮
第8章符号的Follow集
8.1函数调用关系
8.2内容概述
8.3颠倒项目传播链的次序
8.4找出符号的Follow集
第9章计算LALR(1)分析器
9.1数调用关系
9.2内容概述
9.3装配动作链表
9.4压缩动作链表
9.5报告动作链表
第10章生成LALR(1)语法分析器
10.1函数调用关系
10.2内容概述
10.3生成语法分析器的主角
10.4“转运承载”数据结构(acttab)
10.5模板文件
10.6从模板文件中拷贝代码
10.7头文件
10.8定义分析器中各种数据类型
10.9维数组线性化和压缩
10.10计算和生成动作数组
10.11输出语法分析器的各数组
10.12移进归约和接受的操作处理
10.13产生式文法符号向语法分析栈元素的转换
10.14出错与接受的操作处理
10.15语法分析器动作分析
10.16打印头文件和显示处理结果
第11章语法分析器的一些特性
11.1语法分析器中函数和数组调用关系
11.2语法分析器的封装性
11.3条件编译语句块
  评论这张
 
阅读(764)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017