lwch
【QQ:510134884】【Email:lwch748@gmail.com】

隨筆-91 評(píng)論-137 文章-0 trackbacks-0

接上一篇，首先需要修正的是在DFA生成算法中的傳播部分，應(yīng)該需要有個(gè)循環(huán)一直傳播到不能傳播為止，在多次實(shí)驗(yàn)中表明，有些展望符是通過第2，3，4甚至更多次傳播得來的。

應(yīng)此，相應(yīng)的make函數(shù)變成了

  bool LALR1::make()
    {
        vector<LALR1Production> v;
        v.push_back(inputProductions[begin][0]);
        pStart = closure(v);
        pStart->idx = Item::inc();
        context.states.insert(pStart);
        items.push_back(pStart);

        queue<Item*> q;
        q.push(pStart);

        vector<Item*> changes;

        bool bContinue = false;
        while (!q.empty())
        {
            Item* pItem = q.front();
            vector<Production::Item> s;
            symbols(pItem, s);
            select_into(s, vts, compare_production_item_is_vt, push_back_unique_vector<Production::Item>);
            select_into(s, vns, compare_production_item_is_vn, push_back_unique_vector<Production::Item>);
            for (vector<Production::Item>::const_iterator i = s.begin(), m = s.end(); i != m; ++i)
            {
                Item* pNewItem = NULL;
                if (go(pItem, *i, pNewItem))
                {
                    long n = itemIndex(pNewItem);
                    if (n == -1)
                    {
                        pNewItem->idx = Item::inc();
                        q.push(pNewItem);
                        items.push_back(pNewItem);
                        context.states.insert(pNewItem);
                    }
                    else
                    {
                        items[n]->mergeWildCards(pNewItem, bContinue);
                        changes.push_back_unique(items[n]);
                        destruct(pNewItem, has_destruct(*pNewItem));
                        Item_Alloc::deallocate(pNewItem);
                    }
                    edges[pItem].push_back_unique(Edge(pItem, n == -1 ? pNewItem : items[n], *i));
                }
            }
            q.pop();
        }
        while (bContinue)
        {
            vector<Item*> v;
            v.reserve(changes.size());
            bContinue = false;
            for (vector<Item*>::const_iterator i = changes.begin(), m = changes.end(); i != m; ++i)
            {
                vector<Production::Item> s;
                symbols(*i, s);
                for (vector<Production::Item>::const_iterator j = s.begin(), n = s.end(); j != n; ++j)
                {
                    Item* pNewItem = NULL;
                    if (go(*i, *j, pNewItem))
                    {
                        long n = itemIndex(pNewItem);
                        if (n == -1) throw error<const char*>("unknown item", __FILE__, __LINE__);
                        else
                        {
                            items[n]->mergeWildCards(pNewItem, bContinue);
                            v.push_back_unique(items[n]);
                            destruct(pNewItem, has_destruct(*pNewItem));
                            Item_Alloc::deallocate(pNewItem);
                        }
                    }
                }
            }
            changes = v;
        }
    }

在merge函數(shù)中，會(huì)檢測(cè)有沒有新生成的展望符來決定是否繼續(xù)傳播下去。

一個(gè)示例
下面我們用一個(gè)例子來說明LALR1 DFA是如何生成的，首先它的文法如下

S -> L "=" R
  | R "+"
  | R
  ;

L -> "*" R
  |  "id"
  ;

R -> L
  ;

根據(jù)之前的算法，我們先來看自生的部分

首先我們寫出這個(gè)文法的增廣文法

begin -> . S (#)

求取它的閉包得到

begin -> . S
wildCards:
#
S -> . L "=" R
wildCards:
#
S -> . R "+"
wildCards:
#
S -> . R
wildCards:
#
L -> . "*" R
wildCards:
"=" "+"
L -> . "id"
wildCards:
"=" "+"
R -> . L
wildCards:
"+" #

我們觀察到，其中有5個(gè)可轉(zhuǎn)移的符號(hào)，分別為S、L、R、"*"和"id"，我們分別用go函數(shù)對(duì)這5個(gè)轉(zhuǎn)移符號(hào)求出新的狀態(tài)

首先用符號(hào)S求出新狀態(tài)

begin -> S
wildCards:
#

由于這個(gè)狀態(tài)不在原有列表中，應(yīng)此它是一個(gè)新生成的狀態(tài)，我們?yōu)樗砑右粭l通過符號(hào)S轉(zhuǎn)移的邊。

