实验十 LL(1)分析表的构造

原创 2017年12月13日 19:55:39

一、实验目的

学习和掌握FIRST集合、FOLLOW集合的计算,LL(1)分析表的构造方法。

二、实验任务

(1)存储文法;
(2)计算给定文法所有非终结符的FIRST集合;
(3)计算给定文法所有非终结符的FOLLOW集合;
(4)构造该文法的LL(1)文法的分析表并按实验九的文法格式存储;
(5)结合实验九,完成完整的LL(1)分析过程。

三、实验内容

(1)确定文法的文件存储格式,存储文法的非终结符集合、开始符号、终结符集合和产生式规则集合。要求为3个以上测试文法准备好相应的存储文件。
(2)计算给定文法所有非终结符的FIRST集合。
(3)计算给定文法所有非终结符的FOLLOW集合;
(4)构造该文法的LL(1)文法的分析表并按实验九的文法格式存储;
(5)结合实验九,完成完整的LL(1)分析过程。

四、实验结果

文法一:

E -> TY
Y -> +TY | e
T -> FZ
Z -> *FZ | e
F -> (E) | i

测试结果:

这里写图片描述

文法二:

S -> T
T -> (S)ST | e

测试结果:

这里写图片描述

文法三:

S -> iEtST | a
T -> eS | e
E -> b

测试结果:

这里写图片描述

完整代码

#include<iostream>
#include<string>
#include<fstream>
#include<map>
#include<set>
#include<iomanip>
using namespace std;
ifstream input("in1.txt");
map<char,set<char>>first; //first集合
map<char,set<char>>follow; //follo集合
map<char,set<char>>first_temp;
map<char,set<char>>follow_temp;
map<char,set<string>>string_temp;
set<char>table; //终结符号
set<char>no_end; //非终结符
string s[10][10]; //分析表
map<char,int>xlab;
map<char,int>ylab;
void First(){
    string temp;
    while(getline(input,temp)){
         int len = temp.length();
         if(first.find(temp[0])==first.end()){
            int l=5;
            while(temp[l]!='|'&&l<len) l++;
                 if(!(temp[5]>='A'&&temp[5]<='Z'))
                     first[temp[0]].insert(temp[5]);
                 else
                     first_temp[temp[0]].insert(temp[5]);
                 if(l<len&&temp[l]=='|'){
                    if(!(temp[l+2]>='A'&&temp[l+2]<='Z'))
                         first[temp[0]].insert(temp[l+2]);
                    else first_temp[temp[0]].insert(temp[l+2]);
               }
         }
    }
    map<char,set<char>>::iterator it=first_temp.begin();
    while(first_temp.size()!=0){
        set<char>::iterator ij=it->second.begin();
        while(ij!=it->second.end()){
             if(first.find(*ij)!=first.end()){
                set<char>::iterator ik=first[*ij].begin();
                while(ik!=first[*ij].end())
                      first[it->first].insert(*ik),ik++;
                it->second.erase(ij++);
             }
             else ij++;
        }
        if(it->second.size()==0)
           first_temp.erase(it++);
        else
           it++;
        if(it==first_temp.end())
           it=first_temp.begin();
    }
    input.close();
}

