posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理
          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ù)類型
          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,可以有兩種不同的分析樹(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


          評(píng)論

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

          2011-03-14 22:16 by 過(guò)客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 過(guò)客2011
          比如對(duì)于 if(a) if(b) b1 else b2 else if(c) c1 else c2。如是請(qǐng)回復(fù)。
          guoshuai0020000@gmail.com
          主站蜘蛛池模板: 灵丘县| 准格尔旗| 宾川县| 黄平县| 舞钢市| 漳平市| 刚察县| 林芝县| 汤原县| 衡东县| 临泽县| 北票市| 霍山县| 苗栗县| 乐亭县| 沽源县| 金山区| 繁昌县| 颍上县| 广宗县| 赞皇县| 沙田区| 兴和县| 西吉县| 凤翔县| 合阳县| 云浮市| 望都县| 共和县| 延寿县| 凤山市| 芜湖市| 金平| 兴宁市| 金塔县| 郎溪县| 新蔡县| 正宁县| 晋州市| 乐亭县| 买车|