以下所說的文法文件均為QParserGenerator的文法文件
產(chǎn)生式
我們將文法文件中形如
strings -> strings "{String}"
| "{String}"
;
形式的式子稱為產(chǎn)生式，它由它的左端非終結符（strings）和右端終結符和非終結符組成。
非終結符：非終結符總是出現(xiàn)在產(chǎn)生式的左端，它表示這個條目是由右側的一些終結符和非終結符推導而來的。
終結符：終結符總是出現(xiàn)在產(chǎn)生式的右端，一般的它總是一個常量字符串或Regex，在文法文件中由最頂端的%token定義出來，內(nèi)部有一些內(nèi)置的Regex比如"{Digit}"對應正則表達式為[0-9]+。
上面的文法可分解為兩條產(chǎn)生式
strings -> strings "{String}";
strings -> "{String}";
在文法文件中遇到或的關系就可將這條產(chǎn)生式分為若干條左端相同的產(chǎn)生式，只是為了書寫形式上的好看，所以在QParserGenerator中支持了|符號。
產(chǎn)生式的結構
首先我們定義出一種結構來描述一個終結符或非終結符
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++;
}
};
只有一個非終結符對象才會用到rule成員對象。
有了這個基本類型之后，讓我們來構造出一條產(chǎn)生式的結構
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;
};
正如前面所說，每條產(chǎn)生式的左端總是一個非終結符，而右端是若干的終結符或非終結符，應此我們有了以上結構。
LALR1的產(chǎn)生式
在LALR1中由于每條產(chǎn)生式是帶若干個展望符和圓點的，應此我們設計另外一個繼承自Production的結構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域來表示圓點的位置。而對于增廣的產(chǎn)生式（指begin->. 開始符號)總是只帶展望符$的，應此我們有了其中的Item結構來表示它是結束符$或是其他的rule。
有了上面兩個結構之后，我們便可以開始實現(xiàn)從產(chǎn)生式轉換到DFA的過程了。
LALR1的狀態(tài)和邊
LALR1的每個狀態(tài)中包含有若干條LALR1的產(chǎ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的一條邊是由一個狀態(tài)通過一個文法符號抵達另一個狀態(tài)的，所以它也非常形象。
LALR1 DFA生成算法
網(wǎng)上流傳著非常多的LALR1 DFA生成算法，其中有比較費時的先生成LR1狀態(tài)機然后合并同心集來轉化到LALR1 DFA的算法，也有較快的展望符傳播算法，出于性能的考慮，我們在這里選用的是第二種算法。
算法描述：
首先是自生展望符的計算過程和DFA的生成過程
1.拓廣文法begin->. 開始符號，并求取它的closure閉包，并將生成的LALR1項目加入到隊列q和items列表中。
2.從隊列q中拿出一個項目item，并求出這個item中所有的狀態(tài)轉移符號s。
3.對這個item和每個狀態(tài)轉移符號應用go函數(shù)求出由這個item可以轉換到的其他狀態(tài)newItem。
4.若轉移到的狀態(tài)newItem不在items列表當中將其加入到隊列q和items列表中，否則合并新生成狀態(tài)newItem和items中原有的對應狀態(tài)oldItem的展望符列表，并將原有狀態(tài)oldItem加入到changes列表中。
5.添加一條從item到newItem或oldItem的邊，它通過一個文法符號x來轉換。
6.循環(huán)2直到隊列q為空。
下面是傳播展望符的部分
7.遍歷changes列表，并求出每個狀態(tài)的狀態(tài)轉移符號s。
8.遍歷每個狀態(tài)轉移符號并應用go函數(shù)求出新產(chǎn)生的狀態(tài)newItem，由于新計算出來的狀態(tài)newItem必定在items列表中，我們只需要將它的展望符做合并即可。
LALR1的核
LALR1的核是由增廣項目"begin->. 開始符號“通過某些文法所產(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通過文法符號start到達K1，K1通過其中的另外一條產(chǎn)生式到達K2（通過closure函數(shù)可求出這個產(chǎn)生式，將會在下文介紹），K1中第二條表達式通過文法符號"a"到達核K3。應此我們說LALR1的核就是增廣文法通過一些文法符號所產(chǎn)生的一些最小狀態(tài)，然后通過閉包函數(shù)closure可求出這個狀態(tài)包含的所有產(chǎn)生式集。
closure（閉包）函數(shù)
通過閉包函數(shù)可求出LALR1最小狀態(tài)中拓展出來的其他產(chǎn)生式，應此它有一個核作為輸入和一個LALR1狀態(tài)作為輸出，它的算法描述如下
1.將核中的所有產(chǎn)生式加入輸出狀態(tài)item中，并將每條產(chǎn)生式加入隊列q中。
2.從隊列q中取出一個元素p。
3.若p是一個待約項目（圓點右邊是一個非終結符）那么繼續(xù)執(zhí)行4，否則循環(huán)到2。
4.求這個產(chǎn)生式的AFirst集合記作v。
5.遍歷所有左側是p圓點之后非終結符且圓點不在最左側的產(chǎn)生式i。
6.若求出的AFirst集合v為空，則將p的展望符集中的所有元素插入到i中，否則將v中的每個元素插入到i中。
7.若i已存在于輸出狀態(tài)item則將它的展望符合并到原產(chǎn)生式中，否則將這個產(chǎn)生式i插入到輸出狀態(tài)item和隊列q中。
8.循環(huán)2知道隊列q為空為止。
通過以上函數(shù)便可求出每個核K所對應的LALR1狀態(tài)item。
AFirst函數(shù)
AFirst函數(shù)其實就是求這個產(chǎn)生式圓點后第二個符號的First集合。
First函數(shù)
First函數(shù)返回的是一些終結符的集合，應此若輸入的是一個非終結符，它會去查看所有左端是這個非終結符的產(chǎn)生式的右側第一個符號，若它仍然是一個非終結符則繼續(xù)遞歸下去，否則將這個終結符加入到輸出集合中。而為了不產(chǎn)生死循環(huán)，它不會處理左遞歸的產(chǎn)生式。
go（狀態(tài)轉移）函數(shù)
狀態(tài)轉移函數(shù)有兩個輸入分別為某個狀態(tài)item和一個文法符號x以及一個輸出newItem，表明item狀態(tài)通過文法符號x達到newItem狀態(tài)。它的算法描述如下
1.遍歷item中的每條產(chǎn)生式i。
2.若i不是一個歸約項目（圓點在最后）則將其加入集合j中。
3.若集合j不為空，則求取j的閉包作為輸出狀態(tài)newItem。
當然通過go函數(shù)求出來的新狀態(tài)是有可能已經(jīng)存在的。
通過上面這些算法的描述，我們已經(jīng)可以求出一個完整的LALR1 DFA了。下面我們來看看這些算法的代碼會是什么樣的。
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())
// 待約項目
{
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;
}
其實代碼并不算多，只是描述起來有些麻煩罷了。
QParserGenerator就先介紹到這里，接下來一篇文章將會介紹一個例子來說明某個文法是如何變成LALR1 DFA的。最后完整的代碼可到
http://code.google.com/p/qlanguage/下載。
posted on 2013-05-12 22:32
lwch 閱讀(2556)
評論(1) 編輯 收藏 引用 所屬分類:
QLanguage