void Follow(){
     input.open("in.txt");
     string temp;
     table.insert('$');
     while(getline(input,temp)){
           int l=5,len=temp.length();
           no_end.insert(temp[0]);
           while(l<len-1&&temp[l+1]!=' '){
                 if(!(temp[l]>='A'&&temp[l]<='Z')&&temp[l]!='e')
                     table.insert(temp[l]);
                 if(temp[l]>='A'&&temp[l]<='Z') {
                    follow[temp[l]].insert('$');
                    if(!(temp[l+1]>='A'&&temp[l+1]<='Z'))
                         follow[temp[l]].insert(temp[l+1]);
                    else{
                         int ok=1;
                         set<char>::iterator it=first[temp[l+1]].begin();
                         while(it!=first[temp[l+1]].end()){
                               if(*it!='e')
                               follow[temp[l]].insert(*it);
                               else ok=0;
                               it++;
                         if(!ok)
                            follow_temp[temp[l]].insert(temp[0]);
                        }
                    }

                }
            l++;
          }
          int k=0;
          while(temp[k+5]!='\0'&&temp[k+5]!='|')
                k++;
          if(temp[k+5]=='\0')
              string_temp[temp[0]].insert(temp.substr(5,k));
          else
              string_temp[temp[0]].insert(temp.substr(5,k-1));
          if(temp[k+5]=='|'){
             int y=0;
             while(temp[k+5+y]!='\0')
                   y++;
             string_temp[temp[0]].insert(temp.substr(k+7,y));
          }
          if(l<len&&temp[l]>='A'&&temp[l]<='Z')
             follow_temp[temp[l]].insert(temp[0]);
         while(l<len) {
              if(!(temp[l]>='A'&&temp[l]<='Z')&&temp[l]!=' '&&temp[l]!='|'&&temp[l]!='e')
                   table.insert(temp[l]);
              l++;
         }
     }
    map<char,set<char>>::iterator it=follow_temp.begin();
    while(follow_temp.size()!=0){
        set<char>::iterator ij=it->second.begin();
        while(ij!=it->second.end()){
             if(follow.find(*ij)!=follow.end()){
                set<char>::iterator ik=follow[*ij].begin();
                while(ik!=follow[*ij].end())
                      follow[it->first].insert(*ik),ik++;
                it->second.erase(ij++);
             }
             else
                ij++;
        }
        if(it->second.size()==0)
           follow_temp.erase(it++);
        else
           it++;
        if(it==follow_temp.end())
           it=follow_temp.begin();
    }
    input.close();
}


void show_first(){ //打印FIRST集合
     cout<<"FIRST集合为:"<<endl;
     map<char,set<char>>::iterator it=first.begin();
     while(it!=first.end()){
           cout<<"FIRST"<<"("<<it->first<<")"<<"={ ";
           set<char>::iterator ij=it->second.begin();
           int l=0,len=it->second.size();
           while(ij!=it->second.end()){
            cout<<*ij;ij++;
            if(l<=len-2)
               cout<<" , ";
            l++;
        }
        it++;
        cout<<" }"<<endl;
    }
}

void show_follow(){ //打印FOLLOW集合
     cout<<"FOLLOW集合为:"<<endl;
     map<char,set<char>>::iterator it=follow.begin();
     while(it!=follow.end()){
          cout<<"FOLLOW"<<"("<<it->first<<")"<<"={ ";
          set<char>::iterator ij=it->second.begin();
          int l=0,len=it->second.size();
          while(ij!=it->second.end()){
                cout<<*ij;ij++;
                if(l<=len-2)
                   cout<<" , ";
                l++;
          }
        it++;
        cout<<" }"<<endl;
    }
}

void show_table(){  //打印并存储LL1分析表
    cout<<"LL1分析表为:"<<endl;
    cout<<"---------------------------------------------------"<<endl;
    cout<<"        ";
    set<char>::iterator it=table.begin();
    int k=0;
    while(it!=table.end()){
        ylab[*it]=k++;
        cout<<*it<<"         ";it++;
    }
    cout<<endl;
    it = no_end.begin();
    int l=0;
    while(it!=no_end.end()){
         cout<<*it<<"       ";
         set<char>::iterator ij=table.begin();
         int j=0;
         while(ij!=table.end()){
               set<string>::iterator ik=string_temp[*it].begin();
               int ok=0;
               while(ik!=string_temp[*it].end()){
                    string temp=*ik;
                    if(first[temp[0]].count(*ij)!=0||temp[0]==*ij){
                       ok=1;cout<<*it<<"->"<<temp; s[l][j]=temp;
                       for(int x=temp.length()+3;x<10;x++) cout<<" ";
                     }
                    if(ok==0 &&(first[temp[0]].count('e')!=0||(*ik)[0]=='e')){
                          if(follow[*it].count(*ij)!=0){
                             ok=1;cout<<*it<<"->"<<temp; s[l][j]=temp;
                             for(int x=temp.length()+3;x<10;x++)
                                 cout<<" ";
                          }
                    }
                    ik++;
                }
               if(!ok)
                  cout<<"          ",s[l][j]=" ";
               ij++;
               j++;
          }
         cout<<endl;
         xlab[*it]=l;
         it++;
         l++;
    }

}