接下來用符號(hào)L求出新狀態(tài)

S -> L . "=" R
wildCards:
#
R -> L
wildCards:
"+" #

這個(gè)狀態(tài)也不在原有列表中，應(yīng)此它也是一個(gè)新生成的狀態(tài)，我們?yōu)樗砑右粭l通過符號(hào)L轉(zhuǎn)移的邊。

然后用符號(hào)R求出新狀態(tài)

S -> R . "+"
wildCards:
#
S -> R
wildCards:
#

這個(gè)狀態(tài)也不在原有列表中，應(yīng)此它也是一個(gè)新生成的狀態(tài)，我們?yōu)樗砑右粭l通過符號(hào)R轉(zhuǎn)移的邊。

然后用符號(hào)*求出新的狀態(tài)

L -> "*" . R
wildCards:
"=" "+"
R -> . L
wildCards:
"+" # "="
L -> . "*" R
wildCards:
"=" "+" #
L -> . "id"
wildCards:
"=" "+" #

同樣的它也不在原有的列表中，我們同樣為其添加一條通過符號(hào)*轉(zhuǎn)移的邊。

然后是符號(hào)id的

L -> "id"
wildCards:
"=" "+"

同樣不在列表中，我們?yōu)槠涮砑右粭l通過符號(hào)id轉(zhuǎn)移的邊。

這樣，從start狀態(tài)轉(zhuǎn)移出來的5條邊就生成好了，下面來看看這5個(gè)新生成的狀態(tài)又會(huì)生成一些什么呢

begin -> S
wildCards:
#

由第一個(gè)狀態(tài)可知，它沒有任何的邊。

S -> L . "=" R
wildCards:
#
R -> L
wildCards:
"+" #

第二個(gè)狀態(tài)則有一個(gè)=的轉(zhuǎn)移，它生成了一個(gè)新狀態(tài)

S -> L "=" . R
wildCards:
#
R -> . L
wildCards:
"+" # "="
L -> . "*" R
wildCards:
"=" "+" #
L -> . "id"
wildCards:
"=" "+" #

S -> R . "+"
wildCards:
#
S -> R
wildCards:
#

第三個(gè)狀態(tài)有一個(gè)+的轉(zhuǎn)移，它生成了一個(gè)新狀態(tài)

S -> R "+"
wildCards:
#

L -> "*" . R
wildCards:
"=" "+"
R -> . L
wildCards:
"+" # "="
L -> . "*" R
wildCards:
"=" "+" #
L -> . "id"
wildCards:
"=" "+" #

第四個(gè)狀態(tài)有4個(gè)轉(zhuǎn)移，分別為R、L、*和id

1.通過符號(hào)R轉(zhuǎn)移到新狀態(tài)

L -> "*" R
wildCards:
"=" "+"

2.通過符號(hào)L轉(zhuǎn)移到新狀態(tài)

R -> L
wildCards:
"+" # "="

3.通過*則可轉(zhuǎn)移到它自己

4.通過id轉(zhuǎn)移到第5個(gè)狀態(tài)

第五個(gè)狀態(tài)則沒有任何的轉(zhuǎn)移。

S -> L "=" . R
wildCards:
#
R -> . L
wildCards:
"+" # "="
L -> . "*" R
wildCards:
"=" "+" #
L -> . "id"
wildCards:
"=" "+" #

第六個(gè)狀態(tài)有4個(gè)轉(zhuǎn)移，分別為R、L、*和id

1.通過符號(hào)R可轉(zhuǎn)移到新狀態(tài)

S -> L "=" R
wildCards:
#

2.通過符號(hào)L可轉(zhuǎn)移到狀態(tài)9

3.通過符號(hào)*可轉(zhuǎn)移到狀態(tài)4

4.通過符號(hào)id可轉(zhuǎn)移到狀態(tài)5

第6、7、8個(gè)狀態(tài)都沒有任何轉(zhuǎn)移

然后讓我們來看下changes列表里有哪些東西，根據(jù)上一篇的算法可知，所有已存在的狀態(tài)都在changes列表里，應(yīng)此它里面應(yīng)該會(huì)有4、5和9三個(gè)狀態(tài)。

至此，整個(gè)自生的部分完成了，下面我們將其畫成一張圖

下面是傳播部分
在第一次傳播時(shí)changes列表里有3個(gè)狀態(tài)，分別對(duì)這3個(gè)狀態(tài)用go函數(shù)求出新的展望符，并把它們合并到原有的狀態(tài)上。

