介绍
第二版前言
第一版前言
1.
简介
1.1.
解析技术
1.2.
使用方法
1.3.
内容概要
1.4.
参考文献
2.
语法，发源之地
2.1.
语言，一个无限的集合
2.1.1.
语言
2.1.2.
语法
2.1.3.
无限集带来的问题
2.1.4.
通过有限集描述一门语言
2.2.
形式语法
2.2.1.
形式语法的形式主义
2.2.2.
通过形式语法生成句子
2.2.3.
形式语法的表达力量
2.3.
语法和语言的Chomsky层次结构
2.3.1.
1型语法
2.3.2.
2型语法
2.3.3.
3型语法
2.3.4.
4型语法
2.3.5.
结论
2.4.
用语法生成句子
2.4.1.
短语结构案例
2.4.2.
CS案例
2.4.3.
CF案例
2.5.
收敛或不收敛
2.6.
生成空语言的语法
2.7.
CF和FS语法的限制
2.7.1.
uvwxy理论
2.7.2.
uvw理论
2.8.
作为转换图的CF和FS语法
2.9.
上下文无关语法的健全
2.9.1.
未定义的非终结符
2.9.2.
不可到达的非终结符
2.9.3.
非生成性规则和非终结符
2.9.4.
循环
2.9.5.
清理上下文无关语法
2.10.
设定上下文无关和正则语言的属性
2.11.
语义连接
2.11.1.
属性语法
2.11.2.
转导语法
2.11.3.
增广转换网络
2.12.
语法类型的隐喻比较
2.13.
总结
2.14.
问题
3.
解析简介
3.1.
解析树
3.1.1.
解析树的大小
3.1.2.
各种模糊性
3.1.3.
解析树的线性化
3.2.
解析一个句子的两种方法
3.2.1.
自顶向下解析
3.2.2.
自底向上解析
3.2.3.
适用性
3.3.
非确定型自动机
3.3.1.
构建NDA
3.3.2.
构建控制机制
3.4.
0型到4型语法的识别和解析
3.4.1.
时间要求
3.4.2.
0型和1型语法
3.4.3.
2型语法
3.4.4.
3型语法
3.4.5.
4型语法
3.5.
上下文无关解析方法的概述
3.5.1.
方向性
3.5.2.
搜索技术
3.5.3.
一般定向方法
3.5.4.
线性化方法
3.5.5.
确定性自顶向下和自底向上方法
3.5.6.
非规范方法
3.5.7.
广义线性方法
3.5.8.
总结
3.6.
解析技术的力量
3.7.
解析树的表现形式
3.7.1.
生产者-消费者模型中的解析树
3.7.2.
数据结构模型中的解析树
3.7.3.
解析林
3.7.4.
解析林语法
3.8.
什么时候才是完成了解析呢？
3.9.
传递闭包
3.10.
解析与布尔矩阵乘法的关系
3.11.
总结
3.12.
问题
4.
一般非定向分析
4.1.
Unger解析方法
4.1.1.
不含ε规则和循环的Unger解析方法
4.1.2.
含有ε规则的Unger方法
4.1.3.
从Unger方法中获得解析林语法
4.2.
CYK解析法
4.2.1.
普通CF语法的CYK识别
4.2.2.
Chomsky基本形式语法的CYK识别
4.2.3.
将CF语法转换为Chomsky普通形式
4.2.4.
重访问示例
4.2.5.
Chomsky普通形式的CYK解析
4.2.6.
消除CNF转换的影响
4.2.7.
CYK的简短回顾
4.2.8.
从CYK解析获取解析林语法
4.3.
表解析
4.3.1.
自顶向下表解析
4.3.2.
自底向上表解析
4.4.
结语
4.5.
问题
5.
正则语法与有限状态
5.1.
正则语法的应用
5.1.1.
CF解析中的正则语言
5.1.2.
拥有无限存储的系统
5.1.3.
模式搜索
5.1.4.
SGML和XML验证
5.2.
正则语法的生成物
5.3.
使用正则语法进行解析
5.3.1.
用状态替换集合
5.3.2.
ε转换和非标准符号
5.4.
操作正则语法和正则表达式
5.4.1.
正则表达式产生的正则语法
5.4.2.
来自正则语法的正则表达式
5.5.
正则语言的操作
5.6.
左正则语言
5.7.
最小化有限状态自动机
5.8.
自顶向下正则表达式识别
5.8.1.
识别器
5.8.2.
评价
5.9.
FS系统中的语义
5.10.
使用有限状态自动机快速文本搜索
5.11.
总结
5.12.
问题
6.
有向自顶向下解析
6.1.
仿最左推导
6.2.
下推自动机
6.3.
广度优先自顶向下解析
6.3.1.
一个例子
6.3.2.
一个反例：左递归
6.4.
左递归的消除
6.5.
深度优先（回溯）解析器
6.6.
递归下降
6.6.1.
一个纯粹的方式
6.6.2.
穷举回溯递归下降
6.6.3.
广度优先递归下降
6.7.
有限子句语法
6.7.1.
Prolog
6.7.2.
DCG格式
6.7.3.
获取解析树信息
6.7.4.
运行有限子句语法程序
6.8.
取消解析
6.8.1.
取消集
6.8.2.
转换方案
捐助
Light
Rust
Coal
Navy
Ayu
解析技术
2.3.5 结论
图Fig 2.16的表格总结了在生成一个字符串时会出现的最复杂的数据结构，在相关语法类型中使用到的。参见图Fig 3.15，在解析中获得的相应的数据类型。
