無法讓我的腦袋爲創建無歧義的語法做好準備

Question

這是我們教授寫的一篇教程，我無法理解它。我可以拿出推導，但我不能只通過分析推導拿出語法。

在這種情況下，「匹配」是指什麼？

你能解釋如何匹配匹配，matched_stmt，unmatched_if工作在簡單的話:)？

The following is an unambiguous grammar for the problem: 

stmt → if_stmt | nonif_stmt 
if_stmt → matched_if | unmatched_if 
matched_if → 'if' logical_expr 'then' matched_stmt 'else' matched_stmt 
matched_stmt → mathced_if | nonif_stmt 
unmatched_if → 'if' logical_expr 'then' stmt 
| 'if' logical_expr 'then' matched_stmt 'else' unmatched_if 
logical_expr → id '==' lit 
nonif_stmt → assgn_stmt 
assgn_stmt → id '=' expr 
expr → expr '+' term | term 
term → '(' expr ')' | id 
id → 'A' | 'B' | 'C' 
lit → '0' | '1' | '2' 


Consider the following input: 
if A == 0 then 
    if B == 1 then 
    C = A + B 
    else 
    B = C 

Let us do a leftmost derivation for the input: 

stmt 
=> if_stmt 
=> unmatched_if 
=> 'if' logical_expr 'then' stmt 
=> 'if' id '==' lit 'then' stmt 
=> 'if' 'A' '==' lit 'then' stmt 
=> 'if' 'A' '==' '0' 'then' stmt 
=> 'if' 'A' '==' '0' 'then' if_stmt 
=> 'if' 'A' '==' '0' 'then' matched_if 
=> 'if' 'A' '==' '0' 'then' 'if' logical_expr 'then' matched_stmt 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' id '==' lit 'then' matched_stmt 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' lit 'then' matched_stmt 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' matched_stmt 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' nonif_stmt 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' assgn_stmt 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' id '=' expr 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' expr '+' term 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' term '+' term 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' id '+' term 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' 'A' + term 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' 'A' + 'B' 'else' matched_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' 'A' + 'B' 'else' nonif_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' 'A' + 'B' 'else' assgn_stmt 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' 'A' + 'B' 'else' id '=' expr 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' 'A' + 'B' 'else' 'B' '=' expr 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' 'A' + 'B' 'else' 'B' '=' term 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' 'A' + 'B' 'else' 'B' '=' id 
=> 'if' 'A' '==' '0' 'then' 'if' 'B' '==' '1' 'then' 'C' '=' 'A' + 'B' 'else' 'B' '=' 'C' 

Answer 1

「匹配」 意味着每then與一個else匹配。

這是沒有必要的if語句具有相匹配的else，但如果它不，它不可能是一個匹配if語句中，因爲這將意味着一些else相匹配的外then而不是內部then） 。

所有的語法都是將上面的形式化。

一個類似的問題是爲普通算術表達式編寫一個語法，附加規則可以省略尾部的小括號。 （例如，您可以編寫(1+2*(1+2*(1+2）。該語言顯然是明確的，但是當您爲它編寫語法時，需要處理不匹配的括號，因此需要處理包含不匹配括號的表達式。這與「匹配」一詞的用法相同（並且解決方案會有點類似）。