資源簡介
本程序的所用的存儲結構都是string類型的,最主要的存儲文法的數據結構為自定義結構,里面包括一個產生式的左部,右部以及select集合,至于非終結符的first和follow集合,則是定義了一個string類型的數組進行存儲。
本程序的求first,follow,select集合的算法即為書上所介紹的方法,即求first的集合時,只看本產生式,求follow集合時,要進行遞歸查找一個非終結符的所有后跟字符,求select其實就是對first與follow集合的運算,最終根據所有的select集合,便可以判斷此文法是否為LL(1)文法。
對于不是LL(1)文法的產生式,本程序在判斷后進行轉換,先進行消除左遞歸,然后提取左公因子,在這兩步的每一步結束之后,都要對產生式進行整合,去掉空存儲,去掉無法到達的產生式,將select全部置空。
每進行一次非LL(1)到LL(1)的轉換之后,都要對其文法性質進行判斷,如果是LL(1),則跳出,不是則繼續,但是當循環一定次數之后仍不是,程序判定其無法轉換,也要跳出。
其中還有對第一個非終結字符的右部替換與否進行選擇,原因是,有些通過替換就可以很方便的進行轉換,這個要通過人為進行輸入。
提取公因子中也有上一段所說的類似的判斷機制,目的是為了防止文法的左公因子無法提取完的情況出現。
最終有三種結果,一種是是LL(1)文法,一種是不是LL(1),但是經過轉換變成了LL(1),還有一種是經過轉換也無法變成LL(1)。
輸入文本格式樣例:
A
A->ad
A->Bc
B->aA
B->bB
代碼片段和文件信息
評論
共有 條評論