<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

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

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

    Posted on 2007-07-27 11:28 ZelluX 閱讀(8261) 評論(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
    主站蜘蛛池模板: 无码天堂亚洲国产AV| 精品一区二区三区免费毛片爱| 亚洲成人免费电影| 久久亚洲精品无码观看不卡| 在线视频免费观看高清| 日韩精品无码免费一区二区三区| 一级做a爱片特黄在线观看免费看| 亚洲1234区乱码| 亚洲天堂一区二区| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 亚洲成av人片天堂网老年人| av无码免费一区二区三区| 国产精品区免费视频| 国产成人无码免费网站| 蜜桃传媒一区二区亚洲AV| 亚洲影视自拍揄拍愉拍| 久久精品亚洲中文字幕无码网站| 亚洲精品黄色视频在线观看免费资源| 午夜影视在线免费观看| 日本阿v免费费视频完整版| 人妻丰满熟妇无码区免费| 国产性生大片免费观看性| 国产精品美女久久久免费 | 日韩精品视频在线观看免费| 亚洲精品乱码久久久久久蜜桃图片| 久久精品国产精品亚洲毛片| 亚洲AV无码乱码在线观看富二代 | 日韩在线视频线视频免费网站| 亚洲午夜无码久久久久小说| 亚洲成年网站在线观看| 亚洲五月综合缴情婷婷| 亚洲码一区二区三区| 亚洲毛片基地日韩毛片基地| 亚洲视频日韩视频| 亚洲精品视频在线观看视频| 日韩精品亚洲人成在线观看| 亚洲精品在线视频观看| 亚洲精品国产手机| 亚洲午夜久久久精品电影院| 亚洲香蕉在线观看| 亚洲成AV人片高潮喷水|