问左/右递推、左/右派生、优先级、结合性等的差异

EN

不，它们都有不同的含义。

左右递归指的是生产规则中的递归。如果非终端可以派生包含该非终端的序列，则非终端的产生是递归的；如果非终端可以出现在派生序列的开头(左侧边缘)，则为左递归；如果非终端可以出现在末尾(右侧边缘)，则为右递归。产品可以是递归的，而不需要左递归或右递归，甚至可以是左递归的，也可以是右递归的。

例如：

term: term '*' factor            { /* left-recursive */ }
assignment: lval '=' assignment  { /* right-recursive */ }

上述示例都是直接递归；非终端直接派生包含非终端的序列。递归也可以是间接的；它仍然是递归。

所有常见的解析算法都从左到右处理，这是LL和LR中的第一个L.自顶向下(LL)解析找到最左边的派生(第二个L)，而自下而上(LR)解析找到最右边的派生( R)。

实际上，两种类型的解析器都以单个非终端(起始符号)开始，并根据当前序列中的某个非终端“猜测”一个派生，直到导出输入文本为止。在最左边的派生中，扩展的始终是最左边的非终端。在最右边的推导中，它总是最右边的非终端.

因此，自顶向下的解析器总是猜测第一个非终端要使用哪种产品，然后它需要再次处理现在是第一个非终端的任何产品。(“猜”这里是非正式的。它可以查看要匹配的输入--或者至少是输入的下一个k标记--以确定要使用哪种产品)。这被称为自顶向下处理，因为它从自顶向下构建解析树。

它更容易(至少对我来说)可视化自下而上解析器的操作；它通过反复读取足够多的输入来构建自下而上的解析树，从而找到一些结果，这将是派生链中的最后一个派生。因此，它确实产生了一个最右边的派生，但它输出它的背面-正面。

在用于运算符语言的LR语法中(粗略地说，用于类似算术表达式的语言的语法)，左-右结合分别用左递归语法规则和右递归语法规则建模。“联想性”是对语法的非正式描述，也是“优先性”。

优先级是通过使用一系列语法规则来建模的，每条规则都引用下一条规则(并且通常以处理括号-- '(' expr ')' --既不是左--也不是右--递归)的递归结果结束。

有一种较旧的自下而上分析风格，称为“运算符优先分析”，其中优先级显式地成为语言描述的一部分。一个常见的算子优先算法是所谓的调车场算法.但是，如果您有一个LALR(1)解析器生成器，就像bison一样，您也可以使用它，因为它更通用、更精确。

(我不是解析器和编译器理论方面的专家。我碰巧学到了一些相关的东西。我想和大家分享一下我迄今发现的一些东西。)

我强烈建议看一下这个精彩文章。

对LL算法和LR算法进行了说明和插画，给出了算法。你可以清楚地看到为什么LL被称为自上而下，LR被称为自下而上。

一些引文：

LL和LR解析器的主要区别在于，LL解析器输出解析树的预顺序遍历，LR解析器输出后续遍历。 ..。 我们正在为LL和LR解析器的运行提供一个非常简单的模型。两者都读取输入令牌流，并输出相同的令牌流，在适当的位置插入规则以实现解析树的预顺序(LL)或后置顺序(LR)遍历。 ..。 当您看到诸如LL(1)、LR(0)等名称时，括号中的数字是前瞻性标记的数目。

关于缩略语：(来源)

LR和LL中的第一个L意味着:解析器以的一个方向读取输入文本，而不备份；该方向通常在每一行中从左到右，从上到下跨越完整输入文件的行。

剩余的R和L分别表示:最右和最左的派生.

这是两种不同的解析策略。解析策略确定要重写的下一个非终端。(来源)

• 对于最左边的推导，它总是最左边的非终端。
• 对于最右边的推导，它总是最右边的非终端.