python - 解析过程中随时列出所有可用标记的解析技术

Question

我想知道是否可以使用 CFG 或 PEG 启发的语法来表示 CLI 提示；例如，自动生成设置向导或调查。为了实现这一点，解析器必须根据用户已经输入的内容提示用户输入下一个输入标记。示例:

customer_info -> "My name is " name_expression " and I'm " %age " years old."
name_expression -> %name %name
                 | %name

name_expression 允许您输入名字和姓氏，或者只是一个名字。字符串常量将由提示自动填充。此规范将为假设的用户编译以下示例体验:

My name is (enter %name):
>> john
My name is john (1 for "%lastname", 2 for " and I'm "):
>> 2
My name is john and I'm (enter a number):
>> 39
My name is john and I'm [39] years old.
Prompt complete, exiting.

我读过一些关于“逆解析器”的内容，其想法是在交互式对话期间，所有潜在的响应都会在对话的每一步中列出(想想 RPG 风格的视频游戏对话) NPC)。关于这项技术的信息在网上似乎很少，我不确定它是否能完全达到我想要的效果。

我研究过 Earley 解析器、预测 LL 解析器和其他一些解析器，但学习每一个候选解析器只是为了找出它是否适合这种情况似乎是不合理的。我的问题是，哪种解析技术最能让我在给定不完整的输入句子的情况下提示用户提供有效标记列表？

虽然我对递归下降解析和使用各种解析器生成器感到满意，但我只研究了大约一年的 Material ，所以请原谅我的无知。

谢谢。

Answer 1

此技术已存在于 LRSTAR 中我认为它内置于 ANTLR 和 Bison/Yacc 生成的解析器中。当输入中遇到错误时它会被激活。然后它列出了所有预期的有效 token 。

有些人称之为自动完成或句子完成。它很少用于您所询问的目的。然而，使用修改后的解析器是可行的。解析器必须生成问题“我的名字是”，然后从用户读取预期的标记“ ”。

这实际上是解析器功能的简化。使用 LR 解析器来处理如此简单的事情有点过分了。

语法可能如下所示:

Goal      -> Questions <eof>
Questions -> FirstName LastName Street City State Zipcode Age
FirstName -> first name <first_name>
LastName  -> last name <last_name>
Street    -> street <street>
City      -> city <city>
State     -> state <state>
Zipcode   -> zipcode <zipcode>
Age       -> age <age> 

这是自动创建调查问卷的有效方法。解析器会生成不在尖括号中的单词，并要求用户输入变量信息。或者只是将尖括号单词放入语法中，以避免冗余并询问用户 、 等。

最好、最可靠的方法是创建 Canonical LR(1) 解析器。这种解析器在每个状态下都有所有预期的标记。无需通过默认减少来查看其他州。只要您的语法不是很大，您就应该尝试 CLR(1) 解析器。

LRSTAR可以生成一个 CLR(1) 解析器，该解析器已经内置了代码来列出预期的标记。