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

中吴南顾惟一笑

成功法则就是那19个字

 
 
 

日志

 
 

[转]ANTLR lexical analysis的一些概念  

2010-06-09 09:41:00|  分类: R&D |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1. Context-Free Grammar:
a).终结符集合
b).非终结符集合
c).产生式集合,产生式左部为一个非终结符,右部为终结符或非终结符序列
d).一个初始状态

2. Parse Tree(Concrete Syntax Tree)/Abstract Syntax Tree(AST)
分析树也称为具体树,抽象语法树不包含具体的文法信息(或形式)

3. Syntax-Directed Translation
Syntax-Directed: 文法符号与一个属性集合关联,产生式与一个语义规则集合关联,文法符号(属性集合)和语义规则集合构成Syntax-Directed定义

4. Nondeterministic finite automata NFA
a). 一个状态的有穷集合S
b). 一个输入符号集合Σ
c). 一个转换函数move,把状态和符号组成的二元组映射到状态集合
d). 状态s0是唯一的初始状态
e). 状态集合F是终止状态集合

5. Deterministic finite automata DFA
DFA是NFA的特例,DFA在任何状态下,对任一输入符号最多只有一个转换
a). 没有一个状态具有ε转换
b). 对每个状态s和输入符号a,最多只有一条标记为a的边离开s

Token与Lexeme区别: Token相当于类型,lexeme相当于不同的实例。例如token为relation,lexeme可能包括<, >, <>, <=, >=等

很多例子中,都是直接在语法文件中嵌入处理代码,这种方式ANTLR称为嵌入式动作(embeded action)。
复杂情况下,需要基于语法树遍历(walking the tree)生成目标代码。embeded action将处理代码跟语法描述混合起来,语法复杂时使语法文件臃肿。另外语法可能经常需要修改,但语法的主要表达式不会变动,将语法识别与转换、生成 (目标代码)等处理分离是有好处的。
所以产生以下概念:
识别(recognize): 前面讲的由语法描述文件生成的词法分析器、语法分析器代码,就是语法识别器(recognizer)。它接受原始输入字符流(类似源代码),进行分析,得到抽象语法树AST。
转换(translate): 我们可以编写一个转换器(translator, tree walker),使用AST作为输入,进行计算处理,或生成目标代码等操作。



http://www.antlr.org/grammar/list中有sql和asn的.g
  评论这张
 
阅读(318)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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