int main(){
    First(); //求first集合
    show_first(); //打印first集合
    Follow(); //求follow集合
    show_follow(); //打印follo集合
    show_table(); //打印LL1分析表
}
版权声明:本文为博主原创文章,未经博主允许不得转载。

编译原理(五) LL(1)文法分析法(预测分析表的构造算法C++实现)

基本定义 FIRST(α):FIRST(\alpha): 令G是一个不含左递归的文法,对G的所有非终结符的每个候选α定义它的终结首符集FIRST(α)为: FIRST(α)={a | α=>*a…...
  • qq_24451605
  • qq_24451605
  • 2015年11月28日 20:02
  • 7768

编译原理:LL(1)文法 语法分析器(预测分析表法)

设计要求:对于任意输入的一个LL(1)文法,构造其预测分析表,并对指定输入串分析其是否为该文法的句子。 思路:首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法,再根据FIRST和F...
  • NK_test
  • NK_test
  • 2016年05月22日 20:54
  • 21553

实验九 LL(1)分析

一、实验目的 学习和掌握LL(1)文法的判定和LL(1)分析方法。 二、实验任务 (1)存储文法的LL(1)分析表; (2)根据LL(1)分析表判断文法是否LL(1)文法; (3)实现L...
  • tangyuanzong
  • tangyuanzong
  • 2017年12月13日 18:27
  • 301

LL(1)分析法_C++实现

Code by C++#include #include #include /*******************************************/int count=0; ...
  • shaguabufadai
  • shaguabufadai
  • 2017年05月28日 23:41
  • 359

实验二——自顶向下分析方法之表驱动LL(1)分析程序

自顶向下分析方法之表驱动LL(1)分析程序分为三个部分: 非LL(1)文法转换为LL(1)文法; LL(1)文法的判别; 构造预测分析表和对输入符号串进行分析。 程序流程图:非LL(1)文法转换为LL...
  • liujian20150808
  • liujian20150808
  • 2017年06月02日 10:06
  • 962

编译原理:LL(1)文法 语法分析器(预测分析表法)

设计要求:对于任意输入的一个LL(1)文法,构造其预测分析表,并对指定输入串分析其是否为该文法的句子。 思路:首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法,再根据FIRST和...
  • bfboys
  • bfboys
  • 2016年09月08日 19:02
  • 939

编译原理实现预测分析法(LL(1))

编译原理实现预测分析法(LL(1))
  • ismahui
  • ismahui
  • 2016年12月25日 22:57
  • 1621

编译原理上机作业2——LL(1)语法分析

#include #include #include #include char grammer[200][200]; char terSymbol[200]; char nterSymbo...
  • sambrown123
  • sambrown123
  • 2013年11月03日 20:55
  • 2171

编译原理 实验2 语法分析器的构造 LL(1)

【实验目的】        练习构造语法分析程序的方法,熟悉上下文无关文法的使用,加深对课堂教学的理解;提高词法分析方法的实践能力 【实验要求】     利用某一高级程序设计语言构造语法分...
  • bfboys
  • bfboys
  • 2016年09月13日 22:54
  • 396

编译原理学习笔记·语法分析(LL(1)分析法/算符优先分析法OPG)及例子详解

语法分析(自顶向下/自底向上) LL(1)分析法 算符优先分析法OPG
  • jave_f
  • jave_f
  • 2017年10月18日 20:33
  • 396
内容举报
返回顶部
收藏助手
不良信息举报
您举报文章:实验十 LL(1)分析表的构造
举报原因:
原因补充:

(最多只允许输入30个字)