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

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

          Posted on 2007-07-27 11:28 ZelluX 閱讀(8264) 評論(2)  編輯  收藏 所屬分類: Courses
          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


          評論

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

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

          # 樓主給出的消除二義性的if文法任然是二義性的。。。  回復  更多評論   

          2011-03-14 22:18 by 過客2011
          比如對于 if(a) if(b) b1 else b2 else if(c) c1 else c2。如是請回復。
          guoshuai0020000@gmail.com
          主站蜘蛛池模板: 铁岭县| 英德市| 罗城| 马边| 济源市| 莱州市| 钟山县| 齐齐哈尔市| 永福县| 屯留县| 阿坝县| 六盘水市| 台中县| 德保县| 大悟县| 大洼县| 通渭县| 盐亭县| 车险| 双牌县| 中宁县| 上虞市| 尖扎县| 东港市| 郸城县| 台南市| 怀仁县| 宁都县| 石城县| 常德市| 巴东县| 禄丰县| 平安县| 贵阳市| 兴仁县| 宁阳县| 准格尔旗| 金昌市| 大悟县| 花莲县| 汉源县|