ANTLR3完全参考指南读书笔记[02]

前言

程序语言是什么?
用wiki上的描述,程序语言是一种人工设计的语言,用于通过指令与机器交互;程序语言是编程程序的标记,而程序是一种计算或算法的描述。详细介绍和背景信息参考:
Programming_language(http://en.wikipedia.org/wiki/Programming_language)
Programming_language_generations(http://en.wikipedia.org/wiki/Programming_language_generations)  
History_of_programming_languages(http://en.wikipedia.org/wiki/History_of_programming_languages)。
 
那如何确定程序语言是合法的(well-formed)呢?
识别器(reccognizer)!
 
大家都这么懒,有什么简单的方法能自动生成程序语言?
工具早被视为不是银弹了,不过像eclipse EMF、PD等建模工具提供了代码生成(code generation)功能。
但是如果想像一些开源软件,暴露出xml格式的配置文件,根据这些配置文件再做一些逻辑处理,这时需要解析xml文件;进一步,如果定义了自己的内部数据格式,每次使用时都得解析;再进一步,在数据格式中融入可变的逻辑操作,实现解析功能的代码恐怕没有那么简单了。
直观的感觉,只要有格式,冥冥之中总会存在能够描述这种格式的方法,文法/语法是很好的候选者。
那这好像跳入了编译原理这个大坑里,幸好有了Parr的工作。
 
内容
状态机(statemachine)/确定有限自动机deterministic finite automation, DFA)
句子的树结构
语言的歧义(ambiguous):文法所无法描述的语言特征:短语上下文依赖(context dependency)、短语优先级(precedence)
 
1 自动机
如当前法国人尝试用固定的方程描述上帝所做的一切一样,面对问题时,人们总是期望可以通过建模,在有限步骤内解决。
状态机可以用于生成语句吗?Parr举了个简单英文语句生成状态机的例子:(该图用graphviz(http://www.graphviz.org/)重新生成)
ANTLR3完全参考指南读书笔记[02]
这是一个DFA。
 
但同法国人的失败一样,状态机不能避免生成不符合某种规范/约束要求的语句的情况,例如my truck is sad;Parr指出其原因有:语法中表达不出含义,句中短语可能存在依赖和顺序关系。
 
通过状态机生成的语言称为正则语言(regualr languages),状态机在生成语言发面的缺陷的本质在于它无记忆,即无法记住它之前生成过什么。
 
2 树
树作为一种数据结构的抽象,在计算机科学中扮演着很重要的角色,以至于在遇到需要存在嵌套和顺序关系时,IT从业者总会想到树。
树在生成语句时称为推导树(derivation tree),而在识别语句时称为解析树(parse tree)。下图是文中给出的赋值语句的树结构示例:
ANTLR3完全参考指南读书笔记[02]

从分治策略(divide and conquer)角度看,这些箭头都可以理解为方法的调用,自然而然的可以在状态机基础上添加方法调用和返回功能。

 
那如何在状态机中添加记忆功能呢?栈(stack)!
就跟方法调用一样,参数和方法返回地址等信息用栈保存是极便利的。这点在Java虚拟机规范中的每个方法对应一个stack frame可以说明这一点。
加了栈的状态机成为自顶向下状态机(pushdown automation)。
 
这个语法图又是什么?
ANTLR3完全参考指南读书笔记[02]

恩,也是一个状态机,好高端的样子,在Oracle SQL官方文档中也可以看到。

该语法规则是递归的,幸运的是它不是左递归的。关于左递归,看看下面的Java代码片段:
void expr(){
expr();
otherMethod();
}
一旦调用,时间或长或短,JVM绝对会报*Error,在适当配置VM运行参数的情况下,吐出点东西来,作为诅咒你的证据。
 
3 语言结构的歧义
程序语言的歧义是指,在语法图中,一个句子可以用多条路径生成。举个例子:3+4×5,是该解释为(3+4)×5还是3+(4×5)。
ANTLR3提供了谓词用于解决歧义问题:表达规则间优先级的语法谓词(syntactic predicate)和作为语言结构识别运行时布尔开关的语义谓词(semantic predicate)。这点在后面的笔记中再做记录。
 
 
上一篇:PostgreSQL的 initdb 源代码分析之十六


下一篇:【SVM】周志华