posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          BNF 文法 (1) - 語法樹 | 二義性的解決

          Posted on 2007-07-27 11:28 ZelluX 閱讀(8282) 評(píng)論(2)  編輯  收藏 所屬分類: Courses
          1. 考慮表達(dá)式3 + 4的語法分析樹,exp( exp(number (3)), op(+), exp(number (4)) )。
          還有一種更為簡(jiǎn)單的表示方法,例如將(34 - 3) * 42表示為*(-(34, 3), 42)
          后者被稱為抽象語法樹(abstract syntax tree),它的效率更高,但是不能從中重新得到記號(hào)序列。


          2. 簡(jiǎn)單的算術(shù)表達(dá)式的抽象語法樹的數(shù)據(jù)類型
          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. 簡(jiǎn)單算術(shù)文法的二義性解決
          例如串34 - 3 * 42,可以有兩種不同的分析樹:
          34 - 3 = 31, 31 * 42
          3 * 42 = 126, 34 - 126
          解決二義性的方法通常有兩種,一種是設(shè)置消除二義性規(guī)則(disambiguating rule),如設(shè)置運(yùn)算符的優(yōu)先權(quán);另一種是將文法限制為只能分析成單一的分析樹,如將上式表示為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ī)則下,因此在分析樹和語法樹中加減法將更接近于根,由此也就接受了更低一級(jí)的優(yōu)先權(quán)。
          這樣將算符放在不同的優(yōu)先權(quán)級(jí)別中的辦法是在語法說明中使用BNF的一個(gè)標(biāo)準(zhǔn)方法,成為優(yōu)先級(jí)聯(lián)(precedence cascade)。
          接下來的問題就是如何讓同級(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 懸掛的問題
          簡(jiǎn)單 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
          這時(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

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


          評(píng)論

          # re: BNF 文法 (1) - 語法樹 | 二義性的解決  回復(fù)  更多評(píng)論   

          2011-03-14 22:16 by 過客2011
          比如對(duì)于 if(a) if(b) b1 else b2 else if(c) c1 else c2。如是請(qǐng)回復(fù)。
          guoshuai0020000@gmail.com

          # 樓主給出的消除二義性的if文法任然是二義性的。。。  回復(fù)  更多評(píng)論   

          2011-03-14 22:18 by 過客2011
          比如對(duì)于 if(a) if(b) b1 else b2 else if(c) c1 else c2。如是請(qǐng)回復(fù)。
          guoshuai0020000@gmail.com
          主站蜘蛛池模板: 剑阁县| 平利县| 西吉县| 邵东县| 界首市| 资源县| 娱乐| 通许县| 当雄县| 都安| 大港区| 密云县| 宁海县| 明光市| 陵川县| 元氏县| 天峻县| 铜川市| 台北市| 得荣县| 南康市| 汾阳市| 丽江市| 大邑县| 定襄县| 汉源县| 苏尼特右旗| 京山县| 汾西县| 光泽县| 宁强县| 凌海市| 宣威市| 中超| 鹤壁市| 双牌县| 松潘县| 长宁县| 贡嘎县| 陇川县| 普定县|