找到一个等价的 LR 文法
Find an equivalent LR grammar
我正在尝试为 Pascal 查找 LR(1) 或 LR(0) 语法。这是我的语法的一部分，它不是 LR(0)，因为它有 shift/reduce 冲突。
EXPR --> AEXPR | AEXPR realop AEXPR
AEXPR --> TERM | SIGN TERM | AEXPR addop TERM
TERM --> TERM mulop FACTOR | FACTOR
FACTOR --> id | num | ( EXPR )
SIGN --> + | -
(大写为变量，小写+,-为终结符)
如您所见，EXPR --> AEXPR | AEXPR realop AEXPR 导致 LR(0) 解析发生 shift/reduce 冲突。我尝试添加一个新变量，以及一些其他方法来为此找到等效的 LR (0) 语法，但我没有成功。
我有两个问题。
第一：这个文法是LR(1)文法吗？
其次：是否可以为该语法找到一个 LR(0) 等价物？ LR(1) 等价物呢？
是的，你的文法是 LR(1) 文法。 [见下面的注释]
导致LR(0) 冲突的不仅仅是第一个产品。在 LR(0) 文法中，您必须能够预测是移动还是减少（以及减少哪个生产），而无需咨询前瞻符号。这是一个非常严格的要求。
尽管如此，还是有一种语法可以识别同一种语言。它不是等价语法，因为它不会产生相同的解析树（或任何有用的解析树），所以这取决于你认为什么是等价的。
EXPR → TERM | EXPR OP TERM
TERM → num | id | '(' EXPR ')' | addop TERM
OP → addop | mulop | realop
以上通过忽略运算符优先级来工作；它将表达式视为简单的常规语言 TERM (op TERM)*。 （我将 + | - 更改为 addop，因为我看不到您的扫描仪在其他情况下如何工作，但这并不重要。）
有一个转换通常用于使 LR(1) 表达式文法适合 LL(1) 解析，但由于允许 LL(1) 检查先行字符，它能够处理运算符优先级正常方式。 LL(1)“等价”语法不会生成具有正确运算符关联性的解析树——所有运算符都变为 right-associative——但可以通过简单的树旋转来恢复正确的解析树。
在 LR(0) 语法的情况下，运算符优先级已丢失，树转换几乎等同于重新解析输入，使用调车场算法之类的东西来创建真正的解析树。
备注
我不认为所提供的语法是正确的语法，因为它使一元加号和减号的绑定不如乘法紧密，结果 -3*4 被解析为 -(3*4)。碰巧的是，大多数时候没有语义差异，但我仍然觉得不对劲。我会把语法写成：
EXPR → AEXPR | AEXPR realop AEXPR
AEXPR → TERM | AEXPR addop TERM
TERM → FACTOR | TERM mulop FACTOR
FACTOR → num | id | '(' EXPR ')' | addop FACTOR
这使得一元运算符绑定得更紧密。 （如上所述，我假设 addop 恰好是 + 或 -。）
我正在尝试为 Pascal 查找 LR(1) 或 LR(0) 语法。这是我的语法的一部分，它不是 LR(0)，因为它有 shift/reduce 冲突。
EXPR --> AEXPR | AEXPR realop AEXPR
AEXPR --> TERM | SIGN TERM | AEXPR addop TERM
TERM --> TERM mulop FACTOR | FACTOR
FACTOR --> id | num | ( EXPR )
SIGN --> + | -
(大写为变量，小写+,-为终结符)
如您所见，EXPR --> AEXPR | AEXPR realop AEXPR 导致 LR(0) 解析发生 shift/reduce 冲突。我尝试添加一个新变量，以及一些其他方法来为此找到等效的 LR (0) 语法，但我没有成功。
我有两个问题。
第一：这个文法是LR(1)文法吗？
其次：是否可以为该语法找到一个 LR(0) 等价物？ LR(1) 等价物呢？
是的，你的文法是 LR(1) 文法。 [见下面的注释]
导致LR(0) 冲突的不仅仅是第一个产品。在 LR(0) 文法中，您必须能够预测是移动还是减少（以及减少哪个生产），而无需咨询前瞻符号。这是一个非常严格的要求。
尽管如此，还是有一种语法可以识别同一种语言。它不是等价语法，因为它不会产生相同的解析树（或任何有用的解析树），所以这取决于你认为什么是等价的。
EXPR → TERM | EXPR OP TERM
TERM → num | id | '(' EXPR ')' | addop TERM
OP → addop | mulop | realop
以上通过忽略运算符优先级来工作；它将表达式视为简单的常规语言 TERM (op TERM)*。 （我将 + | - 更改为 addop，因为我看不到您的扫描仪在其他情况下如何工作，但这并不重要。）
有一个转换通常用于使 LR(1) 表达式文法适合 LL(1) 解析，但由于允许 LL(1) 检查先行字符，它能够处理运算符优先级正常方式。 LL(1)“等价”语法不会生成具有正确运算符关联性的解析树——所有运算符都变为 right-associative——但可以通过简单的树旋转来恢复正确的解析树。
在 LR(0) 语法的情况下，运算符优先级已丢失，树转换几乎等同于重新解析输入，使用调车场算法之类的东西来创建真正的解析树。
备注
我不认为所提供的语法是正确的语法，因为它使一元加号和减号的绑定不如乘法紧密，结果 -3*4 被解析为 -(3*4)。碰巧的是，大多数时候没有语义差异，但我仍然觉得不对劲。我会把语法写成：
EXPR → AEXPR | AEXPR realop AEXPR
AEXPR → TERM | AEXPR addop TERM
TERM → FACTOR | TERM mulop FACTOR
FACTOR → num | id | '(' EXPR ')' | addop FACTOR
这使得一元运算符绑定得更紧密。 （如上所述，我假设 addop 恰好是 + 或 -。）