Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >ANTLR4互左递归文法

ANTLR4互左递归文法
EN

Stack Overflow用户
提问于 2017-01-21 22:44:54
回答 1查看 703关注 0票数 2

我在StackOverflow上读过许多关于LL(k)解析器中的互左递归问题的问题。我找到了删除左递归的通用算法:

代码语言:javascript
运行
AI代码解释
复制
A : Aa | b ;

变成了

代码语言:javascript
运行
AI代码解释
复制
A : bR ;
R : (aA)? ;

然而,我想不出如何将它应用于我的情况。我有过

代码语言:javascript
运行
AI代码解释
复制
left_exp: IDENT | exp DOT IDENT ;
exp     : handful
        | of
        | other rules
        | left_exp ;  

“少数其他规则”都包含有规律的递归,如exp : exp PLUS exp等,没有任何问题。问题在于left_expexp是相互递归的。

我考虑将IDENTexp DOT IDENT添加到exp规则中,但在某些情况下,其他有效的exp规则不适用,left_exp将是有效的。

编辑

我还有下面的规则,它要求一个左表达式,然后是赋值。

代码语言:javascript
运行
AI代码解释
复制
assign_statement: left_exp ( COLON IDENT )? EQUAL exp SEMI ;

因为正则表达式如果后面跟着DOT IDENT,那么它只是一个左表达式,所以我似乎不能仅仅添加

代码语言:javascript
运行
AI代码解释
复制
| IDENT
| exp DOT IDENT

对于我的表达式定义,因为赋值将接受左边的任何其他有效表达式,而不是仅接受这两个表达式中的一个。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2017-01-22 01:00:01

我采用的方法通常是这样的:

代码语言:javascript
运行
AI代码解释
复制
A: Aa | b;

变成:

代码语言:javascript
运行
AI代码解释
复制
A: b (a)*;

或者一般情况下:所有没有左递归的all,以及所有具有(已删除的)左递归且无限制发生的all (通过kleene运算符表示)。示例:

代码语言:javascript
运行
AI代码解释
复制
A: Aa | Ab | c | d | Ae;

变成:

A:(c __( d) ) (a _B_ e)*;

您可以通过连续替换A来轻松地检查这一点:

代码语言:javascript
运行
AI代码解释
复制
A: Aa | b;
A: (Aa | b)a | b;
A: Aaa | ba | b;
A: (Aa | b)aa | ba | b;
A: Aaaa | baa | ba | b;

等。

然而,在您的示例中,有一个间接的左递归(通过2条规则)。ANTLR不接受这一点。一个解决方案是将alts从left_exp移到exp规则,然后应用我前面描述的算法。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/41788100

