ANTLR 词法分析器如何消除其规则的歧义(或者为什么我的解析器会产生“输入不匹配”错误)?

2023-11-29

Note:这是一个自答问题旨在为 ANTLR 用户最常犯的错误之一提供参考。


当我测试这个非常简单的语法时:

grammar KeyValues;

keyValueList: keyValue*;
keyValue: key=IDENTIFIER '=' value=INTEGER ';';

IDENTIFIER: [A-Za-z0-9]+;
INTEGER: [0-9]+;

WS: [ \t\r\n]+ -> skip;

输入以下内容:

foo = 42;

我最终遇到以下运行时错误:

第 1:6 行不匹配输入“42”,需要 INTEGER
第 1:8 行输入“​​;”不匹配期待“=”

为什么ANTLR不识别42 as an INTEGER在这种情况下?
它应该与模式匹配[0-9]+正好。

如果我颠倒顺序INTEGER and IDENTIFIER定义它似乎有效,但为什么顺序首先很重要?


在ANTLR中,词法分析器与解析器是隔离的,这意味着它将把文本分割成typed根据词法分析器语法规则进行标记,解析器对此过程没有影响(不能说“给我一个INTEGER now"例如)。它产生一个令牌流通过它自己。此外,解析器不关心标记文本,它只关心标记类型以匹配其规则。

当多个词法分析器规则可以匹配相同的输入文本时,这很容易成为问题。在这种情况下,将根据这些选择令牌类型优先规则:

  • 首先,选择与longest输入子串
  • 如果最长匹配的子字符串等于隐式定义的标记(例如'='),使用隐式规则作为token类型
  • 如果多个词法分析器规则匹配相同的输入,请选择first一、基于定义顺序

为了有效地使用 ANTLR,记住这些规则非常重要。


在问题的示例中,解析器期望看到以下标记流来匹配keyValue解析器规则:IDENTIFIER '=' INTEGER ';' where '=' and ';'是隐式标记类型。

Since 42可以匹配both INTEGER and IDENTIFIER, and IDENTIFIER首先定义,解析器将收到以下输入:IDENTIFIER '=' IDENTIFIER ';'它将无法匹配到keyValue规则。请记住,解析器cannot交流to词法分析器,它只能从中接收数据,因此它不能说“尝试匹配INTEGER next".

建议尽量减少词法分析器规则重叠,以限制此效果的影响。在上面的例子中,我们有几种选择:

  • 重新定义IDENTIFIER as [A-Za-z] [A-Za-z0-9]*(要求以字母开头)。这完全避免了这个问题,但阻止了定义以数字开头的标识符名称,因此它改变了语法的意图。
  • Reorder INTEGER and IDENTIFIER。这解决了大多数情况下的问题,但阻止了定义完全数字的标识符,因此它也以微妙的、不那么明显的方式改变了语法的意图。
  • 当词法分析器规则重叠时,使解析器接受两种标记类型:
    首先,交换INTEGER and IDENTIFIER为了优先考虑INTEGER。然后,定义解析器规则id: IDENTIFIER | INTEGER;然后使用该规则而不是IDENTIFIER在其他解析器规则中,这会改变keyValue to key=id '=' value=INTEGER ';'.

这是要总结的第二个词法分析器行为示例:

组合语法如下:

grammar LexerPriorityRulesExample;

// Parser rules

randomParserRule: 'foo'; // Implicitly declared token type

// Lexer rules

BAR: 'bar';
IDENTIFIER: [A-Za-z]+;
BAZ: 'baz';

WS: [ \t\r\n]+ -> skip;

给定以下输入:

aaa foo bar baz barz

将从词法分析器生成以下标记序列:

IDENTIFIER 'foo' BAR IDENTIFIER IDENTIFIER EOF

  • aaa属于类型IDENTIFIER

    只有IDENTIFIER规则可以匹配这个标记,没有歧义。

  • foo属于类型'foo'

    解析器规则randomParserRule引入了隐含的'foo'令牌类型,优先于IDENTIFIER rule.

  • bar属于类型BAR

    这段文字匹配BAR规则,其定义为before the IDENTIFIER规则,因此具有优先权。

  • baz属于类型IDENTIFIER

    这段文字匹配BAZ规则,但它也符合IDENTIFIER规则。后者是根据定义选择的before BAR.

    考虑到语法,BAZ永远无法匹配,因为IDENTIFIER规则已经涵盖了一切BAZ可以匹配。

  • barz属于类型IDENTIFIER

    The BAR规则可以匹配该字符串的前 3 个字符 (bar),但是IDENTIFIER规则将匹配 4 个字符。作为IDENTIFIER匹配更长的子串,它被选择BAR.

  • EOF (文件结尾) 是隐式定义的标记类型,始终出现在输入的末尾。

根据经验,应定义具体规则before更通用的规则。如果规则只能匹配先前定义的规则已覆盖的输入,则它将never使用。

隐式定义的规则,例如'foo'就好像它们已被定义一样before所有其他词法分析器规则。由于它们增加了复杂性,建议完全避免它们并声明显式词法分析器规则。这种方法的一个显着优点是,只需将标记列表放在一个位置,而不是将它们分散在语法中。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

ANTLR 词法分析器如何消除其规则的歧义(或者为什么我的解析器会产生“输入不匹配”错误)? 的相关文章

  • 解析整数集的字符串并列出间隔

    I have 2 5 7 9 12 string 我想从中获取 2 5 7 8 9 12 列表 python中有没有内置的函数 Thanks UPD 我想 直接的答案是No 不管怎样 谢谢你的 片段 使用一个 建议者斯文 马尔纳克 s 2
  • Javascript 和自动分号插入

    test262 http test262 ecmascript org测试套件有test http hg ecmascript org tests test262 file 927ea8563f7f test suite ch07 7 9
  • 从电话号码确定国际电话代码的算法

    我可以使用 iOS 上的地址簿框架从设备中检索联系人的电话号码 如何区分或识别哪个是国家 地区代码 哪个是实际电话号码 是否可以 国家 地区代码是一个相当混乱的主题 但足够标准 通过一些程序员维护就可以解决它 您可以通过其初始子序列来识别国
  • 用于打印 C/C++ 文件的所有函数定义的 Python 脚本

    我想要一个 python 脚本来打印 C C 文件中定义的所有函数的列表 e g abc c定义两个函数为 void func1 int func2 int i printf d i return 1 我只想搜索文件 abc c 并打印其中
  • 如何在批处理文件中解析带有特殊分隔符的文件?

    我想使用批处理来解析一个如下所示的文件 a string containing various characters and spaces 1 b string containing various characters and space
  • 生成基于内联 HTML 样式的样式表?

    一段时间以来 我一直致力于对网站的不同部分进行样式设计 但是我尚未将内联样式放入样式表中 我想知道是否存在一个工具可以解析 HTML 文件并从中生成样式表 例如 这是我网站的一个片段 div class block style border
  • 如果没有解析器生成器,如何用 C 或 Objective-C 编写解析器?

    我正在尝试用 C 或 Objective C 制作一个计算器 它接受以下字符串 8 2 4 3 9 2 并返回答案 2920 我不想使用像 Lex 或 Yacc 这样的生成器 所以我想从头开始编码 我该怎么做呢 除了 龙 这本书之外 还有其
  • DateTime.ParseExact - 为什么 yy 变成 2015 而不是 1915

    为什么 NET 假定以下年份是 2015 年 而不是 1915 年 var d DateTime ParseExact 20 11 15 dd MM yy new CultureInfo en GB 我想 它会尝试接近 但其背后是否有合理的
  • 如何向 Parse Signup 功能添加额外属性?

    我想向我的解析注册函数添加一个额外的属性 我的代码就像 signUp function e var self this var username this signup username val var password this sign
  • 来自 ANTLR 解析树的 Python AST?

    我找到了一个ANTLR4 Python3 语法 https github com bkiers python3 parser 但它会生成一个解析树 该树通常有许多无用的节点 我正在寻找一个已知的包来从该解析树获取 Python AST 这样
  • 寻找引文解析器

    我需要一个解析器来扫描学术文本 提取引文 并将这些引文解析为其组成部分 作者 标题 出版日期等 我尝试过 Paracite 但它速度非常慢 而且不能产生高质量的结果 任何语言都可以 但首选 Java 看一眼ParsCit http aye
  • less.js - 在解析器回调中获取变量值

    我正在使用 less js 1 3 0 在客户端将 less 解析为 css 在解析器的回调中 我想获取每个变量的值 我尝试了以下方法但没有成功 var data colour red example background color co
  • 在压缩存档内的文本文件上运行“head”,而不解压存档

    问候 我接手了之前的团队并编写了处理 csv 文件的 ETL 作业 我在 ubuntu 上结合使用 shell 脚本和 perl csv 文件很大 它们以压缩档案形式到达 解压后 很多都超过 30Gb 是的 那是 G 旧进程是在 cron
  • 在 C# 中遍历 ANTLR AST 的教程?

    有人知道在 C 中遍历 ANTLR 生成的 AST 的教程吗 我能找到的最接近的是this https web archive org web 20201019210638 http www manuelabadia com blog Pe
  • 使用 Boost::Spirit 解析 time_period 表达式

    我需要使用 Boost Spirit 解析以下 EBNF 表达式 period date part time part date part time part time part hours minutes seconds date par
  • 如何使用 ICU 解析汉字数字字符?

    我正在编写一个使用 ICU 来解析由汉字数字字符组成的 Unicode 字符串的函数 并希望返回该字符串的整数值 五 gt 5 三十一 gt 31 五千九百七十二 gt 5972 我将区域设置设置为 Locale getJapan 并使用
  • 在自定义对象中映射 JSON 对象

    我一直在搜索是否可以获取 JSON 字典或数组并将其直接映射到属性与 JSON 标签同名的自定义对象中 但我没有找到任何相关信息 我一直在手动解析 JSON 字典 如下所示 id deserializedObj nil id jsonObj
  • strings.xml 中的 Android 变量

    我在某处读到如何在 XML 文档中使用变量 他们说这很简单 我想也是如此 我在 Android strings xml 文件中成功地使用了它 我一整天都这样使用它 直到突然 android 停止解析它并停止将它视为变量 我这样使用它
  • 搜索引擎如何找到相关内容? [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 Google 在解析网络时如何找到相关内容 例如 Google 使用 PHP 原生 DOM 库来解析内
  • 在 Python 中解析 TCL 列表

    我需要在双括号上拆分以空格分隔的 TCL 列表 例如 OUTPUT 172 25 50 10 01 01 Ethernet 172 25 50 10 01 02 Ethernet Traffic Item 1 172 25 50 10 01

随机推荐

  • Mongo 聚合与 Java for 循环和性能

    我存储了以下 mongo 文档 Field1 ABC Field2 Field3 ABC1 Field4 id 123 id 234 id 345 Field3 ABC2 Field4 id 123 id 234 id 345 Field3
  • 通过重命名旧表然后填充新版本来将表停机时间降至最低?

    我有一些左右的永久桌子需要每晚重建 为了使这些表尽可能长时间地 活动 并且也提供仅备份前一天数据的可能性 另一位开发人员含糊地建议 当夜间构建发生时 采取与此类似的路线 创建永久表 构建版本 例如 tbl build Client 重命名活
  • MYSQL 中的批量插入

    在 MS SQL 上 我可以使用下面的 sql 命令进行批量插入 BULK INSERT myDatabase MyTable FROM C MyTextFile txt WITH FIELDTERMINATOR 现在我想在 MySQL 上
  • 如何计算JavaScript中的图像加载/渲染时间?

    有没有办法使用 javascript jquery 查找网页中的图像加载 渲染时间 这里正确的答案是使用 Chrome 或 Firefox Firebug 等浏览器内置的开发工具 它会告诉您页面中所有资源的加载时间 这些工具可以访问纯 Ja
  • PHP - 遍历文件夹并显示 HTML 内容

    我目前正在尝试开发一种方法来概述我多年来创建和 合法 下载的所有不同的网页模板 我想过像这样展示它们WordPress正在使用一个小的预览窗口预览其模板 显示带有样式和所有内容的具体文件 如何将它们分为行和列并创建Ajax模式窗口在预览和分
  • 提高远程桌面上的 WPF 应用程序速度?

    在我们的场景中 我们有一个wpf应用程序 供用户通过远程桌面使用 我们发现用户体验非常慢 对于改善这种情况下的用户体验有什么建议吗 其中一点可能是禁用任何动画 故事板 并避免在 UI 中使用渐变 更多想法值得赞赏 对于渐变来说 这不像多个渲
  • unix 中正则表达式的语法错误

    我尝试找到一个与 1 到 999 之间的任何数字匹配的正则表达式 当使用钩子时我收到语法错误 bash syntax error near unexpected token 当我不使用钩子时 什么也不会发生 我的正则表达式是 egrep 1
  • Android 操作栏:我可以替换 appcompat v7 中的自定义标题吗

    我想在肌动蛋白条的左侧添加自定义操作标题 替换为默认标题 如下图所示 显示默认图像 在这里我想添加这个标题 您需要更改操作栏中的徽标和标题 您可以使用 getActivity getActionBar setTitle your title
  • Perl:如何使所需脚本中的变量在所需脚本中可用

    example out pl my our local global whatever var test require inside pm 里面 pm print var 我不想使用软件包 它超出了我的需求 谢谢 You are alwa
  • 对数组进行排序所需的最少操作数

    我正在尝试练习解决 Codeforces 中的问题 它通过将数组的元素移动到数组的开头或结尾来对数组进行排序 起初我认为它是最长的递增子序列 但在某些情况下它不起作用 例如 如果输入是 4 1 2 5 3 则 LIS 是 3 但问题的答案是
  • 如何在 C#.NET 中更改图像的像素颜色

    我正在Java中处理图像 我设计了超过100多个图像 png 格式 它们都是透明和黑色绘图 问题是 现在我被要求更改绘图的颜色 黑色 我在谷歌上搜索了许多代码 这些代码改变了图像的位图 像素 但我不猜测我必须做什么来匹配确切的像素 并在图像
  • 构建战争时删除插件视图(gsp)

    我们在 grails 应用程序中使用各种插件 如日志记录 spring security core ui acl 等 现在这些插件带有默认的 gsp 在每个插件的视图文件夹中 我想构建一个 WAR 而不包含任何插件的视图 因此 当战争现在构
  • ASP.NET 中的多选下拉列表

    asp net 是否存在任何好的带有复选框 webcontrol 的多选下拉列表 多谢 你可以使用System Web UI WebControls CheckBoxList控制或使用System Web UI WebControls Li
  • android 棒棒糖通知背景颜色

    是否可以更改 android lollipop 中通知的背景颜色 我注意到有些通知是白色的 有些是浅灰色的 有些是深灰色的 source gottabemobile com source sftcdn net 您可以看到音乐播放器通知具有深
  • 如何使用PyTorch计算偏导数?

    我想使用 PyTorch 获取输出和输入之间的偏导数 假设我有一个函数Y 5 x1 4 3 x2 3 7 x1 2 9 x2 5 然后我训练一个网络来替换这个函数 然后我使用 autograd 来计算dYdx1 dYdx2 net torc
  • 将 pandas 数据框中的所有行除以特定行

    我有一个 pandas 数据框 如下所示 Sample name C14 Cer mean C16 Cer mean C18 Cer mean C18 1 Cer mean 0 1 1 0 124749 0 285659 35 302029
  • EC2 启动时自动启动 docker-compose

    我有一个 Linux AMI 2 AWS 实例 其中包含一些通过 docker compose 编排的服务 并且我使用 docker compose up 或 docker compose start 命令来启动它们 现在我每天都会自动启动
  • 通过 ssh 包装命令:如何管理复杂的引号?

    我使用 HPC 集群 计算节点无法访问互联网 只能访问前端 所以我想包装所有需要访问互联网的命令 以便在正面执行它们 例如 对于 wget bin bash ssh frontal bin wget gt 工作正常 我必须包装这个 bq g
  • 生成所有可能的深度为 N 的树?

    我有几种不同类型的树节点 每个节点可能有 0 到 5 个子节点 我正在尝试找出一种算法来生成所有可能的深度 Here s a Python program I wrote up that I think does what you re a
  • ANTLR 词法分析器如何消除其规则的歧义(或者为什么我的解析器会产生“输入不匹配”错误)?

    Note 这是一个自答问题旨在为 ANTLR 用户最常犯的错误之一提供参考 当我测试这个非常简单的语法时 grammar KeyValues keyValueList keyValue keyValue key IDENTIFIER val