`

ANTLR学习笔记一:概念理解

阅读更多

 

ANTLR学习笔记一:概念理解

 

一、什么是ANTLR。

ANTLR是ANother Tool for Language Recognition的缩写,

意为“另一种语言识别工具”,读作Antler。

它是一种解析器程序的代码生成器(作用类似于YACC),

使用LL(*)方法,即从输入字符串的左到右,

用候选项的最左符号匹配输入(即与所有以终结符开头的候选项匹配),

每次向前(右)看n个符号(好像计算机下棋那样)。

 

二、ANTLR的特点

ANTLR作为一种编译器的制作工具,具有很多有用的功能和特点。

1. 使用语法(.g文件)作为输入,生成语言识别器的代码。

2. 支持生成各种语言的代码(只需修改与实现语言相关的部分)。

3. 自身用Java实现。

4. 使用上下文无关语法。

(即语法的所有产生式/规则的左侧总是非终结符,

简单说就是,一个被识别的非终结符无论放在什么地方,

都可以用已有的方式推导)

5. 语法基于EBNF(扩展的巴科斯范式)。

这意味着,在ANTLR中既可以使用BNF元语言符号

冒号(:)表示推导,

竖线(|)表示或,

也可以使用扩展的元语言符号如

星号(*)表示出现0次或以上。

问号(?)表示出现0次或1次。

加号(+)表示出现1次或以上。

关于EBNF更多介绍可以参考这里:

http://hi.baidu.com/helloweenpad/blog/item/f5b6f701a2694e16738b655e.html

6. 可以生成多种解析器(通过标注来指定),包括:

文法解析器(常用于把符号保存为AST的非线性结构中)。

词法解析器(把输入切割成线性结构的符号)。

树解析器(输入是树结构数据,即AST,抽象语法树)。

组合词法解析器(文法和词法解析同时进行)。

它比同类工具更易于使用。

7. 如果不嵌入源代码,所生成的代码将只检查输入是否可以被识别(即语法检查)。

如果嵌入源代码,可以对识别的语法元素执行相应的动作。

利用嵌入的代码可以获取符号表或中间语言指令(即解析器或编译器)。

8. 丰富的参考资料。官方收集了很多语法源文件。

见http://www.antlr.org/grammar/list

9. 有相关的辅助开发工具和Eclipse插件。

10. 更详细请参考官方网站

http://www.antlr.org/

或英文wiki

http://en.wikipedia.org/wiki/ANTLR

 

三、什么是上下文无关语法和巴科斯范式

ANTLR的语法是基于EBNF的上下文无关语法。

在形式语言的范畴中,上下文无关语法是较弱的文法

(有些语法可以被上下文相关语法描述,

但不能被上下文无关语法描述)。

另外还有更弱的右线性文法(即正则语法)

由于这些特点,普遍使用上下文无关语法来编写计算机语言的

文法解析器(即递归推导),

用更弱的正则语法编写词法解析器来切割符号(即非递归推导)。

在形式上上下文无关语法被写成四元式,即

终结符集合、非终结符集合、(单个)开始符、产生式集合(有限)。

其中非终结符表示可以再分的语法元素,用大写字母表示;

终结符表示不可以再分的元素,用小写字母表示

(有时可以直接写出终结符的字符串内容,或用引号引用,如用-或"-"直接表示减号)

开始符属于非终结符,表示语法推导的开始,一般用S表示。

产生式表示一系列的可选择推导(一般右边个数比左边的个数多)

如果多个产生式的左边相同,可以用竖线(|)合并为一条产生式,

合并后用或分割的符号称为候选式。

巴科斯范式是上下文无关语法的描述语言。

通常只列出产生式和开始符S。

在ANTLR中(习惯上?)词法符号用全大写,文法符号用全小写,

开始符一般放在开头(开始符会变成public方法,被外部程序调用)。

作为终结符的运算符可以用单引号引用,直接写在产生式右边。

 

四、什么是LL(k)

一种递归下降的分析方法。

第一个L表示从左往右。

第二个L表示最左匹配。

k表示向前看k个符号。

所谓向前看,是指向右看k个符号的内容,但不读入。


分享到:
评论
1 楼 ggwang 2014-10-27  
总结得很简练清晰啊,学习了!

相关推荐

    The+Definitive+ANTLR+4+Reference 学习笔记word

    这本书的学习笔记将帮助读者深入理解ANTLR4的工作原理和实践应用。 ANTLR4的核心功能包括: 1. **语法定义**:ANTLR4允许用户使用EBNF(扩展巴科斯范式)来定义语法规则,这是一种形式化的语法描述语言。这些规则...

    The Definitive ANTLR4Reference 学习笔记

    学习ANTLR 4的参考手册时,首先需要了解的是语言、语法、解析树、词法单元和解析器的基本概念。语言由一系列有效句子组成,每个句子包含短语,而短语又由子短语组成。语法是语言的语法规则的正式定义,它指定了子...

    antlr笔记

    这篇笔记主要涵盖了ANTLR的相关知识,结合了“编译原理LL(K).ppt”的内容,我们将深入探讨ANTLR的工作原理以及在源码分析和工具开发中的应用。 ANTLR的工作流程主要包括以下几个步骤: 1. **语法定义**:ANTLR使用...

    CXF webservice初学笔记

    1. **了解基础**:首先要掌握 JAX-WS 和 SOAP 基础,理解 Web 服务的基本概念和工作原理。 2. **安装与配置**:下载并配置 CXF,了解如何在项目中引入 CXF 库。 3. **创建服务**:学习如何使用 CXF 创建 SOAP 或 ...

    编译原理 词法分析器.zip

    - **ANTLR**:一种强大的解析器生成器,支持多种语言,可以生成词法分析器、语法分析器和抽象语法树。 深入学习词法分析器涉及语言学、计算机科学和软件工程等多个领域的知识,有助于提升对编译器和解释器工作的...

    云南大学软件学院编译原理ppt以及相关资料

    国科大的MOOC笔记提供了补充学习资源,可能包括更深入的实例、练习题和编译器构造工具的使用,如ANTLR、Flex和Bison。这些工具可以帮助学生实践编译器设计,理解它们如何工作。 通过这门课程的学习,学生不仅能掌握...

    语法分析器 编译课 计算机学习

    在描述中提到的“该语法分析器在给出一个具体的语法后能自动生成一个C文件的语法器”,这通常指的是使用诸如Yacc(Yet Another Compiler-Compiler)或者ANTLR等工具来实现。这些工具接受一种形式化的文法描述(如...

    Hibernate新手上路

    学习Hibernate,首先要理解这些基本概念和配置,然后逐步掌握实体类的定义、映射文件的编写、会话和事务管理等核心概念。随着经验的积累,你将能够熟练地利用Hibernate来实现数据的持久化操作,从而大大提高开发效率...

    编译原理答案

    文档“近万份大学生能用的资料 [下载地址目录单](173页).doc”可能包含了大量关于编译原理的学习资源,如课件、笔记、习题解答等,对大学生深入理解和应用编译原理非常有帮助。文档中的173页内容可能涵盖了从基础...

    独家! 中国科技大学 陈意云 编译原理全套!课堂ppt,历年考试真题,课程实验讲稿

    压缩包内的文档文件可能是陈意云教授的课程补充资料或学生的学习笔记。例如,"chap1.doc"到"chap6.doc"可能对应课程的六个主要章节,详细阐述了编译原理的各个主题。"contents.doc"可能是课程大纲,列出了每个章节的...

    TigerWorks:佐治亚理工学院 CS4240 的 Tiger 编译器

    通过参与 TigerWorks 项目,学生将深入理解编译器的工作原理,学习如何使用 ANTLR 设计和实现解析器,以及如何进行语义分析、中间代码生成和优化。此外,他们还将学习如何编写测试用例以确保编译器的正确性,这对于...

    Python.rar_Java编程_Python_

    由于压缩包内只有一个名为"Python"的文件,这可能是Python源代码文件、笔记、教程文档或者是与Java语法分析器相关的Python实现。如果是Python代码,可能是一个用Python编写的工具,用于辅助Java语法分析,例如生成...

    编译器-2021-spring

    **编译器基础** 编译器是计算机科学中的核心组件之一,它负责将高级编程语言转换为机器可执行的指令。...学习编译器不仅有助于理解软件开发的底层机制,还能为成为软件工程师、研究员或教育工作者提供坚实的基础。

Global site tag (gtag.js) - Google Analytics