主題

[創作|作業][C++]編譯器Prob3C：First

極巨龍神塔奇 | 2018-11-29 08:52:40 | 巴幣 0 | 人氣 1422

First 生成

First是在建構Parser時的重要資訊之一，當同時符合多條規則時，能夠用來決定要選擇哪一條規則進行展開。

First的定義如下：

1.若有一Nonterminal A，其規則為A → α1 | α2 | ... | αn ，則First (A) = First (α1) ∪ First (α2) ∪ ... ∪ First (αn)。

2.若有一Right Hand Side (RHS) 為β1β2 ... βn，則First (β1) = First (β1β2 ... βn)。

3.承上，若First (β1) = ε，則First (β2) = First (β1β2 ... βn)，以此類推。

4.承上，若First (βn) = ε，則First (βn) = First (β1β2 ... βn) = ε。

請依據上述規則，計算出讀入Grammar的First Set並印出。

Input

每行開頭為一Nonterminal，隔一個空白後接其規則，不同規則會以新的一行表示。相同Nonterminal若有多條規則，每條皆視為不同規則。其中Nonterminal與Terminal皆為單一字母。

可接受的輸入Token如下：

單一大寫字母A-Z作為Nonterminal

單一小寫字母a-z作為Terminal

;視作空字串ε

$視為EOF（視作是Terminal，不一定會出現在Grammar中，出現再判斷即可）

此題不需考慮規則錯誤或輸入錯誤的情況，請以規則正確的前提來作答。

EX：

S → ABC | dD

A → a

會以下面方式表示

2

S ABC

S dD

A a

Output

依照ASCII編碼由小到大排序Nonterminal和First Set並印出。

每行開頭為Nonterminal，隔一個空白後印出對應的First Set，並在每行以\n作為結尾。

例如A的First Set為abc;，則印出A ;abc。

Nonterminal和First Set皆須按照ASCII由小排到大。

範例輸入：

S ABC

A a

A Cb

A ;

B C

B dA

B ;

C e

C f

C ;

範例輸出：

A ;abef

B ;def

C ;ef

S ;abdef

#include<iostream>
#include<string>
#include<list>

using namespace std;

list<string> nTml[26];
list<char> result[26];

void first(char current)
{
   if(nTml[current-'A'].empty())
   {
      return;
   }
   for(list<string>::iterator it=nTml[current-'A'].begin();it!=nTml[current-'A'].end();it++)
   {
      bool thenext=true;
      for(string::iterator sit=(*it).begin();sit!=(*it).end()&&thenext;sit++)
      {
         thenext=false;
         if(*sit>='A' && *sit<='Z')
         {
            if(result[*sit-'A'].empty())
            {
               first(*sit);
            }
            for(list<char>::iterator cit=result[*sit-'A'].begin();cit!=result[*sit-'A'].end();cit++)
            {
               if(*cit==';')
               {
                  if(sit==(*it).end()-1)
                  {
                     result[current-'A'].push_back(*cit);
                  }
                  thenext=true;
               }
               else
               {
                  result[current-'A'].push_back(*cit);
               }
            }
         }
         else if((*sit>='a' && *sit<='z') || *sit=='$')
         {
            result[current-'A'].push_back(*sit);
         }
         else if(*sit==';')
         {
            thenext=true;
            result[current-'A'].push_back(*sit);
         }
      }
   }
   result[current-'A'].sort();
   result[current-'A'].unique();
}

int main(void)
{
   while(!cin.eof())
   {
      char lToken;
      string rToken;
      cin >> lToken >> rToken;
      nTml[lToken-'A'].push_back(rToken);
   }

   for(char i='A';i<='Z';i++)
   {
      first(i);//look every non-terminal rules
   }

   for(char i='A';i<='Z';i++)
   {
      if(result[i-'A'].empty())
      {
         continue;
      }
      cout << i << " ";
      for(list<char>::iterator it=result[i-'A'].begin();it!=result[i-'A'].end();it++)
      {
         cout << *it;
      }
      cout << endl;
    }

    return 0;
}