解析技术，在解析过程中的任意点列出所有可用的标记

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解析器和其他一些解析器，但是学习这些候选人中的每一个仅仅是为了找出它是否适合这种情况似乎是不合理的。我的问题是，什么样的解析技术最能让我提示用户提供一个给定不完整输入句子的有效标记列表？

虽然我对递归下降解析和使用各种解析器生成器很满意，但我只学习了大约一年的材料，所以请原谅我的无知。

谢谢。

Answer 1

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

有些人称它为自动完成或句子完成。它很少用于你想要的目的。但是，修改后的解析器是可行的。解析器必须生成问题，“我的名字是”，然后从用户处读取预期的令牌"“。

这实际上是对解析器所能做的事情的简化。对于这样简单的事情使用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> 

这是一种有效的方法，可以自动生成提问者。解析器将生成不位于角括号中的单词，并要求用户输入变量信息。或者只需在语法中放置有角度的括号词，以避免冗余，并向用户询问、等。

最好和最可靠的方法是创建一个规范的LR(1)解析器。这种解析器在每种状态下都具有所有预期的令牌。没有必要通过减少违约来看待其他国家。只要语法不是很大，就应该尝试使用CLR(1)解析器。

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

Answer 2

任何只需要一个前瞻性令牌的从左到右的解析方案都可以正常工作，前提是语言可以用该方案进行解析。如果解析表是可访问的和有文档的(不幸的是，大多数解析器生成器的情况并非如此)，那么使用表驱动的实现可能更容易，但是您可以使用任何带有"push“接口和可复制状态的黑盒解析器，只需循环遍历所有可能的标记类型，并记录哪些标记类型不会产生错误。

预测逻辑使用LL(1)语法比LR(1)语法容易，因为LL解析器状态始终是唯一的项。LR解析器状态通常是几个项的结合，因此如何描述当前的解析上下文可能并不完全清楚。另一方面，LR解析器可以处理更大的语法集。