复制
相关文章
消除文法的左递归
其中,β是不以P开头的符号串。那么,我们可以把P的规则改写为如下的非直接左递归形式:
里克贝斯
2021/05/21
4.1K0
消除文法的左递归
编译原理文法详解_编译原理为什么存在递归文法
学完了词法分析,我们知道词法分析器将正则表达式转换成词法单元流,但对于这个记号流我们不知道是否能由正确的文法产生,因此我们需要通过语法分析器来检测其合法性。语法分析器的输出是一棵语法分析树(无论显性还是隐性),并且进行一些语法纠错处理。语法分析的整个过程大概就是我们先定义一个语法,再用相应的算法来检测我们的词法单元流是否符合该语法。这里主要讨论上下文无关文法构成的语法和自顶向下、自底向上的语法分析。
全栈程序员站长
2022/11/17
7760
编译原理文法详解_编译原理为什么存在递归文法
LL(1)文法--递归下降程序
递归下降程序一般是针对某一个文法的。而递归下降的预测分析是为每一个非终结符号写一个分析过程,由于文法本身是递归的,所以这些过程也是递归的。 以上是前提。
Enterprise_
2019/02/20
1.1K0
66. 精读《手写 SQL 编译器 - 语法分析》
自顶而下一般采用递归下降方式处理,称为 LL(k),第一个 L 是指从左到右分析,第二个 L 指从左开始推导,k 是指超前查看的数量,如果实现了回溯功能,k 就是无限大的,所以带有回溯功能的 LL(k) 几乎是最强大的。LL 系列一般分为 LL(0)、LL(1)、LL(k)、LL(∞)。
黄子毅
2022/03/14
1.5K0
66. 精读《手写 SQL 编译器 - 语法分析》
打破国外垄断,开发中国人自己的编程语言(1):编写解析表达式的计算器
本文是《打破国外垄断,开发中国人自己的编程语言》系列文章的第1篇。本系列文章的主要目的是教大家学会如何从零开始设计一种编程语言(marvel语言),并使用marvel语言开发一些真实的项目,如移动App、Web应用等。marvel语言可以通过下面3种方式运行:
蒙娜丽宁
2020/07/30
2.4K1
打破国外垄断,开发中国人自己的编程语言(1):编写解析表达式的计算器
LeetCode 404. 左叶子之和(递归)
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/sum-of-left-leaves 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Michael阿明
2020/07/13
3190
LeetCode 404. 左叶子之和(递归)
递归下降实现LL(1)文法分析C语言与Python实现
对文法G的句子进行确定的自顶向下语法分析的充分必要条件是,G的任意两个具有相同左部的产生式A—>α|β 满足下列条件:
里克贝斯
2021/05/21
1.1K0
递归下降实现LL(1)文法分析C语言与Python实现
自顶向下分析:解决回溯及无限循环问题
当我们尝试使用E -> E + TE \Rightarrow E + T,最终导致无限循环。
灯珑LoGin
2023/10/18
4660
自顶向下分析:解决回溯及无限循环问题
浅尝antlr4
这次使用antlr的诱因是whosbug中使用的ctags(另一个语法分析器)只对c系语言支持较好,对java等语言的支持欠佳(甚至可以说很差了),为了whosbug的鲁棒性我认为还是有必要换一个语法分析器的
Kevinello
2022/08/19
1.8K0
浅尝antlr4
Antlr4 语法解析器(下)
Antlr4 的两种AST遍历方式:Visitor方式 和 Listener方式。
awwewwbbb
2021/07/16
3.6K0
Antlr4  语法解析器(下)
65.精读《手写 SQL 编译器 - 文法介绍》
我们将一块语法规则称为 产生式,使用 “Left → Right” 表示任意产生式,用 “Left => Right” 表示产生式的推导过程,比如对于产生式:
黄子毅
2022/03/14
5720
第四章 自顶向下语法分析方法
基本方法:对任何输入串,试图从文法的开始符号出发, 自上而下地为输入串建立一棵语法树,或者说为输入串寻找一个最左推导。
Here_SDUT
2022/09/09
1.3K0
第四章 自顶向下语法分析方法
Antlr4实战:统一SQL路由多引擎
ANTLR是一款功能强大的语法分析器生成器,可用来读取、处理、执行和转换结构化文本或二进制文件。它被广泛应用于学术界和工业界构建各种语言、工具和框架。Antlr在Hadoop整个生态系统应用较为广泛,如Hive 词法文件是Antlr3写的;Presto词法文件也Antlr4实现的;SparkSQL词法文件是用Presto的词法文件改写的;还有HBase的访问客户端Phoenix也用Antlr工具进行SQL解析的等等。
用户7600169
2022/04/25
10.1K1
Antlr4实战:统一SQL路由多引擎
编译原理学习笔记-5:自顶向下语法分析
在词法分析中,我们扫描输入源程序的每个字符,得到多种类型的单词(token),一系列的单词就构成了一条单词流。可以设想,单词流的某个部分有多个并排的单词,它们可能会构成某个句子,但是这个句子是否真的符合语法规则呢?我们需要借助语法分析器才能进行判断。更直接点,我们可以说语法分析器是用来判断句子是否符合某个给定的上下文无关文法的。
Chor
2020/05/12
5.2K2
Java递归下降分析器_递归下降语法分析器[通俗易懂]
用java语言编写的递归下降语法分析器,是一种适合手写语法编译器的方法,且非常简单。递归下降法对语言所用的文法有一些限制,但递归下降是现阶段主流的语法分析方法,因为它可以由开发人员高度控制,在提供错误信息方面也很有优势。就连微软C#官方的编译器也是手写而成的递归下降语法分析器。
全栈程序员站长
2022/09/07
1.2K0
语法分析
code-child
2023/05/30
3040
语法分析
文法和语言
∑0\sum0∑0={ε} (∑)n(\sum)^n(∑)n={(∑)n−1∑(\sum) ^{n-1}\sum(∑)n−1∑} 例如:{0,1}的3次方={0,1}{0,1}{0,1}={000,001,010,011,100,101,110,111} 字母表中的n次幂:长度为n的符号串构成的集合
code-child
2023/05/30
3310
文法和语言
antlr4入门篇
ANTLR实际上有两件事:一种将您的语法转换为Java(或其他目标语言)的解析器/词法分析器的工具,以及生成的解析器/词法分析器所需的运行时。即使您使用ANTLR Intellij插件或ANTLRWorks来运行ANTLR工具,生成的代码仍将需要运行时库。
山行AI
2020/08/18
4.4K0
antlr4入门篇
Antlr4的相关用法
ANTLR (ANother Tool for Language Recognition) 是一个强大的解析器的生成器,可以用来读取、处理、执行或翻译结构化文本或二进制文件。他被广泛用来构建语言,工具和框架。ANTLR可以从语法上来生成一个可以构建和遍历解析树的解析器。
东风压倒西风
2022/11/23
7030
点击加载更多

相似问题

求解互左递归文法

12

ANTLR4互左递归

14

Antlr4互左递归误差

11

antlr4 json文法与间接左递归

14

ANTLR4 C#文法和左递归

21
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

扫码加入开发者社群
关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
社区富文本编辑器全新改版!诚邀体验~
全新交互,全新视觉,新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能,全面提升创作效率和体验
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文