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