parsing - 左/右递归、左/最右推导、优先级、结合性等之间的区别

Question

我目前正在学习语言处理器，经常出现的一个话题是语法中元素的使用方向。从左到右或从右到左。
我理解这个概念，但似乎有很多方法可以编写这些规则，我不确定它们是否都相同。到目前为止我看到的是:

右/左递归，
最右/最左推导，
右/左归约、优先级、结合性等。

这些都是同一个意思吗？

Answer 1

不，它们都有不同的含义。
右递归和左递归是指产生式规则内的递归。一个非终结符的产生式是递归的，如果它可以导出一个包含该非终结符的序列；如果非终结符可以出现在派生序列的开头(左边缘)，则它是左递归的，如果它可以出现在结尾(右边缘)，则它是右递归的。产生式可以是递归的，既不是左递归也不是右递归，甚至可以是左递归和右递归。
例如:

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

上面的例子都是直接递归；非终端直接衍生出包含非终端的序列。递归也可以是间接的；它仍然是递归。
所有常见的解析算法都是从左到右处理的，也就是LL和LR中的第一个L。自上而下 (LL) 解析找到最左边的派生 (第二个 L)，而自下而上 (LR) 解析找到最右边的派生 (R)。
实际上，两种类型的解析器都以单个非终结符(起始符号)开始，并根据当前序列中的某个非终结符“猜测”一个派生，直到派生输入文本。在最左边的推导中，展开的总是最左边的非终结符。在最右边的推导中，它总是最右边的非终结符。
所以自上而下的解析器总是猜测第一个非终端使用哪个产生式，之后它需要再次处理现在是第一个非终端的任何产品。 (这里的“猜测”是非正式的。它可以查看要匹配的输入——或者至少是输入的下 k 个标记——以确定要使用哪个产生式。)这称为自顶向下处理，因为它从上到下构建解析树。
逆向可视化自底向上解析器的 Action 更容易(至少对我而言)；它通过反复读取刚好足够的输入来找到一些产生式，这将是推导链中的最后一个推导，从而自下而上地构建解析树。所以它确实产生了最右边的推导，但它是从后到前输出的。
在运算符语言的 LR 文法(粗略地说，看起来像算术表达式的语言的文法)中，左结合和右结合分别使用左递归和右递归文法规则建模。 “结合性”是对语法的非正式描述，“优先级”也是如此。
优先级是通过使用一系列语法规则来建模的，每个语法规则都引用下一个规则(并且通常以处理括号的递归产生式结束——'(' expr ')'——既不是左递归也不是右递归)。
有一种较旧的自底向上解析风格，称为“运算符优先级解析”，其中优先级明确地是语言描述的一部分。一种常见的运算符优先算法是所谓的Shunting Yard 算法。但是如果你有一个 LALR(1) 解析器生成器，比如野牛，你不妨改用它，因为它更通用也更精确。