我正在构建一个LL(1(解析器(递归下降解析器(,我需要解析句子a = 3
,我有两个过程来匹配该规则:parse_assignment
和parse_binary_operator
,
每个函数消耗第一个令牌,然后需要查看运算符(=
(是否与规则匹配,所以我首先调用消耗令牌的parse_assignment
;a";,然后消耗"=&";,然后消耗";3〃;。如果函数失败(不匹配(,我会尝试匹配下一条规则。
但是如果我想解析句子a - 1
呢?我尝试调用parse_assignment
,但它消耗了a
并失败,然后我尝试调用parse_binary_operator
,但令牌"0";a";已经被消耗,因此函数只有"0";CCD_ 10";现在进行解析。
因此,我需要以某种方式将令牌返回到流中,以防函数不匹配,但我认为将令牌返回流不是一个好主意,我想有更稳定的技术可以做到这一点。
;(1( ";在";LL(1(";指示解析器被允许查阅(1(未使用的令牌,以便决定采取哪个操作。这个令牌通常被称为";前瞻性";令牌,因为解析器可以在不实际使用它的情况下提前查看它。无论您在解析器和lexer之间实现什么接口,都必须以某种方式实现此功能;否则,你会遇到你提到的问题。
这个接口的确切性质将取决于您使用哪种语言来编写解析器,因此很难给出具体的答案。但基本上,词汇分析器有两种基本方法:
peek
,返回先行令牌的令牌类型。(令牌通常有许多附加功能,所有这些功能都应该通过peek
或其他方法以某种方式可用,这些方法也是前瞻性令牌的视图。这些功能包括令牌的语义值(如果有的话(,以及令牌在源文件中的位置指示consume
,其丢弃先行令牌并用下一个输入令牌替换它
还有其他可能的接口,它们本质上是等价的。例如,实现布尔便利函数(如";匹配X并在成功时消耗该令牌";,尽管如果您还需要返回匹配令牌的语义值,那么这可能不太方便。
先行标记是词法分析器状态的一部分,它还包括诸如当前正在解析的字符串和该字符串中的当前输入位置之类的信息。将这种状态存储在全局变量中曾经很常见(这是词法分析器在(f(lex的帮助下构建的(,但这使得用两个不同的词法分析器编写程序变得更加困难。现代编程风格不鼓励使用全局变量,这就需要在解析器状态(或对象(中包括词法分析器的状态(或目标(,或者通过递归解析调用显式传递对词法分析器状态的引用。