精华内容
下载资源
问答
  • 文章目录1 实验目的和内容1.1 实验目的1.2 实验内容1.3 实验要求2 设计思想2.1 根据BNF描述该文法2.2 根据文法画相应的语法图2.3 判断是否是LL(1)文法---求First、Follow集2.4 递归下降子程序3 算法流程4 源程序5 ...

    1 实验目的和内容

    1.1 实验目的

    (1)给出 PL/0 文法规范,要求编写 PL/0 语言的语法分析程序。

    (2)通过设计、编制、调试一个典型的自上而下语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步 掌握常用的语法分析方法。

    (3)选择最有代表性的语法分析方法,如递归下降分析法、预测分析法; 选择对各种常见程序语言都具备的语法结构,如赋值语句,特别是表达式,作为分析对象。

    1.2 实验内容

    (1)已给 PL/0 语言文法,构造表达式部分的语法分析器。

    (2)分析对象〈算术表达式〉的 BNF 定义如下:

    <表达式> ::= [+|-]<项>{<加法运算符> <项>}

    <项> ::= <因子>{<乘法运算符> <因子>}

    <因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’

    <加法运算符> ::= +|-

    <乘法运算符> ::= *|/

    <关系运算符> ::= =|#|<|<=|>|>=

    1.3 实验要求

    (1)将实验一“词法分析”的输出结果,作为表达式语法分析器的输入,

    进行语法解析,对于语法正确的表达式,报告“语法正确”;对于语

    法错误的表达式,报告“语法错误”, 指出错误原因。

    (2)把语法分析器设计成一个独立一遍的过程。

    (3)采用递归下降分析法或者采用预测分析法实现语法分析。

    2 设计思想

    2.1 根据BNF描述该文法

    (1)对BNF中的各对象简称如下

    B:表达式 C:乘法运算符

    J:加法运算符 N:无符号整数

    X:项 S:标识符

    Y:因子 G:关系运算符

    (2)文法如下

    B->JX(JX)|X(JX)

    X->Y(CY)*

    Y->S|N|(B)

    J->+|-

    C->*|/

    G->=|#|<|<=|>|>=

    2.2 根据文法画相应的语法图

    (1)表达式

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-E4Eno25n-1634695547322)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEAD.tmp.jpg)]

    图1 表达式—语法图

    (2)项

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rAdwgE3F-1634695547328)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEAE.tmp.jpg)]

    图2 项—语法图

    (3)因子

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JuUz14zj-1634695547333)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEAF.tmp.jpg)]

    图3 因子—语法图

    2.3 判断是否是LL(1)文法—求First、Follow集

    (1)改文法没有左递归。

    (2)各非终结符的First、Follow集如下所示

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1Vo8F67r-1634695547338)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEB0.tmp.jpg)]

    (3)根据LL(1)文法的判断规则可知,该文法满足LL(1)文法的条件,所以该文法是LL(1)文法。

    2.4 递归下降子程序

    (1)表达式

    PROCEDUER B;
    BEGIN
      IF SYM = '+' OR SYM = '-' THEN ADVANCE;
      ELSE IF SYM 在 First(X) THEN
      BEGIN
        ADVANCE;
        X;
      END
      ELSE ERROR; 
      WHILE SYM = '+' OR SYM = '-' THEN
      BEGIN
        ADVANCE;
        X;
      END
    END
    

    (2)项

    PROCEDUER X;
    BEGIN
      IF SYM 在 First(Y) THEN
      BEGIN
        ADVANCE;
        Y;
      END
      ELSE ERROR; 
      WHILE SYM = '*' OR SYM = '/' THEN ADVANCE;
      IF SYM 在 First(Y) THEN
      BEGIN 
        ADVANCE;
        Y;
      END
      ELSE ERROR;
    END
    

    (3)因子

    PROCEDUER Y;
    BEGIN
      IF SYM = '(' THEN
      BEGIN
        ADVANCE;
        B;
        ADVANCE;
        IF SYM = ')' THEN ADVANCE;
        ELSE ERROR;
      END
      ELSE IF SYM 在 First(Y) THEN ADVANCE;
      ELSE ERROR;
    END
    

    3 算法流程

    语法分析程序的输入是一个个单词符号的二元组,输出是一个个语法单位,它的任务是在词法分析识别出单词符号串的基础上,分析并判定程序的语法结构是否符合语法规则。

    首先逐行扫描单词符号二元组,然后遍历串的每一个字符,判断字符是不是+或-、*或/、因子的first集,再进行下一步的判断,选择进行表达式分析、项分析和因子分析,并输出相应的语句。如果不符合这几种情况,将会归入出错处理。完整算法流程如下图所示。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hNx9tFQu-1634695547341)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEC0.tmp.jpg)]

    图4 算法流程图

    4 源程序

    #include<iostream>
    #include<string>
    #include<stdlib.h>
    using namespace std; 
    
    #define L 8 
    
    void fac_aly();
    void all_aly();
    
    string input_str[L];//存储单词符号
    int str_i = 0;//访问input_str的下标
    
    //字符串数组下标往前移
    void str_i_adv()
    {
      str_i++;
      if(str_i > L-1)
      {
        cout<<"下标越界,请重新输入!";
        exit(0);
        //重新输入
        string str;
        for(int i=0;i<L-1;i++)
        {
          cin>>str;
          //检测输入的结束
          int zero_id = str.find(',', 0);
          //存储识别出来的字母到字符串数组中
          input_str[i] = str.substr(1, zero_id - 1);
        }
      }
    } 
    
    //对表达式进行分析
    void exp_aly()
    {
      //对表达式中的每一个因子做分析
      fac_aly();
      while(input_str[str_i] == "times" || input_str[str_i] == "slash")
      {
        //数组下标前移
        str_i_adv();
        //对表达式中的每一个因子做分析
        fac_aly();
      }
      return;
    } 
    
    //对表达式中的每一个因子做分析
    void fac_aly()
    {
      //判断是否是字母
      if(input_str[str_i] == "ident")
      {
        //数组下标前移
        str_i_adv();
      }
      //判断是否是数字
      else if(input_str[str_i] == "number")
      {
        //数组下标前移
        str_i_adv();
      }
      //判断是否是左括号
      else if(input_str[str_i] == "lparen")
      {
        //数组下标前移
        str_i_adv();
        //对目前的数组进行整体分析
        all_aly();
        //判断是否是右括号
        if(input_str[str_i] == "rparen")
        {
          //数组下标前移
          str_i_adv();
        }
        else {
          cout<<"ERROR!"<<endl;
          exit(0);
        }
      }
      return;
    }
    
    //对目前的表达式进行整体分析
    void all_aly()
    {
      if(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
        //数组下标前移
        str_i_adv();
      }
      exp_aly();
      while(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
        //数组下标前移
        str_i_adv();
        exp_aly();
      }
      return;
    } 
    
    int main()
    {
      string str;
      //输入词法分析的结果
      for(int i=0;i<L-1;i++)
      {
        cin>>str;
        //检测输入的结束
        int zero_id = str.find(',', 0);
        //存储识别出来的字母到字符串数组中
        input_str[i] = str.substr(1, zero_id - 1);
      } 
      //对字符串数组中的表达式进行分析
      if(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
        //数组下标前移
        str_i_adv();
      }
      //表达式分析
      exp_aly();
      while(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
         //数组下标前移
        str_i_adv();
        //表达式分析
        exp_aly();
      }
      if(str_i == L-1) cout<<"Yes,it is correct."<<endl;
      else cout<<"No,it is wrong.";
      return 0;
    }
    

    5 调试数据

    (1)测试样例如下

    【样例输入】
    (lparen,()
    (ident,a)
    (plus,+)
    (number,15)
    (rparen,))
    (times,*)
    (ident,b) 
    
    【样例输出】
    Yes,it is correct.
    

    (2)测试样例结果如下

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v1QuvnUG-1634695547344)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBED1.tmp.jpg)]

    图5 样例测试结果

    6 思考:词法分析+语法分析

    6.1 将实验一的词法分析作为函数写入语法分析程序

    int main()
    {
      string st1r;
      //输入源程序
      for(int i=0;i<L-1;i++)
      {
        cin>>str1;
        //检测输入的结束
        string str;
        str = fun_cifa(str1);//调用词法分析子程序
        int zero_id = str.find(',', 0);
        //存储识别出来的字母到字符串数组中
        input_str[i] = str.substr(1, zero_id - 1);
      }
      //对字符串数组中的表达式进行分析
      if(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
        //数组下标前移
        str_i_adv();
      }
      //表达式分析
      exp_aly();
      while(input_str[str_i] == "plus" || input_str[str_i] == "minus")
      {
         //数组下标前移
        str_i_adv();
        //表达式分析
        exp_aly();
      }
      if(str_i == L-1) cout<<"Yes,it is correct."<<endl;
      else cout<<"No,it is wrong.";
      return 0;
    }
    

    6.2 调试数据

    【样例输入】
    (a+15)*b
    
    【样例输出】
    (lparen,()
    (ident,a)
    (plus,+)
    (number,15)
    (rparen,))
    (times,*)
    (ident,b)
    Yes,it is correct.
    

    6.3 调试结果

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RRDxtJde-1634695547346)(file:///C:\Users\User\AppData\Local\Temp\ksohtml\wpsBEE2.tmp.jpg)]

    图6 样例测试结果

    7 实验调试情况及体会

    7.1 实验调试情况

    由上两步中的测试样例可以得到,所有的测试样例均得到了相应的输出结果,说明代码编写成功,并且在代码中设置了出错处理,以便解决其他情况。

    本次实验同时也实现了词法分析与语法分析合在一起去识别源程序的程序,但依然存在一些问题,比如语句只能一句一句地去识别,而不能进行整体识别,该问题会在后续过程中加以解决。

    7.2 实验体会

    这次实验采用的方法是自上而下分析中的递归下降分析法,首先画出了递归下降分析的语法图,然后判断文法是否属于LL(1)文法,最后写出了递归下降的子程序,并写出了代码,在代码中即可以调用上次词法分析的程序,直接对输入的字符串进行分割传入字符串str。

    通过这次实验对于LL(1)文法的三个条件有了更深刻的认识,以及加深对于first 和follow 集合的求法,并且独立完成递归调用函数的书写和实现,对于递归思想又有了进一步的认识,要写函数结束出口,防止函数进入死循环。

    通过这次实验进一步了解了自上而下的语法分析:对于输入的词法分析结果,进行左推导,得到一个合法句子或者非法结构,是一种递归和试探的方法,并且自上而下建立输入序列的分析树,而且需要消除左递归并且提取公因子,进一步理解了理论课所学的具体内容,加深对于一些自上而下课后题的理解。这次实验课的收获很大。

    最后,感谢刘善梅老师和其他同学在这次实验中给予我的帮助,不胜感激!

    展开全文
  • 整理陈火旺《编译原理》第五章知识点: 这就引出了可归约串的定义,事实上有多种“可归约串”的定义,从而形成不同的自下而上分析方法。例如算符优先分析中“可归约串”被定义为“最左素短语”,而在“规范规约”...

    整理陈火旺《编译原理》第五章知识点:

    (1)

    在这里插入图片描述
    这就引出了可归约串的定义,事实上有多种“可归约串”的定义,从而形成不同的自下而上分析方法。例如算符优先分析中“可归约串”被定义为“最左素短语”,而在“规范规约”分析中“可归约串”被定义为“句柄。

    还可用分析树展示语法分析过程(P84-85)

    展开全文
  • 自上而下的语法分析(Java描述) 【问题描述】 依据给定的LL(1)文法,识别输入符号串是否是文法的合法句子。 【基本要求】 1、输入 LL(1)文法、待识别的符号串...5、输出识别过程(推导或语法树)及结论。 【测试用例...

    自上而下的语法分析(Java描述)

    【问题描述】
    依据给定的LL(1)文法,识别输入符号串是否是文法的合法句子。

    【基本要求】
    1、输入 LL(1)文法、待识别的符号串。
    2、实现由 LL(1)文法构造 First 集和 Follow 集的算法。
    3、根据First 集和 Follow 集构造相应的预测分析表。
    4、实现预测分析技术的总控程序。
    5、输出识别过程(推导或语法树)及结论。

    【测试用例】

    ∙ \bullet 文法G[S]产生式如下:

    S -> (L) | a
    L -> L,S | S

    ∙ \bullet 我们不难发现给定文法中存在左递归,消除左递归后的文法:(程序中使用‘&’表示空)

    S -> (L) | a
    L -> Sl
    l -> ,Sl | ε \varepsilon ε

    ∙ \bullet 测试输入串:

    合法:(a,(a,a))#
    合法:(a,(a,a),(a,a))#
    非法:(a,(aa))#


    【构造文法First集】

    先声明文法类的数据结构:

        public class WenFa {
        	
    		char BeginSymbol; //文法的开始符
    		StringBuffer terminator; //终结符
    		StringBuffer nonterminator; //非终结符
    		ArrayList<startNode> production; //文法产生式存储入口
    		
    		WenFa(){
    			terminator = new StringBuffer("");
    			nonterminator = new StringBuffer("");
    		}
    	}
    

    构造 First(A)集的步骤如下:
    扫描所有左部为 A 的产生式,

    (1)、若A-> ε \varepsilon ε ,则将 ε \varepsilon ε并入 First(A)。

    (2)、若A->a ,则将 a 并入 First(A)。

    (3)、若A->B……,则将 First(B)并入 First(A)。

    (4)、若A->XB……或A->Xa……,且 X-> ε \varepsilon ε,则类似于(2)、(3)处理。

    下面是文法类(WenFa)所拥有的方法,功能是求一个非终结符的First集:

        //求一个非终结符的first集
        	public HashSet getFirstCollection(char C){
        		
    		HashSet firstSet = new HashSet(); //定义first集
    		for(startNode startnode : production){ //遍历非终结符
    			if(startnode.val==C){ //非终结符匹配
    				Node node = startnode.next;
    				while(node!=null){
    					
    					//遇到终结符,直接加入first集
    					if(isTerminator(node.val)==true){
    						firstSet.add(node.val);
    						while(node.next1!=null) //其他产生式
    							node = node.next1;
    						node = node.next2;
    					}
    					//遇到非终结符
    					else if(isNonterminator(node.val)==true){
    						HashSet ha = new HashSet(getFirstCollection(node.val));
    						ha.remove('&'); //非终结符First集去空
    						firstSet.addAll(ha); //递归调用
    						
    						while(node.next1!=null) //转至其他产生式
    							node = node.next1;
    						node = node.next2;
    					}	
    				}
    			}
    			//System.out.println(firstSet);
    		}
    		return firstSet;
    	}
    

    测试输出First集:



    【构造文法Follow集】

    构造 Follow(A)集的步骤如下:
    扫描所有右部包含 A 的产生式,

    (1)、若 B->xAy ,则将 First(y)中的非 ε \varepsilon ε终极符并入 Follow(A)。

    (2)、若 B->xA,或者 B->xAy 且 y-> ε \varepsilon ε则将 Follow(B)并入 Follow(A)。

    (3)、若A是开始符,则将 ‘#’ 并入 Follow(A)。

    注意:Follow集中是不出现 ε \varepsilon ε

    算法思路:
    在每一个产生式中逐个字符匹配A,若匹配成功则检查A的下一个字符char;

    1、若char是终结符,则将char加入Follow(A)。

    2、若char是非终结符,将First(char)加入Follow(A);若char还可以推出空,将Follow(char)加入Follow(A)。

    3、若char为空,即不存在下一个字符,A是产生式最末端的字符。则将此产生式左端的字符的Follow集加入Follow(A)。此处注意判断此产生式左端的字符与A是否相同,若相同会出现无限递归的情况。注意避免。

    4、对Follow(A)去空。

    求一个非终结符的Follow集算法同样是文法类(WenFa)所有的方法:

        //求一个非终结符的follow集
        public HashSet getFollowCollection(char C){
        		
    		HashSet followSet = new HashSet(); //定义follow集
    		//是开始符号
    		if(C==BeginSymbol)
    			followSet.add('#');
    		
    		for(startNode startnode : production){ //遍历非终结符
    			Node node = startnode.next;
    			while(node!=null){
    				
    				//1当前字符与C匹配成功
    				if(node.val==C){ 
    					//1.1当前字符不在产生式末端
    					if(node.next1!=null){
    						//1.1.1下一个字符是终结符
    						if(isTerminator(node.next1.val)==true){
    							followSet.add(node.next1.val); //情况1:将后一个终结符字符加入
    							//转下一个产生式
    							while(node.next1!=null){
    								node=node.next1;
    							}
    							node = node.next2;
    						}
    						//1.1.2下一个字符是非终结符
    						else{ 
    							//System.out.println("getFirstCollection of "+node.next1.val+" = "+getFirstCollection(node.next1.val));//====
    							followSet.addAll(getFirstCollection(node.next1.val)); //加入非终结符的First集
    							if(getFirstCollection(node.next1.val).contains('&')) //如果此非终结符可推出空
    								followSet.addAll(getFollowCollection(node.next1.val)); //加入Follow集
    							while(node.next1!=null){
    								node=node.next1;
    							}
    							node = node.next2;
    						}
    					}
    					//1.2当前字符在产生式末端
    					else{
    						if(C!=startnode.val){ //此判断避免陷入无限递归
    							//System.out.println("getFollowCollection of "+startnode.val+" = "+getFollowCollection(startnode.val));//====
    							followSet.addAll(getFollowCollection(startnode.val));
    						}
    						node = node.next2;
    					}
    				}
    				
    				//2当前字符与C未匹配成功
    				else{ 
    					if(node.next1!=null) //检验下一个字符
    						node = node.next1;
    					else				//检验下一个产生式
    						node = node.next2;
    				}
    				//System.out.println(followSet);
    			}	
    		}
    		followSet.remove('&'); //集合去空(空用‘&’表示)
    		return followSet;
    	}
    

    测试输出Follow集:

    【构造预测分析表】

    预测分析表中存储的是某一非终结符遇到某一终结符时可使用的关于此非终结符的产生式。

    此处不显式用数组存储预测分析表,只给出相关算法,支持查询相关产生式的功能,代替预测分析表。

    下面算法接受两个字符:一个非终结符statue和一个终结符letter。返回一个StringBuffer类的字符串对应产生式信息。

    1、若letter在First(statue)中,查询左端为statue的产生式:

    (1)若产生式右端第一个字符是letter,搜索成功,返回当前产生式;否则,进行(2)

    (2)若产生式右端第一个字符是非终结符,判断letter是否在这个非终结符的First集中。若在,搜索成功,返回当前产生式。

    2、letter不在First(statue)中但在Follow(statue)中:搜索成功,返回空转换 ε \varepsilon ε

    3、letter既不在First(statue)中又不在Follow(statue)中:搜索完成,返回产生式为空。(输入串错误)

    	//查询预测分析表得到对应产生式
    	public StringBuffer searchProduction(char statue,char letter){
    		StringBuffer pro = new StringBuffer("");
    		
    		//输入字符在当前非终结符的First集中
    		if(getFirstCollection(statue).contains(letter)){
    			for(startNode startnode : production){ //遍历非终结符
    				if(startnode.val==statue){ //定位到非终结符
    					
    					Node node = startnode.next;
    					while(node!=null){
    						
    						if(isTerminator(node.val)==true){ //遇终结符
    							if(node.val==letter) //锁定first集,生成产生式
    							{
    								while(node!=null){
    									pro.append(node.val);
    									node = node.next1;
    								}
    							}
    						}
    						else{ //遇非终结符
    							HashSet set = new HashSet(getFirstCollection(node.val));
    							if(set.contains(letter)){ //锁定first集,生成产生式
    								while(node!=null){
    									pro.append(node.val);
    									node = node.next1;
    								}
    							}
    						}
    						
    						//进行下一产生式
    						if(node!=null){ //避免指针指空
    							while(node.next1!=null)
    								node = node.next1;
    							node = node.next2;
    						}
    					}
    					
    				}
    				
    			}
    			
    		}
    		else{
    			//输入字符在当前非终结符的Follow集中
    			if(getFollowCollection(statue).contains(letter)){
    				pro.append('&'); //空转换
    			}			
    		}
    		return pro;
    	}
    

    【输入串分析】

    根据预测分析过程的特点,定义两个数据结构:

    符号栈:stack,存储分析过程中的匹配符号。

    输入串队列:queue,存储分析过程中的输入串。

    算法步骤:

    1、输入串以字符形式进入队列,’#’ 和文法开始符依次入栈。

    2、设置文法分析循环标志 analyseFlag,并赋初值为0。

    3、弹出stack栈顶元素c1并获取队列queue首个元素c2

    若c1= ‘#’,且c1=c2,则输入串分析成功,文法合法。analyseFlag=1,算法结束。

    若c1= ’#‘,但c1!=c2,则输入串分析成功,文法不合法。analyseFlag=-1,算法结束。

    若c1!= ‘#’,但c1=c2,则表明匹配成功一次,队列queue首元素弹出。

    若c1!= ‘#’,且c1!=c2,则表明此次匹配不成功,查询预测分析表,获取当前已出栈元素和当前队列首元素所对应的产生式。将产生式划分为字符,倒序入栈。若对应的产生式为 ε \varepsilon ε,则空字再紧接着出栈。输出显示stack和queue中的元素,展示分析过程。

    4、若文法分析循环标志 analyseFlag = 0,重复步骤3。

    对输入字符分析的算法同样是文法类(WenFa)所有的方法:

        //对输入串进行语法分析
        	public void AnalyseSentence(StringBuffer inputSen){
        		
    		LinkedList queue = new LinkedList(); //输入串队列
    		for(char c : inputSen.toString().toCharArray()){
    			queue.add(c);
    		}
    		
    		int analyseFlag = 0; //文法分析循环标志
    		Stack stack = new Stack(); //符号栈
    		
    		stack.push('#'); //'#'进栈		
    		stack.push(BeginSymbol); //文法开始符进栈
    		
    		System.out.println(stack);
    		System.out.println(queue);
    		
    		while(analyseFlag == 0){
    
    			char c1 = (char) stack.pop(); //出栈
    			char c2 = (char) queue.getFirst(); //获取队列首元素
    			if(c1=='#'){
    				if(c1==c2){
    					analyseFlag = 1; //分析成功
    					stack.push('#'); //多余一步,为了输出方便观察
    					break;
    				}
    				else{
    					analyseFlag = -1; //分析失败,出现错误
    					break;
    				}
    			}
    			
    			if(c1==c2){
    				queue.pollFirst(); //首元素出队列
    			}
    			
    			//c1!=c2,产生式入栈
    			else{
    				String str = searchProduction(c1,c2).toString();
    				System.out.println("Production = "+str+"\n");
    				if(str!=null){
    					char[] array = str.toCharArray();
    					for(int i=array.length-1;i>=0;i--){
    						stack.push(array[i]); //产生式倒序入栈
    					}
    					if(array.length==1){
    						if(array[0]=='&')
    							stack.pop(); //空字出栈
    					}
    					System.out.print("stack = "+stack+"   ");
    					System.out.print("queue = "+queue+"   ");
    				}
    				else
    					analyseFlag = -1; //出现错误
    			}
    			
    		}
    		System.out.println("\n\nstack = "+stack+"   queue = "+queue);
    		
    		switch(analyseFlag)
    		{
    		case 1:
    			System.out.println("\n分析成功!语句合法!");
    		  break;
    		case 0:
    			System.out.println("\n分析失败...");
    		  break;
    		default:
    			System.out.println("\n分析完成,语句不合法");
    		}
    	}
    	
    



    【实例测试】
    1、输入串为 “(a,(a,a))#”

    2、输入串为 “(a,(aa))#”




    写在最后:

    由于本人水平有限,数据结构设计及算法实现不可避免会有漏洞或不足之处。欢迎大家指出思路和代码中的不足,也期待大佬分享更简洁精巧的代码实现。

    欢迎转载!(注明出处 嘻嘻)

    展开全文
  • 那语法分析是如何判断输入串是否符合语法规则呢,对于自上而下分析而言,从文法的起始符出发进行对句子进行推导,从而进行语法规则的验证,最终产生一个颗正确的语法树。 自上而下分析的基本思想,将输...

    知识点:

      什么是语法分析,语法分析就是在词法分析识别出单词符号的基础上,分析并判断程序的语法结构是否符合语法规范。语法分析的方法有两种类型的方法,自上而下推导和自下而上规约,本章主要讲的是自上而下的推到方法。那语法分析是如何判断输入串是否符合语法规则呢,对于自上而下分析而言,从文法的起始符出发进行对句子进行推导,从而进行语法规则的验证,最终产生一个颗正确的语法树。

      自上而下分析的基本思想,将输入的一个字符串从文法的根节点开始,根据文法自上而下的为输入串建立一颗语法树,即为输入串寻找一个左推导。其本质思想是一个探索过程,是反复使用不同产生式谋求匹配输入串的过程。

      具体方法为为每一个非终结符号对应一个递归子程序,每个子程序根据判断返回真或假。但这种方法存在许多问题,如:

    1. 文法左递归问题:如果P=>Pa,则在没有识别任何输入符号的情况下,又得重新要求P去重新进行新的匹配,这样就造成了无限循环。
    2. 回溯成本问题:匹配不成功,则需要回溯,既费时又费力。
    3. 虚假匹配问题:设有文法(1) S → xAy;(2) A →* | **;分析输入串x**y。若判断A->*,再对下一个*进行匹配时,由于没有了A,则只能推出y。
    4. 不易知出错位置:当最终报告分析不成功是,难以知道输入串中出错的确切位置。
    5. 效率低:因为以上问题,所以得出效率低。

      未解决以上问题,则使用LL(1)分析法,可称为不带回溯的自上而下分析法,即要消除文法的左递归,并找出客服回溯的充分必要条件。

    1. 消除左递归:

            例: 设有产生式
    P→Pα|β (1)
    其中β不以P开头,α不为ε。那么,我们可以把P的规则改为如下的非直接左递归形式:
    P→βP’

    P’→αP’|ε  (2)

            对于(1)式:P=>Pα=>Pαα=>…=>Pαα…α=>βαα…α

            对于(2)式:P=>βP’=>βαP’=>βααP’=>…=>βαα…αP’=> βαα…α

            由此可见,消除左递归后的效果与使用左递归的效果相同。

           间接左递归:

                    例:考虑文法:
            S->Qc|c
                    Q ->Rb|b
                    R ->Sa|a 
            把R带入到Q中有关的候选式:    Q -> Sab|ab|b 

                    现在Q同样不含直接左递归,把它带入S的有关候选式:S ->Sabc|abc|bc|c

          2. 消除回溯:

            之所以会出现回溯,是因为在分析对非终结符号进行递归时,若将错误的终结符被判断成正确,则会接着该错误的结果继续进行下去,如果对该非终结符号所有的候选式进行判断,以此来得到精准的匹配结果。未完成此任务,我们定义first集

        

            同时将文法改造,提取出相同的左公因子。使得候选首符集两两不相交,但如果空字ε属于某个非终结符的候选式的首符集,就会有问题。

        定义follow集:  


     LL(1)文法的使用条件:

             (1)文法不含左递归

    (2)对于文法中每一个非终结符A的各个产生式的候选式的FIRST集两两不相交。即,若
    A→α1|α2|…|αn
    FIRST(αi)∩FIRST(αj)=Φ (i≠j)
    (3)对于文法中的每个非终结符A,若它的某个候选首符集包含ε,则
    FIRST(A)∩FOLLOW(A)=Φ

    如果一个文法G满足以上条件,则称该文法G为LL(1)文法(第1个L代表从左到右扫描输入串,第2个L代表最左推导,1表示分析时每一步只看1个符号)

    LL(1)文法的使用方法:

    对于LL(1)文法,假设要用非终结符A进行匹配,面临输入符号为a,A的所有产生式为 A→α1|α2|…|αn

    (1)若a ∈ FIRST(αi) ,则指派αi去匹配
    (2)若a不属于任何一个候选首符集,则:
    ①若ε属于某个 FIRST(αi)且a∈FOLLOW(A),则让A与ε自动匹配;

    ②否则,a的出现是一种语法错误

            3.预测分析程序:使用分析表和栈对文法进行分析。



    习题:




    感想:

            从这一刻起,我们学会了在编译程序中如何判断语句是否符合语法规范。这一章的重点在于最后的如何构造first集合和follow集合以及如何得到最后的预测分析表。简单来说,first(x)集合是x产生式中第一个终结符,若x产生式中某候选式第一个字符是非终结符号,则将该非终结符号的first集合去掉空集后加入x的候选式中。follow集合,若该符号是开始符号,则加入#,若该符号X中产生式的某一候选式中的最后一个符号是终结符,则将该终结符的first集加入X的follow集合中,若最后一个符号是非终结符号,这将该非终结符号的follow集合加入X的follow集合中去。分析表由文法的所有产生式构造的。

    展开全文
  • (2)通过设计、编制、调试一个典型的自上而下语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步掌握常用的语法分析方法。 (3)选择最有代表性的语法分析方法,如递归下降分析法、...
  • 文章目录一、自上而下分析的一般方法1.描述2.问题二、消除左递归1.定义2.消除直接左递归(1)算法3.1 消除直接左递归(2)例子2.消除左递归(1)算法3.2 消除左递归(2)例子三、提取左因子1.算法3.3 提取文法的左...
  • 编译原理 - 语法分析(1): 自上而下语法分析 为什么我们不用词法分析那一套方式(正则文法、有限状态机等)来解决语法分析? 正则文法通常什么样? 对于文法G=(V, T, S, P),如果产生式的形式如下:...
  • 语法分析是编译过程的核心部分,这一章我们主要学习了自上而下的分析方法进行语法分析,上一章已经对句法有了一定的了解,下一步就是要学好语法分析,这样才能够在后面的学习中部吃力,语法分析也是编译原理最基础的...
  • 整理编译原理笔记 编译原理和形式语言自动机关系很大,可以结合自动机的内容一起看 教材《程序设计语言 编译原理(第3版)》—— 陈火旺 等 个人理解,仅供参考,错误欢迎指出 一、语法分析器的功能 在词法分析...
  • 语法树:语法分析树的浓缩表示,算符和关键字是作为内部节点 语法制导翻译可以基于分析树,也可以基于语法树 构造语法树的语法制导定义 S属性的自下而上 n是结束符号 三,L属性定义的自上而下计算 翻译方案:语法...
  • 今天学习了编译原理中的语法分析-自上而下分析的基本问题这一章节,我参考了国防工业出版社《编译原理》教材1 和中国大学MOOC-国防科技大学《编译原理》的PPT,整理了这一章的内容,希望能够理解这部分的知识。
  • 编译原理-语法分析

    千次阅读 2019-03-29 00:56:33
    1.语法分析概述 1.1 定义 语法分析就是根据高级语言的语法规则对程序的语法结构进行分析。如下图所示: 1.2 任务 ... 语法分析的任务就是在词法分析识别出正确的单词符号串是否符合语言的... 语法分析在编译过程...
  • 或者说,从语法树的末端开始,步步向上规约,直到根结。不带回溯的递归子程序(递归下降)分析方法是自上而下分析法的一种。 文法: 我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器...
  • 目录一、推导与语法树1、语法树2、句型的推导及语法树的生成(自顶向下)3、子树与短语4、树与推导由推导构造语法树语法树构造推导规范归约规范句型二、文法的二义性二义性文法5、Chomsky对文法的分类(1) 0型文法...
  • 编译原理》学习总结--第四章 语法分析 自上而下分析一 知识点 1 移近-规约 用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)...
  • 在上一篇文章中,我们已经得到了LL(1)文法,现在,我们使用java编写递归向下的语法分析程序开建立语法分析。 当一个文法满足LL(1)条件时,我们就可以为它构造一不带回溯的自上而下的分析程序,这个分析程序时由一...
  •  每棵语法树的叶结点自左至右排列就组成一个句型  每棵子树的叶结点自左至右排列就组成一个短语  每棵简单子树的叶结点自左至右排列就组成一个直接短语  每棵最左简单子树的叶结点自左至右排列就组成一个句柄 用...
  • 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、递归下降分析法的前提 改造文法:消除二义性、消除左递归、提取左因子,判断是否为LL(1)文法, 3、递归下降分析法实验设计思想及算法...
  • 编译原理总结

    2018-06-11 08:53:39
    编译原理是计算机专业的一门重要课程,主要介绍在编译程序构造的一般原理和方法,其中有, 编译原理是计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法...
  • 语法分析器在编译原理中占主导地位 语法分析大概分为两类: 自下而上(Bottom-up) 从输入串开始,逐步进行归约,直到文法的开始符号 归约:根据文法的产生式规则,把串中出现的产生式的右部替换成左部符号 从树叶...
  • 语法分析是编译过程的核心部分,其基本任务是根据语言的语法规则进行语法分析,如果不存在语法错误即给出正确的语法结果,并为语义分析和代码生成做准备。 语法分析器的两种方式 语法分析器的任务主要是确定是否...
  • 自上而下:递归下降分析法(LL预测分析法—>推导 自下而上:算符优先分析法(LR分析法—>归约 4.1 语法分析器的功能 4.1.1 语法分析器任务 完成的任务: ① 对词法分析器产生的单词符号进行处理,输出分析 ②与...
  • 一、知识点语法分析器:工作本质是文法的产生式,识别输入符号串是否为一个句子自上而下分析方法:基本思想:对任何输入串,试图用一切可能的方法,从文法开始符号(根结)出发,从上而下地为输入串建立一棵语法树。...
  • 语法分析自下而上语法分析自上而下语法分析3.语义分析 1.词法分析 字母表 字母表Σ是一个有穷符号的集合,包括数字字母和符号 字母表Σ1和Σ2的乘积,是集合内的元素求笛卡尔积 ε表示空串 串 串的...
  • 语法分析---自上而下分析 上一章中,用正规式描述了单词符号的结构,并研究了如何用有限自动机构造词法分析器的问题。由于正规式与正规文法是等价的,它们的描述能力有限,因此将上下文无关文法用作语法分析的基础...
  • 知识总结一、自上而下分析1、基本思想 对任何一个输入串试图用一切可能的办法,从文法的开始符号(根节点)出发,根据文法自上而下地为输入串建立一棵语法树,即为输入串寻找一个最左推导。2、本质:是一种试探过程,...
  • } 运行结果: LL(1)分析法的功能 LL(1)分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及LL(1)分析表,对输入符号串自上而下的分析过程。 LL(1)分析法实验设计思想及算法
  • 语法分析之后,编译的任务是由已识别成功的正确源程序生成一组规格一致,便于计算加工的指令形式。 中间代码的生成方法: 语法制导翻译,属性文法制导翻译 中间代码: 不是机器语言,便于生成机器语言,便于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,769
精华内容 707
关键字:

编译原理自上而下语法树