antlr笔记
jinvasshole 2013-02-19
antlr笔记
antlr的一点笔记，就一点点，还有ll和antlr的一些文档
LL(K)文法
LL文法是自上而下的分析法，从文法的开始符号出发，或是说从树根开始，向下构造语法书，知道建立每个树叶。也叫递归下降分析法。
非确定的自上而下：
ll本质上就是从特定的文法符号开始进行穷举，直到找到匹配的字符串（合法输入）或穷举结束（不合法输入）。
ll的每一步都是对当前句型的最左非终端(通常是表达始终的大写字母),当有多个符号时，就只能逐个尝试，在尝试失败时，当然会回溯到原先字符串，故称带回溯的分析方法。效率低。
非确定的下推自动机：
输入字符串，读头，有穷状态自动机，先进后出下推栈。本质是输入后使得状态机到达某个状态
ll文法如何消除左递归：
1.用扩展的BNF巴科斯范式
用{}表示出现0~n次
用[]表示出现0或1次
用()表示隔离公共因子A->x(y|w|..|z)
2.直接改写，消除左递归
一句U → UxIy
改为U → yU1
U1 → xU1|null
LL(k)文法是上下文无关文法的一个真子集
LL(k)文法也是允许采用确定的从左至右扫描(输入串)和自上而下分析技术的最大一类文法。
LR文法是自下而上的分析法，从给定的输入串开始，或是说从语法书的末端开始，向上规约，直至根节点。也叫算符优先分析法
Antlr笔记
符号 ^ !
我们的识别器, CalcParser, 通过如下的代码来定义：
class CalcParser extends Parser；
options { buildAST = true； // // 默认使用 CommonAST }
expr: mexpr (PLUS^ mexpr)* SEMI! ；
mexpr : atom (STAR^ atom)* ；
atom: INT ；
PLUS和STAR记号是操作符，因此把它们作为子树的根结点，在它们后面注释上字符'^'。SEMI记号后缀有字符'!'，表明它不应该被加入到树中。Antlr语法规则
class MyParser extends Parser 是识别器，生成语法树
默认生成树的规则都是小写如：
expr: mexpr (PLUS^ mexpr)* SEMI! ； mexpr : atom (STAR^ atom)* ； atom: INT ；
Class MyLexer extends Lexer 是词法分析器，分割输入语句
默认这些token都是大写，如：
WS : (' ' | '\t' | '\n'
| '\r') { _ttype = Token。SKIP； } ；
LPAREN: '(' ； RPAREN: ')' ；
STAR: '*' ；
PLUS: '+' ；
SEMI: '；' ；
INT : ('0'..'9')+ ； 其中 fragment XXX 不能作为独立的token，只能被嵌入到token中，相当于宏
如：
fragment EscapeSequence : '\\' ( 'n' | 'r' | 't' | '\'' | '\\' | UnicodeEscape ) ;
Class MyTressWalker extends TreeParser 树的解析器
expr : #(PLUS expr expr) //PLUS为根结点，两个expr分别为左右子结点 | #(STAR expr expr) | INT ；
可以嵌入action
expr returns [int r] {
int a,b； r=0；
}
:
#(PLUS a=expr b=expr) {r = a+b；}
| #(STAR a=expr b=expr) {r = a*b；}
| i:INT {r = Integer.parseInt(i.getText())；}；语法规则笔记：
(...)
子规则
(...)*
闭包子规则（零和多个）
(...)+
正闭包子规则（一个和多个）
(...)?
可选（零个和一个）
{...}
语义动作（action）
[...]
规则参数
{...}?
语义谓词
(...)=>
语法谓词
|
可选符
..
范围符
~
非
.
通配符
=
赋值
:
标号符, 规则开始
；
规则结束
<...>
元素选项
class
语法类
extends
指定语法基类
returns
指定规则返回类型
options
options 段
tokens
tokens 段
header
header 段
tokens
token 定义段token
option
在rule中，^表示将token作为子跟节点，如下，把pow作为powerExpression的跟节点
powerExpression : unaryExpression ( POW^ unaryExpression )* ;
->表示不直接生成代码，这是为了生成语言的扩展，如下，
在ast树种会生成子树，以下的例子就是cellgroup为根，cell logicalExpression为子节点
cellGroup
: CELL'{' logicalExpression? '}' -> ^(CELLGROUP CELL logicalExpression?)
;如果直接写：
cellGroup
: CELL'{' logicalExpression? '}'
{
System.out.println("CELLGROUP " + "CELL " + logicalExpression != null ? logicalExpression.toString() : "NULL");
}
;感谢 http://www.cnblogs.com/vowei/archive/2012/12/29/2839286.html
