Snowdream

1. 考慮表達(dá)式3 + 4的語(yǔ)法分析樹(shù)，exp( exp(number (3)), op(+), exp(number (4)) )。
還有一種更為簡(jiǎn)單的表示方法，例如將(34 - 3) * 42表示為*(-(34, 3), 42)
后者被稱為抽象語(yǔ)法樹(shù)(abstract syntax tree)，它的效率更高，但是不能從中重新得到記號(hào)序列。


2. 簡(jiǎn)單的算術(shù)表達(dá)式的抽象語(yǔ)法樹(shù)的數(shù)據(jù)類型


3. 簡(jiǎn)單算術(shù)文法的二義性解決
例如串34 - 3 * 42，可以有兩種不同的分析樹(shù)：
34 - 3 = 31, 31 * 42
3 * 42 = 126, 34 - 126
解決二義性的方法通常有兩種，一種是設(shè)置消除二義性規(guī)則（disambiguating rule)，如設(shè)置運(yùn)算符的優(yōu)先權(quán)；另一種是將文法限制為只能分析成單一的分析樹(shù)，如將上式表示為34 - (3 * 42)。

設(shè)置運(yùn)算符的優(yōu)先權(quán)
定義如下的簡(jiǎn)單表達(dá)式文法：
exp -> exp addop exp | term
addop -> + | -
term -> term mulop term | factor
mulop -> *
factor -> (exp) | number
這樣乘法被歸在term規(guī)則下，而加減法被歸在exp規(guī)則下，因此在分析樹(shù)和語(yǔ)法樹(shù)中加減法將更接近于根，由此也就接受了更低一級(jí)的優(yōu)先權(quán)。
這樣將算符放在不同的優(yōu)先權(quán)級(jí)別中的辦法是在語(yǔ)法說(shuō)明中使用BNF的一個(gè)標(biāo)準(zhǔn)方法，成為優(yōu)先級(jí)聯(lián)(precedence cascade)。
接下來(lái)的問(wèn)題就是如何讓同級(jí)運(yùn)算從左往右。
可以將表達(dá)式文法改為
exp -> exp addop term | term
addop -> + | -
term -> term mulop factor | factor
mulop -> *
factor -> (exp) | number
這樣就使得加法和減法左結(jié)合，而如果寫成
exp -> term addop exp | term
這樣的形式，則會(huì)使得它們右結(jié)合。

4. else 懸掛的問(wèn)題
簡(jiǎn)單 if 語(yǔ)句的文法
statement -> if-stmt | other
if-stmt -> if (exp) statement | if (exp) statement else statement
exp -> 0 | 1
考慮串 if (0) if (1) other else other
這時(shí)else other的懸掛就出現(xiàn)了二義性，它既可以理解為是if (0)匹配失敗后的選擇，也可以理解為if (0)匹配成功，if (1) 匹配失敗后的結(jié)果。
消除二義性的規(guī)則是
statement -> matched-stmt | unmatched-stmt
matched-stmt -> if (exp) matched-stmt else matched-stmt | other
unmatched-stmt -> if (exp) statement | if (exp) matched-stmt else unmatched-stmt
exp -> 0|1
由這個(gè)定義，上面的串就可以分析為
if (0)  // unmatched-stmt
    if (1) other else other  // matched-stmt

另外一種解決方法就是在語(yǔ)法中解決這個(gè)問(wèn)題。
可以要求出現(xiàn)else部分，或者使用一個(gè)分段關(guān)鍵字(bracketing keyword)，例如
if (1) then
    if (0) then other
    else other
    endif
endif