以下所說(shuō)的文法文件均為QParserGenerator的文法文件
產(chǎn)生式
我們將文法文件中形如
strings -> strings "{String}"
| "{String}"
;
形式的式子稱(chēng)為產(chǎn)生式，它由它的左端非終結(jié)符（strings）和右端終結(jié)符和非終結(jié)符組成。
非終結(jié)符：非終結(jié)符總是出現(xiàn)在產(chǎn)生式的左端，它表示這個(gè)條目是由右側(cè)的一些終結(jié)符和非終結(jié)符推導(dǎo)而來(lái)的。
終結(jié)符：終結(jié)符總是出現(xiàn)在產(chǎn)生式的右端，一般的它總是一個(gè)常量字符串或Regex，在文法文件中由最頂端的%token定義出來(lái)，內(nèi)部有一些內(nèi)置的Regex比如"{Digit}"對(duì)應(yīng)正則表達(dá)式為[0-9]+。
上面的文法可分解為兩條產(chǎn)生式
strings -> strings "{String}";
strings -> "{String}";
在文法文件中遇到或的關(guān)系就可將這條產(chǎn)生式分為若干條左端相同的產(chǎn)生式，只是為了書(shū)寫(xiě)形式上的好看，所以在QParserGenerator中支持了|符號(hào)。
產(chǎn)生式的結(jié)構(gòu)
首先我們定義出一種結(jié)構(gòu)來(lái)描述一個(gè)終結(jié)符或非終結(jié)符
struct Item
{
enum Type
{
TerminalSymbol,
NoTerminalSymbol,
}type;
Rule rule;
uint index;
#if defined(_DEBUG) && DEBUG_LEVEL == 3
string name;
#endif
Item() : type(NoTerminalSymbol), index(inc()) {}
Item(Rule::Context* pContext) : type(TerminalSymbol), rule(pContext), index(0) {}
#if defined(_DEBUG) && DEBUG_LEVEL == 3
Item(const string& name) : type(NoTerminalSymbol), index(inc()), name(name) {}
#endif
Item(const Item& i)
: type(i.type)
, rule(i.rule)
, index(i.index)
#if defined(_DEBUG) && DEBUG_LEVEL == 3
, name(i.name)
#endif
{
}
Item(const Rule& rule) : type(TerminalSymbol), rule(rule), index(inc()) {}
inline Item& operator=(const Item& i)
{
if (&i != this)
{
type = i.type;
rule = i.rule;
index = i.index;
#if defined(_DEBUG) && DEBUG_LEVEL == 3
name = i.name;
#endif
}
return *this;
}
inline const bool operator<(const Item& x)const
{
return index < x.index;
}
inline const bool operator==(const Item& x)const
{
return index == x.index && type == x.type && (type == TerminalSymbol ? rule == x.rule : true);
}
inline const bool operator!=(const Item& x)const
{
return (index != x.index || type != x.type) || (type == TerminalSymbol ? rule != x.rule : false);
}
inline const bool isNoTerminalSymbol()const
{
return type == NoTerminalSymbol;
}
inline const bool isTermainalSymbol()const
{
return type == TerminalSymbol;
}
static uint inc()
{
static uint i = 0;
return i++;
}
};
只有一個(gè)非終結(jié)符對(duì)象才會(huì)用到rule成員對(duì)象。
有了這個(gè)基本類(lèi)型之后，讓我們來(lái)構(gòu)造出一條產(chǎn)生式的結(jié)構(gòu)
class Production
{
public:
Production() {}
Production(const Item& left) : left(left), index(inc()) {}
Production(const Item& left, const Item& item) : left(left), index(inc()) { right.push_back(item); }
Production(const Item& left, const vector<Item>& right) : left(left), right(right), index(inc()) {}
Production(const Production& p) : left(p.left), right(p.right), index(p.index) {}
inline const bool operator<(const Production& p)const
{
return index < p.index;
}
protected:
static uint inc()
{
static uint i = 0;
return i++;
}
public:
Item left;
vector<Item> right;
uint index;
};
正如前面所說(shuō)，每條產(chǎn)生式的左端總是一個(gè)非終結(jié)符，而右端是若干的終結(jié)符或非終結(jié)符，應(yīng)此我們有了以上結(jié)構(gòu)。
LALR1的產(chǎn)生式
在LALR1中由于每條產(chǎn)生式是帶若干個(gè)展望符和圓點(diǎn)的，應(yīng)此我們?cè)O(shè)計(jì)另外一個(gè)繼承自Production的結(jié)構(gòu)LALR1Production
class LALR1Production :
public LR0Production
{
typedef LR0Production parent;
public:
class Item
{
public:
enum { Rule, End }type;
regex::Rule rule;
Item() : type(End) {}
Item(
const regex::Rule& rule) : type(Rule), rule(rule) {}
inline
const bool operator==(
const Item& x)
const
{
return type == x.type && (type == End ?
true : rule == x.rule);
}
inline
const bool operator==(
const Production::Item& x)
const
{
return type == End ?
false : rule == x.rule;
}
inline
const bool operator!=(
const Item& x)
const
{
return type != x.type || (type == End ?
true : rule != x.rule);
}
Item&
operator=(
const Item& x)
{
if (&x ==
this)
return *
this;
type = x.type;
if (type == Rule) rule = x.rule;
return *
this;
}
};
LALR1Production() : LR0Production() {}
LALR1Production(
const Production::Item& left,
const vector<Production::Item>& right) : LR0Production(left, right) {}
LALR1Production(
const Production::Item& left,
const Production::Item& right, size_t pos) : LR0Production(left, right, pos) {}
LALR1Production(
const LALR1Production& p) : LR0Production(p), wildCards(p.wildCards) {}
LALR1Production(
const LR0Production& p) : LR0Production(p) {}
LALR1Production(
const Production& p, size_t pos) : LR0Production(p, pos) {}
inline
const bool operator==(
const LALR1Production& p)
const
{
return static_cast<LR0Production>(*
this) == static_cast<LR0Production>(p);
}
inline LALR1Production stepUp()
{
LALR1Production x(*
this);
++x.idx;
return x;
}
public:
vector<Item> wildCards;
};
由于歷史上的原因我們讓LALR1Production繼承自LR0Production而不是Production，在LR0Production中只是增加了idx域來(lái)表示圓點(diǎn)的位置。而對(duì)于增廣的產(chǎn)生式（指begin->. 開(kāi)始符號(hào))總是只帶展望符$的，應(yīng)此我們有了其中的Item結(jié)構(gòu)來(lái)表示它是結(jié)束符$或是其他的rule。
有了上面兩個(gè)結(jié)構(gòu)之后，我們便可以開(kāi)始實(shí)現(xiàn)從產(chǎn)生式轉(zhuǎn)換到DFA的過(guò)程了。
LALR1的狀態(tài)和邊
LALR1的每個(gè)狀態(tài)中包含有若干條LALR1的產(chǎn)生式應(yīng)此它的結(jié)構(gòu)就很簡(jiǎn)單了
class Item
{
public:
vector<LALR1Production> data;
uint idx;
Item() : idx(0) {}
void mergeWildCards(Item* pItem)
{
#if defined(_DEBUG) && DEBUG_LEVEL == 3
if (data.size() != pItem->data.size()) throw error<const char*>("compare size error", __FILE__, __LINE__);
#endif
for (size_t i = 0, m = data.size(); i < m; ++i)
{
data[i].wildCards.add_unique(pItem->data[i].wildCards);
}
}
inline const bool operator==(const Item& x)const
{
return data == x.data;
}
static uint inc()
{
static uint i = 0;
return i++;
}
};
struct Edge
{
Item* pFrom;
Item* pTo;
Production::Item item;
Edge(Item* pFrom, Item* pTo, const Production::Item& item) : pFrom(pFrom), pTo(pTo), item(item) {}
inline const bool operator==(const Edge& x)const
{
return pFrom == x.pFrom && pTo == x.pTo && item == x.item;
}
};
而LALR1的一條邊是由一個(gè)狀態(tài)通過(guò)一個(gè)文法符號(hào)抵達(dá)另一個(gè)狀態(tài)的，所以它也非常形象。
LALR1 DFA生成算法
網(wǎng)上流傳著非常多的LALR1 DFA生成算法，其中有比較費(fèi)時(shí)的先生成LR1狀態(tài)機(jī)然后合并同心集來(lái)轉(zhuǎn)化到LALR1 DFA的算法，也有較快的展望符傳播算法，出于性能的考慮，我們?cè)谶@里選用的是第二種算法。
算法描述：
首先是自生展望符的計(jì)算過(guò)程和DFA的生成過(guò)程
1.拓廣文法begin->. 開(kāi)始符號(hào)，并求取它的closure閉包，并將生成的LALR1項(xiàng)目加入到隊(duì)列q和items列表中。
2.從隊(duì)列q中拿出一個(gè)項(xiàng)目item，并求出這個(gè)item中所有的狀態(tài)轉(zhuǎn)移符號(hào)s。
3.對(duì)這個(gè)item和每個(gè)狀態(tài)轉(zhuǎn)移符號(hào)應(yīng)用go函數(shù)求出由這個(gè)item可以轉(zhuǎn)換到的其他狀態(tài)newItem。
4.若轉(zhuǎn)移到的狀態(tài)newItem不在items列表當(dāng)中將其加入到隊(duì)列q和items列表中，否則合并新生成狀態(tài)newItem和items中原有的對(duì)應(yīng)狀態(tài)oldItem的展望符列表，并將原有狀態(tài)oldItem加入到changes列表中。
5.添加一條從item到newItem或oldItem的邊，它通過(guò)一個(gè)文法符號(hào)x來(lái)轉(zhuǎn)換。
6.循環(huán)2直到隊(duì)列q為空。
下面是傳播展望符的部分
7.遍歷changes列表，并求出每個(gè)狀態(tài)的狀態(tài)轉(zhuǎn)移符號(hào)s。
8.遍歷每個(gè)狀態(tài)轉(zhuǎn)移符號(hào)并應(yīng)用go函數(shù)求出新產(chǎn)生的狀態(tài)newItem，由于新計(jì)算出來(lái)的狀態(tài)newItem必定在items列表中，我們只需要將它的展望符做合并即可。
LALR1的核
LALR1的核是由增廣項(xiàng)目"begin->. 開(kāi)始符號(hào)“通過(guò)某些文法所產(chǎn)生的一些LALR1的最小狀態(tài)，比如有文法
begin -> start
start -> start "a"
start -> "a"
它的核為
K0:
begin -> . start
K1:
begin -> start .
start -> start . "a"
K2:
start -> "a" .
K3:
start -> start "a" .
K0通過(guò)文法符號(hào)start到達(dá)K1，K1通過(guò)其中的另外一條產(chǎn)生式到達(dá)K2（通過(guò)closure函數(shù)可求出這個(gè)產(chǎn)生式，將會(huì)在下文介紹），K1中第二條表達(dá)式通過(guò)文法符號(hào)"a"到達(dá)核K3。應(yīng)此我們說(shuō)LALR1的核就是增廣文法通過(guò)一些文法符號(hào)所產(chǎn)生的一些最小狀態(tài)，然后通過(guò)閉包函數(shù)closure可求出這個(gè)狀態(tài)包含的所有產(chǎn)生式集。
closure（閉包）函數(shù)
通過(guò)閉包函數(shù)可求出LALR1最小狀態(tài)中拓展出來(lái)的其他產(chǎn)生式，應(yīng)此它有一個(gè)核作為輸入和一個(gè)LALR1狀態(tài)作為輸出，它的算法描述如下
1.將核中的所有產(chǎn)生式加入輸出狀態(tài)item中，并將每條產(chǎn)生式加入隊(duì)列q中。
2.從隊(duì)列q中取出一個(gè)元素p。
3.若p是一個(gè)待約項(xiàng)目（圓點(diǎn)右邊是一個(gè)非終結(jié)符）那么繼續(xù)執(zhí)行4，否則循環(huán)到2。
4.求這個(gè)產(chǎn)生式的AFirst集合記作v。
5.遍歷所有左側(cè)是p圓點(diǎn)之后非終結(jié)符且圓點(diǎn)不在最左側(cè)的產(chǎn)生式i。
6.若求出的AFirst集合v為空，則將p的展望符集中的所有元素插入到i中，否則將v中的每個(gè)元素插入到i中。
7.若i已存在于輸出狀態(tài)item則將它的展望符合并到原產(chǎn)生式中，否則將這個(gè)產(chǎn)生式i插入到輸出狀態(tài)item和隊(duì)列q中。
8.循環(huán)2知道隊(duì)列q為空為止。
通過(guò)以上函數(shù)便可求出每個(gè)核K所對(duì)應(yīng)的LALR1狀態(tài)item。
AFirst函數(shù)
AFirst函數(shù)其實(shí)就是求這個(gè)產(chǎn)生式圓點(diǎn)后第二個(gè)符號(hào)的First集合。
First函數(shù)
First函數(shù)返回的是一些終結(jié)符的集合，應(yīng)此若輸入的是一個(gè)非終結(jié)符，它會(huì)去查看所有左端是這個(gè)非終結(jié)符的產(chǎn)生式的右側(cè)第一個(gè)符號(hào)，若它仍然是一個(gè)非終結(jié)符則繼續(xù)遞歸下去，否則將這個(gè)終結(jié)符加入到輸出集合中。而為了不產(chǎn)生死循環(huán)，它不會(huì)處理左遞歸的產(chǎn)生式。
go（狀態(tài)轉(zhuǎn)移）函數(shù)
狀態(tài)轉(zhuǎn)移函數(shù)有兩個(gè)輸入分別為某個(gè)狀態(tài)item和一個(gè)文法符號(hào)x以及一個(gè)輸出newItem，表明item狀態(tài)通過(guò)文法符號(hào)x達(dá)到newItem狀態(tài)。它的算法描述如下
1.遍歷item中的每條產(chǎn)生式i。
2.若i不是一個(gè)歸約項(xiàng)目（圓點(diǎn)在最后）則將其加入集合j中。
3.若集合j不為空，則求取j的閉包作為輸出狀態(tài)newItem。
當(dāng)然通過(guò)go函數(shù)求出來(lái)的新?tīng)顟B(tài)是有可能已經(jīng)存在的。
通過(guò)上面這些算法的描述，我們已經(jīng)可以求出一個(gè)完整的LALR1 DFA了。下面我們來(lái)看看這些算法的代碼會(huì)是什么樣的。
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;
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);
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();
}
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);
destruct(pNewItem, has_destruct(*pNewItem));
Item_Alloc::deallocate(pNewItem);
}
}
}
return true;
}
LALR1::Item* LALR1::closure(
const vector<LALR1Production>& kernel)
{
Item* pItem = Item_Alloc::allocate();
construct(pItem);
queue<LALR1Production> q;
for (vector<LALR1Production>::const_iterator i = kernel.begin(), m = kernel.end(); i != m; ++i)
{
pItem->data.push_back(*i);
q.push(*i);
}
while (!q.empty())
{
const LALR1Production& p = q.front();
if (p.idx < p.right.size() && p.right[p.idx].isNoTerminalSymbol())
// 待約項(xiàng)目
{
vector<Production::Item> v;
firstX(p, v, p.idx + 1);
for (vector<LALR1Production>::iterator i = inputProductions[p.right[p.idx]].begin(), m = inputProductions[p.right[p.idx]].end(); i != m; ++i)
{
if (i->idx > 0)
continue;
LALR1Production& item = *i;
if (v.empty()) item.wildCards.add_unique(p.wildCards);
else
{
for (vector<Production::Item>::const_iterator j = v.begin(), n = v.end(); j != n; ++j)
{
item.wildCards.push_back_unique(LALR1Production::Item(j->rule));
}
}
vector<LALR1Production>::iterator j = find(pItem->data.begin(), pItem->data.end(), item);
if (j == pItem->data.end())
{
q.push(item);
pItem->data.push_back(item);
}
else j->wildCards.add_unique(item.wildCards);
}
}
q.pop();
}
return pItem;
}
void LALR1::firstX(
const LALR1Production& p, vector<Production::Item>& v, size_t idx)
{
if (idx >= p.right.size())
return;
first(p, v, idx);
}
void LALR1::first(
const LALR1Production& p, vector<Production::Item>& v, size_t idx)
{
#ifdef _DEBUG
if (idx >= p.right.size())
{
throw error<
const char*>("position out of right size", __FILE__, __LINE__);
return;
}
#endif
if (p.right[idx].isTermainalSymbol())
{
v.push_back_unique(p.right[idx]);
return;
}
for (vector<LALR1Production>::const_iterator i = inputProductions[p.right[idx]].begin(), m = inputProductions[p.right[idx]].end(); i != m; ++i)
{
if (i->left == i->right[0])
continue;
if (i->right[0].isTermainalSymbol())
{
v.push_back_unique(i->right[0]);
continue;
}
else
{
first(*i, v, 0);
}
}
}
void LALR1::symbols(Item* pItem, vector<Production::Item>& v)
{
for (vector<LALR1Production>::const_iterator i = pItem->data.begin(), m = pItem->data.end(); i != m; ++i)
{
if (i->idx < i->right.size()) v.push_back_unique(i->right[i->idx]);
}
}
bool LALR1::go(Item* pItem,
const Production::Item& x, Item*& newItem)
{
vector<LALR1Production> j;
for (vector<LALR1Production>::iterator i = pItem->data.begin(), m = pItem->data.end(); i != m; ++i)
{
if (i->idx < i->right.size() && i->right[i->idx] == x) j.push_back_unique(i->stepUp());
// fromItoJ(*i, j);
}
if (j.empty())
return false;
newItem = closure(j);
return true;
}
其實(shí)代碼并不算多，只是描述起來(lái)有些麻煩罷了。
QParserGenerator就先介紹到這里，接下來(lái)一篇文章將會(huì)介紹一個(gè)例子來(lái)說(shuō)明某個(gè)文法是如何變成LALR1 DFA的。最后完整的代碼可到
http://code.google.com/p/qlanguage/下載。
posted on 2013-05-12 22:32
lwch 閱讀(2617)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
QLanguage