首先看狀態(tài)4，它有4個(gè)狀態(tài)轉(zhuǎn)移符，分別是R、L、*和id

1.通過符號(hào)R可轉(zhuǎn)移到狀態(tài)8，同時(shí)它的展望符如下

L -> "*" R
wildCards:
"=" "+" #

2.通過符號(hào)L可轉(zhuǎn)移到狀態(tài)9，同時(shí)它的展望符如下

R -> L
wildCards:
"+" # "="

3.通過符號(hào)*可轉(zhuǎn)移到它自己，同時(shí)它的展望符如下

L -> "*" . R
wildCards:
"=" "+" #
R -> . L
wildCards:
"+" # "="
L -> . "*" R
wildCards:
"=" "+" #
L -> . "id"
wildCards:
"=" "+" #

4.通過符號(hào)id可轉(zhuǎn)移到狀態(tài)5，同時(shí)它的展望符如下

L -> "id"
wildCards:
"=" "+" #

然后我們來看一下狀態(tài)5和9，它們沒有任何狀態(tài)轉(zhuǎn)移符，應(yīng)此它們不會(huì)傳播任何展望符。

現(xiàn)在changes列表里有4個(gè)狀態(tài)，分別為8、9、4和5，又由于第8個(gè)狀態(tài)已經(jīng)產(chǎn)生了新的展望符#應(yīng)此需要繼續(xù)傳播

第二次傳播

首先先看狀態(tài)8和9，它們沒有任何狀態(tài)轉(zhuǎn)移符，應(yīng)此它們不會(huì)傳播任何展望符。

然后來看狀態(tài)4，同樣的它有4個(gè)狀態(tài)轉(zhuǎn)移符，分別為R、L、*和id。

1.通過符號(hào)R可轉(zhuǎn)移到狀態(tài)8，同時(shí)它的展望符如下

L -> "*" R
wildCards:
"=" "+" #

2.通過符號(hào)L可轉(zhuǎn)移到狀態(tài)9，同時(shí)它的展望符如下

R -> L
wildCards:
"+" # "="

3.通過符號(hào)*可轉(zhuǎn)移到它自己，同時(shí)它的展望符如下

L -> "*" . R
wildCards:
"=" "+" #
R -> . L
wildCards:
"+" # "="
L -> . "*" R
wildCards:
"=" "+" #
L -> . "id"
wildCards:
"=" "+" #

4.通過符號(hào)id可轉(zhuǎn)移到狀態(tài)5，同時(shí)它的展望符如下

L -> "id"
wildCards:
"=" "+" #

最后我們來看狀態(tài)5，它沒有任何狀態(tài)轉(zhuǎn)移符，應(yīng)此它不會(huì)傳播任何展望符。

現(xiàn)在changes列表里同樣有4個(gè)狀態(tài)，分別為8、9、4和5，由于沒有一個(gè)狀態(tài)產(chǎn)生了新的展望符，應(yīng)此它將不會(huì)繼續(xù)傳播下去了。

現(xiàn)在整個(gè)文法的DFA就生成完畢了，讓我們來修改一下原先的那張圖來看看最終的DFA是什么樣的。

整個(gè)示例就先介紹到這里，在接下來的一篇文章中將會(huì)通過幾個(gè)示例來介紹closure和go函數(shù)的原理，希望這種由粗到細(xì)的講解順序能夠被讀者所接受。最后完整的代碼可到http://code.google.com/p/qlanguage下載。

posted on 2013-05-30 23:04 lwch 閱讀(1591) 評(píng)論(2) 編輯收藏引用所屬分類: QLanguage

評(píng)論:

# re: QParserGenerator代碼分析二(A fix&An example) 2013-05-30 23:36 | eryar

圖片看不全…… 回復(fù) 更多評(píng)論

# re: QParserGenerator代碼分析二(A fix&An example) 2013-05-31 10:12 | lwch

@eryar
這個(gè)好像是模板的問題，改了一下圖片的大小。回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


相關(guān)文章: QParserGenerator的文法文件介紹 QParserGenerator代碼分析二(A fix&An example) QParserGenerator代碼分析一(生成LALR1 DFA) 詞法分析器2(ε-NFA到DFA的轉(zhuǎn)換) 詞法分析器1(正則表達(dá)式到ε-NFA的轉(zhuǎn)換) 修復(fù)了一個(gè)關(guān)于CParser_Input的Bug QLanguage的AST QLanguage基本語法 ESEngine_Demo5 ESEngine_Demo4

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理