我收到以下错误:
Warning : *** Shift/Reduce conflict found in state #116
between Statement ::= Matched (*)
and Unmatched ::= IF LPAREN Condition RPAREN Matched (*) ELSE Unmatched
and Matched ::= IF LPAREN Condition RPAREN Matched (*) ELSE Matched
under symbol ELSE
Resolved in favor of shifting.
现在,我知道了悬而未决的问题,并且我尝试使语法明确:
Statement ::= Matched | Unmatched ;
Matched ::= IF LPAREN Condition RPAREN Matched ELSE Matched
|
Others
;
Unmatched ::= IF LPAREN Condition RPAREN Statement
|
IF LPAREN Condition RPAREN Matched ELSE Unmatched
;
没有优先运算符,有什么方法可以解决此问题,还是语法有其他问题?
最佳答案
问题中显示的语法没有错,所以我的猜测是,移位/减少冲突是与另一种产品相互作用的结果。
将语句分为Matched
和Unmatched
的想法:
Statement ::= Matched | Unmatched ;
正是为了确保else正确匹配最接近的if。
Matched
语句不能使用else子句扩展;可能是Unmatched
语句。因此,我们要求语法中的其他标记不能跟随Unmatched
语句,从而避免过早减少可能已使用else
子句扩展的语句。因此,在
If
语句内,else只能跟随Matched
语句。如果语句本身没有Unmatched
子句,或者else
子句本身是else
,则该语句本身就是Unmatched
。因此,我们有三个产品:Unmatched_If ::= IF LPAREN Condition RPAREN Statement
| IF LPAREN Condition RPAREN Matched ELSE Unmatched ;
Matched_If ::= IF LPAREN Condition RPAREN Matched ELSE Matched ;
但这还不是全部,因为还有其他可能的复合语句。考虑例如
while
语句。如果语言具有这样的构造,则语法可能包含以下内容:While ::= WHILE LPAREN Condition RPAREN Statement ; /* Wrong! */
那是行不通的,因为
while
语句也可以是Unmatched
,与if...else
语句可以完全一样:如果内部Statement
是Unmatched
。例如,考虑
while (x) if (y) do_x_and_y;
由于上面的
While
生产不正确,可以将其减少如下: WHILE LPAREN Condition RPAREN Unmatched_If
-> WHILE LPAREN Condition RPAREN Statement
-> Matched
但这违反了
Unmatched
不能跟随其他的要求。 Matched
可以跟在else后面,但是在这种情况下,Matched
以Unmatched_If
结尾。因此,我们有一个转移/减少冲突:if (w)
while (x) if (y) do_this;
else do_that;
这可以解析为
IF ( Condition:[w] ) Matched:[while(x)if(y)do_this;] ELSE Statement:[do_that;]
但这实际上不是预期的解析。 (缩进可能使我们认为这是程序员的意图,但这不是语言设计者的意图。)其他(如果不是第一个)应该与第二个匹配,从而导致:
if (w)
while (x)
if (y) do_this; else do_that;
因此,我们需要区分匹配和不匹配的
While
语句,而不仅仅是匹配和不匹配的If
语句:Unmatched_While ::= WHILE LPAREN Condition RPAREN Unmatched ;
Matched_While ::= WHILE LPAREN Condition RPAREN Matched ;
这样,
while (x) if (y) do_x_and_y;
将被解析为Unmatched_While
,因此它不再可以是开始IF LPAREN Condition RPAREN Matched ELSE...
的生产的一部分。当然,其他复合语句(例如
for
语句)也需要执行相同的操作。因此,最终结果将类似于:
Matched ::= Matched_If
| Matched_While
| Matched_For
| ...
| Simple_Statement
;
Unmatched ::= Unmatched_If
| Unmatched_While
| Unmatched_For
| ...
;