语法与算子相关性之间的关系

Question

一些编译器书籍/文章/论文谈论语法的设计及其运算符的关联性的关系.我是自上而下的狂热粉丝,特别是递归下降,解析器和迄今为止我编写的大多数(如果不是全部)编译器都使用以下表达式语法:

Expr   ::= Term { ( "+" | "-" ) Term }
Term   ::= Factor { ( "*" | "/" ) Factor }
Factor ::= INTEGER | "(" Expr ")"

这是该BNF的EBNF表示:

Expr  ::= Term Expr'
Expr' ::= ( "+" | "-" ) Term Expr' | ?
Term  ::= Factor Term'
Term' ::= ( "*" | "/" ) Factor Term' | ?
Factor = INTEGER | "(" Expr ")"

根据我所读到的,有些人认为这种语法是"错误的",因为操作员关联性的变化(这4个操作员从左到右)由不断增长的解析树向右而不是向左证明.对于通过属性语法实现的解析器,这可能是正确的,因为l-attribute值要求首先创建此值,然后传递给子节点.然而,当使用普通的递归下降解析器实现时,由我决定是先构造此节点然后传递给子节点(自上而下)还是先创建子节点然后将返回的值添加为此节点的子节点(通过在这个节点的构造函数中)(自下而上).我应该在这里找到一些东西,因为我不同意这句话说这个语法是"错误的",而且这种语法已被用于许多语言中.Wirthian的.通常(或全部？)表示它的读数会促进LR解析而不是LL.

Answer 1

我认为这里的问题是语言具有抽象语法，就像：

\n\n

E ::= E + E | E - E | E * E | E / E | Int | (E)\n

\n\n

但这实际上是通过具体语法实现的用于指定关联性和优先级的因此，如果您正在编写一个递归的体面解析，那么您将在进行过程中隐式地将具体语法写入其中，这很好，尽管将其精确地指定为短语结构语法可能会更好！

\n\n

如果你的语法是一个成熟的具体语法，那么它有几个问题。首先，您需要添加产生式以“转到下一个级别”，因此稍微放松您的语法：

\n\n

Expr ::= Term + Term | Term - Term | Term\nTerm ::= Factor * Factor | Factor / Factor | Factor\nFactor ::= INTEGER | (Expr)\n

\n\n

否则，无法从起始符号（在本例中为 Expr）开始导出有效的句子。例如，如果没有这些额外的产生式，您将如何导出“1 * 2”？

\n\n

Expr -> Term\n     -> Factor * Factor\n     -> 1 * Factor\n     -> 1 * 2\n

\n\n

我们可以看到其他语法以稍微不同的方式处理这个问题：

\n\n

Expr -> Term Expr'\n     -> Factor Term' Expr'\n     -> 1 Term' Expr'\n     -> 1 * Factor Term' Expr'\n     -> 1 * 2 Term' Expr'\n     -> 1 * 2 \xce\xb5 Expr'\n     -> 1 * 2 \xce\xb5 \xce\xb5\n      = 1 * 2\n

\n\n

但这达到了相同的效果。

\n\n

您的解析器实际上是非关联的。看到这个问如何E + E + E解析，发现不能解析。无论哪个+先被消耗，我们都会得到E一侧和E + E另一侧，但随后我们尝试将E + E其解析为Term这是不可能的。同样，考虑从起始符号导出该表达式，这也是不可能的。

\n\n

Expr -> Term + Term\n     -> ? (can't get another + in here)\n

\n\n

另一种语法是左结合 ebcase 任意长的字符串E + E + ... + E另一种语法是左关联 ebcase ，可以导出

\n\n

所以无论如何，总而言之，您是对的，在编写 RDP 时，您可以实现抽象的任何具体版本，并且您可能比我更了解这一点。但是，当尝试生成精确描述 RDP 的语法时，会出现这些问题。希望有帮助！

\n