[转]ANTLR lexical analysis的一些概念
2010-06-09 09:41:00| 分类:
R&D
| 标签:
|举报
|字号大中小 订阅
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
评论这张
转发至微博
转发至微博
评论