当前位置:首页 > 开发 > 系统架构 > 架构 > 正文

antlr笔记

发表于: 2013-02-19   作者:blackproof   来源:转载   浏览次数:
摘要:                 antlr笔记   antlr的一点笔记,就一点点,还有ll和antlr的一些文档   LL(K)文法 LL文法是自上而下的分析法,从文法的开始符号出发,或是说从树根开始,向下构造语法书,知道建立每个树叶。也叫递归下降分析法。   非确定的自上

                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

 

 

antlr笔记

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
安装配置 需要JRE或者JDK 下载ANTLRWorks: http://www.antlr.org/works/index.html 查看DFA需要使用
目前为止使用的例子中,都是直接在语法文件中嵌入求值处理代码,这种方式ANTLR称为嵌入式动作(embed
前言 这段时间在公司忙的跟狗似的,但忙的是没多少技术含量的活儿。 终于将AST IR和tree grammar过
初次在项目中使用antlr,刚做了第一版,功能很简单(参不多正则都能做╮(╯▽╰)╭) 用antlr做表达
1. 对语法框架结构的整体构思 一方面为了避免过多因素的干扰,另一方面考虑迭代完善过程,在对语法
初次在项目中使用antlr,刚做了第一版,功能很简单(参不多正则都能做╮(╯▽╰)╭) 用antlr做表达
ANTLR3 简介及示例 ANTLR(pronounced Antler) 是一个语言识别工具,Another Tool forLanguage Recog
先从http://www.eclipse.org/downloads/上下载classic版本的Eclipse: 进入http://www.antlr.org/wi
Myeclipse部署工程时,出现antlr.collections.AST.getLine()I错误,原因是Struts 2.1使用了antle-2.7
错误完整表述: Filter execution threw an exception] with root cause java.lang.NoSuchMethodErr
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号