一本厚厚的305页的书,我实在是不可能都抄在这里的。只能拣最紧要的抄出来。而这个紧要的判断,也是以我在读书的过程中的理解为准,最困难的部分,自己总是想不清楚的部分,我就认为是最紧要的了。今天打算抄的是LL与LR的概念。在我看到的很多关于编译原理的书中,都会反复出现LL(1),LR(1)这样的东西,这究竟是什么概念呢?
我们这次从第72页开始抄起:
4.1 语法分析综述
4.1.1 语法分析程序的功能
语法分析(Syntax Analysis)是编译程序的核心部分。编译程序在完成了词法分析之后,就进入语法分析阶段。语法分析的任务是,按照语言既定的语法规则,对字符串形式的源程序进行语法检查,并识别出相应的语法成分。按照第三章所述的词法分析程序模型,语法分析程序处理的对象是从词法分析器输出的属性字流形式的源程序,它的处理依据是语言的文法规则,其分析结果是识别出的无语法错误的语法成分,可以用语法树的形式来表示。
程序设计语言作为一般形式语言的特例,语法分析的关键是句型识别问题。语法分析程序要解决的问题是:
设给定文法G和字符串(句子) α(α∈VT*),检查、判定α∈L(G)?即检查、判定α是否是文法G所能产生的合法的句子,同时检查和处理语法错误。
图4.1示出语法分析器的作用及在编译程序中的位置。
将完成语法分析任务的程序称为语法分析程序,也称为语法分析器或简称分析器。
4.1.2语法分析方法
语法分析的方法多种多样,每种方法的具体实现技术更是五花八门。综合语法分析的力析途径即产生分析树的方向而言,通常将语法分析方法分为两大类,即自上而下分析与自下而上分析:
自上而下的分析方法.实际上是一种产生的方法,面向目标的方法。分析过程是一个推导过程。
自下而上方法是一种辨认方法,分析过程是归约过程。
1.自上而下分析方法
给定文汇G和源程序串$,则自上而下分析是:从G的开始符号S出发,通过反复使用产生式,逐步推导得到$,则可以确认$是文法G的合法句子。
例4.1 设有文法G和输入串$
G:S→aA|a
A→BaA|ε
B→+|-|*|,
$:a*a+a
对输入串$有如下推导过程和相应的语法树的构造如图4.2所示。
推导过程:
S=>aA=>aBaA=>a*aA=>a*aBaA=>a*a+aA=>a*a+a=$
语法树的从左到右叶结点=$,则$∈L(G)。
由例4.1可见,自上而下分析的实质是,按照对输入串的扫描顺序,从文法G的开始符号S出发,通过反复使用产生式对句子中非终结符进行替换,为其建立最左推导,即选择合适的产生式进行推导,逐步使推导结果与$匹配。同样,一个句子的推导过程可以表示成一棵语法树。自上而下分析就是以文法G的开始符号为树的根结点,从此根结点出发,对任何输入字符朗,试图用一切可能的办法,自上而下地为其建立一棵语法树。
2.自下而上分析方法
所谓自下而上分析法,就是从给定的输入串$开始,不断寻找于串与文法G中某个产生式P的候选式进行匹配,并用P的左部代替之。
例4.2 设有文法G和输入串$
G:S→aAb|a|b
A→+|-|*|,
$:a*b
自下而上分析的过程也可以表示成语法树的生成过程。对输入串$逐步进行归约的过程及其对应的语法树的生长过程如图4.3所示。
(未完待续)
分享到:
相关推荐
这本书《The Definitive ANTLR 4 Reference》是ANTLR 4的主要作者Terence Parr的著作,被誉为学习ANTLR 4的权威指南。书中详细介绍了ANTLR 4的设计理念、工作原理以及如何使用ANTLR 4来构建解析器和词法分析器。以下...
从标题“Definitive ANTLR 4 Reference”和描述“ANTLR 4的权威参考”可以看出,这本书详细介绍了ANTLR 4的所有核心功能和特性,是学习和使用ANTLR 4的重要资源。 ANTLR 4的主要特点包括: 1. **高级语法定义**:...
Java Antlr 4 是一个...开发者可以通过研究这些示例,学习如何定义和使用 Antlr 4 语法,从而创建自己的语言解析工具或进行语言分析任务。同时,这个资源也可以作为参考,帮助解决在使用 Antlr 4 过程中遇到的问题。
py3antlr4book, 隐藏ANTLR4图书源代码到Python3版本 py3antlr4book隐藏ANTLR4图书源代码到 python 3版本。如何使用( Windows )安装 python安装 antlr4 python3运行时 pip install antlr4-python
在编译原理的学习中,ANTLR4扮演了核心角色。编译器是将高级语言转换为机器语言的程序,这一过程分为词法分析、语法分析、语义分析和代码生成四个主要阶段。ANTLR4主要用于语法分析阶段,它通过解析源代码的语法结构...
学习ANTLR 4的参考手册时,首先需要了解的是语言、语法、解析树、词法单元和解析器的基本概念。语言由一系列有效句子组成,每个句子包含短语,而短语又由子短语组成。语法是语言的语法规则的正式定义,它指定了子...
书中不仅有清晰的写作和轻松愉快的风格,而且提供了从设计语法到利用输出的每一步过程的详细解释,结合了实用的示例,使其成为学习ANTLR 4的必备参考书。 ANTLR 4在实际应用中表现出色,例如Twitter公司就使用ANTLR...
ANTLR4是一种强大的解析器生成器,广泛用于构建语言、工具和框架。它能够读取、处理、执行或翻译结构化文本或二进制文件。在本项目“基于ANTLR4的CMM语言编译器”中,开发人员使用ANTLR4来创建了一个针对CMM(可能是...
这意味着它可以安装到IntelliJ IDEA中,为用户提供ANTLR 4的支持。安装步骤通常包括解压缩文件,将解压后的文件夹移动到IntelliJ IDEA的plugins目录下,然后重启IDE以加载插件。 在使用ANTLR Intellij Plugin的过程...
通过本章的学习,我们了解到ANTLR4提供的两种强大工具——解析树监听器和访问者模式,可以帮助我们将特定于应用程序的代码与语法解耦,从而提高代码的可维护性和可复用性。无论是通过监听器响应规则事件还是通过访问...
antlr4权威指南中文版,原书作者terence Parr,清晰版本
赠送jar包:antlr4-runtime-4.2.jar; 赠送原API文档:antlr4-runtime-4.2-javadoc.jar; 赠送源代码:antlr4-runtime-4.2-sources.jar; 赠送Maven依赖信息文件:antlr4-runtime-4.2.pom; 包含翻译后的API文档:...
总的来说,《The Definitive ANTLR 4 Reference》是一本详尽的ANTLR4参考书,对于那些希望利用ANTLR4进行语言解析和工具开发的人来说,这是一份宝贵的资源。通过学习笔记,读者不仅可以了解ANTLR4的基本概念,还能...
1. **学习Antlr4**:理解其工作原理,包括如何定义语法规则,如何生成词法分析器和解析器,以及如何使用它们解析SQL语句。 2. **研究Hive SQL语法**:熟悉Hive SQL的特性和与标准SQL的不同之处,例如Hive的JOIN操作...
书中包含了多位行业专家的评论和推荐,如Martin Fowler、Bob McWhirter、Neal Gafter等,他们从各自领域的角度分享了ANTLR3的应用经验和见解,为读者提供了多维度的学习参考。 ### 职业发展与技能提升 手册强调了...
学习ANTLR4的过程中,理解如何定义语法规则、生成解析器和词法分析器,以及如何在代码中使用它们是关键步骤。ANTLR4还提供了丰富的错误处理机制,可以帮助你在解析失败时提供有用的反馈。 通过这个简单的"hello ...
总之,深入学习ANTLR4的源码,不仅可以帮助我们成为ANTLR4的专家,也能加深对解析理论、编译器构造和语言设计的理解。这是一项有价值且富有挑战性的任务,对于任何从事相关领域工作的人来说都是一个宝贵的资源。