什么是编译器设计中带有回溯的自顶向下解析？

在使用回溯的自顶向下解析中，解析器将尝试多个规则或产生式，通过在推导的每一步回溯来识别输入字符串的匹配。因此，如果应用的产生式没有根据需要给出输入字符串，或者它与所需的字符串不匹配，那么它可以撤消该转变。

Example1 - 考虑语法

S → a A d

A → bc | b

为字符串 a bd 制作解析树。Also, show parse Tree when Backtracking is required when the wrong alternative is chosen.

解决方案

字符串abd 的推导将是 -

S ⇒ a A d ⇒ abd （必填字符串）

如果用bc代替非终结符 A，则获得的字符串将是 abcd。

S ⇒ a A d ⇒ abcd（错误选择）

图(a)代表S→aAd

图 (b) 表示具有产生式 A → bc 的树的扩展，它给出了与字符串 abd 不匹配的字符串 abcd。因此，它回溯并选择另一个替代方案，即图(c)中与abd匹配的A→b。

回溯算法

Example2 - 为以下语法编写一个带有回溯的自上而下解析的算法。

S → a A d

A → bc| b

解决方案

在下面的算法中，每个非终结符 S & A 都有一个过程。语法中的终结符号 a、b、c、d 是 Parser 读取的输入符号或前瞻符号。

advance( )− 用于将输入指针移动到下一个输入符号的函数。

回溯自顶向下解析的局限性

以下是一些问题，这些问题发生在使用回溯的自顶向下解析中。

由于这些原因，实际编译器不使用回溯。

Left Recursion - 如果语法产生形式，则它是左递归的。

A → Aα|β

这导致解析器进入无限循环。