1. 考慮表達式3 + 4的語法分析樹,exp( exp(number (3)), op(+), exp(number (4)) )。
還有一種更為簡單的表示方法,例如將(34 - 3) * 42表示為*(-(34, 3), 42)
后者被稱為抽象語法樹(abstract syntax tree),它的效率更高,但是不能從中重新得到記號序列。
2. 簡單的算術表達式的抽象語法樹的數據類型
typedef enum {Plus, Minus, Times} OpKind;
typedef enum {OpKind, ConstKind} ExpKind;
typedef struct streenode
{
ExpKind kind;
OpKind op;
struct streenode *lchild, *rchild;
int val;
} STreeNode;
typedef STreeNode *SyntaxTree;
3. 簡單算術文法的二義性解決
例如串34 - 3 * 42,可以有兩種不同的分析樹:
34 - 3 = 31, 31 * 42
3 * 42 = 126, 34 - 126
解決二義性的方法通常有兩種,一種是設置消除二義性規則(disambiguating rule),如設置運算符的優先權;另一種是將文法限制為只能分析成單一的分析樹,如將上式表示為34 - (3 * 42)。
設置運算符的優先權
定義如下的簡單表達式文法:
exp -> exp addop exp | term
addop -> + | -
term -> term mulop term | factor
mulop -> *
factor -> (exp) | number
這樣乘法被歸在term規則下,而加減法被歸在exp規則下,因此在分析樹和語法樹中加減法將更接近于根,由此也就接受了更低一級的優先權。
這樣將算符放在不同的優先權級別中的辦法是在語法說明中使用BNF的一個標準方法,成為優先級聯(precedence cascade)。
接下來的問題就是如何讓同級運算從左往右。
可以將表達式文法改為
exp -> exp addop
term | term
addop -> + | -
term -> term mulop
factor | factor
mulop -> *
factor -> (exp) | number
這樣就使得加法和減法左結合,而如果寫成
exp -> term addop exp | term
這樣的形式,則會使得它們右結合。
4. else 懸掛的問題
簡單 if 語句的文法
statement -> if-stmt | other
if-stmt -> if (exp) statement | if (exp) statement else statement
exp -> 0 | 1
考慮串 if (0) if (1) other else other
這時else other的懸掛就出現了二義性,它既可以理解為是if (0)匹配失敗后的選擇,也可以理解為if (0)匹配成功,if (1) 匹配失敗后的結果。
消除二義性的規則是
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
由這個定義,上面的串就可以分析為
if (0) // unmatched-stmt
if (1) other else other // matched-stmt
另外一種解決方法就是在語法中解決這個問題。
可以要求出現else部分,或者使用一個分段關鍵字(bracketing keyword),例如
if (1) then
if (0) then other
else other
endif
endif