精华内容
下载资源
问答
  • 递归下降分析程序构造方法

    千次阅读 2016-05-25 22:25:49
    递归下降分析程序构造方法 作业要求   对于文法 E -> E + T | E – T | T T ->T * F | T / F | F F -> (E) | i 取消左递归后,改为: E ->TE’ E’ -> +TE’ | -TE’ |ε T ->FT’ T’ -> *FT’ | /FT’|...

    递归下降分析程序构造方法


    作业要求

     

    对于文法

    E -> E + T | E – T | T

    T ->T * F | T / F | F

    F -> (E) | i

    取消左递归后,改为:

    E ->TE’

    E’-> +TE’ | -TE’ |ε

    T ->FT’

    T’-> *FT’ | /FT’|ε

    F ->(E) | i

    经证明,该文法为LL(1)方法。

     

    请同学们根据第4章的递归下降分析程序构造方法或者预测分析法,为该文法构造程序。该程序的功能为,给定输入,程序按照先后顺序将使用的产生式输出。

    如,输入25.6 * 14.5 + 2(首先经过词法分析,将其转化为 i * i + i),则输出

    E->TE’

    T->FT’

    F->i

    T’->*FT’

    F->i

    T’->ε

    E’->+TE’

    T->FT’

    F-->i

    T’->ε

    E’->ε

     

    提示:

     在验证程序正确性时,要考虑语法正确的串和语法不正确的串。

    如: 正确的串有:

               25.6 * 14.5 + 2    i * i + i

               2 / 5.2 + 78 - 6    i / i + i - i

         错误的串有:

               2 / 5.2 + 78 –     i / i + i -    

               +56 * 7         + i * i

    对于给定的输入,大家可以通过手写推导过程,然后再核对计算机输出的产生式顺序的方法,检验程序写的对错。


    Java代码解决:

    <pre name="code" class="java">package Bianyiyuanli.ThirdWeek;
    
    import java.util.Scanner;
    /*
     * 运行提示: 输入整数或小数以空格和换行分开,最多支持5个字符长度的表达式:
     * 如:12.3 * 6 + 5 
     * 
     */
    public class Up_Down_Word {
    	
    	private static int index = 0;
    	private static String[] string = new String[6];
    
    	static void E() {
    		// E ->TE’
    		T();
    		E1();
    		System.out.println("E ->TE’");
    	}
    
    	static void E1() {
    		// E’-> +TE’| -TE’ |ε
    		if (string[index].equals("+")) {
    			index++;
    			T();
    			E1();
    			System.out.println("E’-> +TE’");
    		} else if (string[index].equals("-")) {
    			index++;
    			T();
    			E1();
    			System.out.println("E’-> -TE’");
    		}
    	}
    
    	static void T() {
    		// T->FT’
    		F();
    		T1();
    	}
    
    	static void T1() {
    		// T’->*FT’ | /FT’|ε
    		if (string[index].equals("*")) {
    			index++;
    			F();
    			T1();
    			System.out.println("T’->*FT’");
    		} else if (string[index].equals("/")) {
    			index++;
    			F();
    			T1();
    			System.out.println("T’->/FT’");
    		}
    	}
    
    	static void F() {
    		// F ->(E) | i
    		if (string[index].equals("i")) {
    			index++;
    			System.out.println("F->i");
    		} else if (string[index].equals("(")) {
    			index++;
    			E();
    			if (string[index].equals(")")) {
    				index++;
    				System.out.println("F->(E)");
    			} else {
    				System.out.println("分析失败");
    			}
    		} else {
    			System.out.println("分析失败");
    		}
    	}
    
    	public static void main(String[] args) {
    
    		Scanner sc = new Scanner(System.in);
    		//System.out.println("请输入算数表达式");
    		while (!sc.equals("----")) {
    			System.out.println("请输入算数表达式");
    			string[5] = "#";
    			for (int i = 0; i < 5; i++) {
    				string[i] = sc.next();
    				try {
    					if (string[i].matches("^(-?\\d+)(\\.\\d+)?$")) {
    						string[i] = "i";
    					} else if (string[i].matches("^-?\\d+$")) {
    						string[i] = "i";
    					}
    				} catch (Exception e) {
    				}
    			}
    			E();
    			System.out.println("正确语句");
    			//string.notifyAll();
    		}
    	}
    }
    

    
    

    运行结果:






    展开全文
  • #include<iostream> usingnamespacestd; charA[100];//用于存放符号串 inti=0;//扫描指针 charsym;//用于保存当前要判断的字符 boolflag=0;//用于判断该输入是否匹配 voidE();//E ......
    #include <iostream>
    using namespace std;
    char A[100];    //用于存放符号串
    int i=0;        //扫描指针
    char sym;        //用于保存当前要判断的字符
    bool flag=0;    //用于判断该输入是否匹配
    void E();   // E
    void EE();  // E'
    void T();   // T
    void TT();  // T'
    void F();   // F
    void advance();        //从字符串数组中读入一个字符
    void main( )
    {
        cout
    <<"\n多读入的结束字符为#\n\n"
        cin
    >>A;    
        cout
    <<"\n***************************************\n\n"
        sym
    =A[0];
        E();
        
    if(sym!='#'){
            
    if(flag==1)
            {
                cout
    <<"\n该输入串不匹配\n\n";        
            }
            
    else
            {
                cout
    <<"\n该输入串匹配\n\n";            
            }
        }
    }
    void E()
    {
        T();
        EE();
    }
    void EE()
    {
        
    if(sym=='+')
        {
            advance();
            T();
            EE();
        }
        
    }
    void T()
    {
        F();
        TT();
    }
    void TT()
    {
        
    if(sym=='*')
        {
            advance();
            F();
            TT();
        }
        
    }
    void F()
    {
        
    if(sym=='i')
            advance();
        
    else
        {
            
    if(sym=='(')
            {
                advance();
                E();
                
    if(sym==')')
                    advance();
                
    else
                    flag
    =1;
            }
            
    else
                flag
    =1;
        }
        
    }
    void advance()
    {
        i
    ++;
        sym
    =A[i];
        
    if(sym=='#')
        {
            
    if(flag==1)
            {
                cout
    <<"\n该输入串不匹配\n\n";        
            }
            
    else
            {
                cout
    <<"\n该输入串匹配\n\n";            
            }
        }
        
    }

    转载于:https://www.cnblogs.com/DonePuzzle/archive/2008/05/10/1191346.html

    展开全文
  • /*题目:自顶向下分析法(递归下降分析程序构造) *说明:功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 *作者:董正荣 *邮箱:chinadongzr@163.com *开发环境:VC6.0 *时间:2011-5-21 */ #...
    /*题目:自顶向下分析法(递归下降分析程序构造)
     *说明:功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。
    *作者:董正荣 *邮箱:chinadongzr@163.com *开发环境:VC6.0 *时间:2011-5-21 */ #include<stdio.h> #include<string.h> //全局变量 char exp[30],gra[30],prod[30]="",chExp='#'; int expSize=0,graSize=0,step=0; //函数声明 /*(1)E->TG (2)G->+TG|-TG|ε (3)T->FS (4)S->*FS|/FS|ε (5)F->(E)|i */ int E(); int T(); int G(); int S(); int F(); //功能函数实现 /*打印文法*/ void printGrammar() { printf("\t\t\t 递归下降分析程序构造\n\t\t(作者:董正荣,邮箱:chinadongzr@163.com)\n"); printf("-----------------------------------------------------------\n"); printf("\t\t\t (1)E->TG\n"); printf("\t\t\t (2)G->+TG|-TG|ε\n"); printf("\t\t\t (3)T->FS\n"); printf("\t\t\t (4)S->*FS|/FS|ε\n"); printf("\t\t\t (5)F->(E)|i\n"); printf("-----------------------------------------------------------\n"); } void GetExp() { printf("请输入表达式:(以#结束)\t"); gets(exp);//获得输入表达式 expSize=strlen(exp); chExp=exp[0]; printf("----------------------------------------------------------\n"); //puts(exp);//显示 } void printHead() { printf("步骤:\t 语法栈:\t\t输入串:\t产生式:\n"); } void printStep() { printf("%d\t%-20s %10s\t \t%-15s\n",step,gra,exp,prod); strcpy(prod,""); step++; if(chExp=='#'&&gra[graSize-1]=='#') { printf("\n表达式分析成功!\n"); } } //语法栈入栈,匹配的语法产生式顺序入栈 void pushGraStack(char* ch) { for(int i=0;i<strlen(ch);i++) { gra[graSize]=ch[strlen(ch)-1-i]; graSize++; } } //语法栈出栈,返回字符ch char popGraStack() { char ch; ch=gra[graSize-1]; gra[graSize-1]='\0'; graSize--; return ch; } //表达式出栈,匹配字符ch void nextChar() { for(int i=0;i<expSize-1;i++) { exp[i]=exp[i+1]; } exp[expSize-1]='\0'; expSize--; chExp=exp[0]; printf("当前chExp=:%c\n",chExp); } //初始化语法栈 void InitGra() { gra[graSize]='#'; graSize++; gra[graSize]='E'; graSize++; printStep(); } //错误打印 void printError() { printf("\n表达式不匹配!\n"); } //主程序 void main() { printGrammar();//输出文法 GetExp();//获取输入表达式 printHead();//打印题头 InitGra();//初始化语法栈 E(); printf("Recursive Down Analyse App!\n"); } /*(1)E->TG (2)G->+TG|-TG|ε (3)T->FS (4)S->*FS|/FS|ε (5)F->(E)|i */ int E() { popGraStack(); char graE[]="TG"; pushGraStack(graE); strcpy(prod,"E-->TG"); printStep(); T(); G(); return 1; } /*(1)E->TG (2)G->+TG|-TG|ε (3)T->FS (4)S->*FS|/FS|ε (5)F->(E)|i */ int T() { popGraStack(); char graT[]="FS"; pushGraStack(graT); strcpy(prod,"T-->FS"); printStep(); F(); S(); return 1; } /*(1)E->TG (2)G->+TG|-TG|ε (3)T->FS (4)S->*FS|/FS|ε (5)F->(E)|i */ int G() { if(chExp=='+'||chExp=='-') { popGraStack(); char graG[]={chExp,'T','G','\0'}; pushGraStack(graG); strcpy(prod,"G-->"); strcat(prod,graG); printStep(); popGraStack(); nextChar(); strcpy(prod,"匹配"); printStep(); T(); G(); return 1; } else { strcpy(prod,"G-->ε"); printStep(); popGraStack(); strcpy(prod,"匹配"); printStep(); return 1; } } /*(1)E->TG (2)G->+TG|-TG|ε (3)T->FS (4)S->*FS|/FS|ε (5)F->(E)|i */ int F() { if(chExp=='(') { popGraStack(); char graF[]="(E)"; pushGraStack(graF); strcpy(prod,"F-->(E)"); printStep(); popGraStack(); nextChar(); strcpy(prod,"匹配"); printStep(); E(); if(chExp==')') { popGraStack(); nextChar(); strcpy(prod,"匹配"); printStep(); return 1; } else { printError(); return 0; } } else if(chExp=='i') { strcpy(prod,"F-->i"); printStep(); //nextChar(); popGraStack(); nextChar(); strcpy(prod,"匹配"); printStep(); return 1; } else { printError(); return 0; } } /*(1)E->TG (2)G->+TG|-TG|ε (3)T->FS (4)S->*FS|/FS|ε (5)F->(E)|i */ int S() { if(chExp=='*'||chExp=='/') { popGraStack(); char graS[]={chExp,'F','S','\0'}; pushGraStack(graS); strcpy(prod,"S-->"); strcat(prod,graS); printStep(); popGraStack(); nextChar(); strcpy(prod,"匹配"); printStep(); F(); S(); return 1; } else { strcpy(prod,"S-->ε"); printStep(); popGraStack(); strcpy(prod,"匹配"); printStep(); return 1; } }

    转载于:https://www.cnblogs.com/MichaelDongzr/archive/2011/05/21/2052547.html

    展开全文
  • 感觉学习资料还不全,模仿了一个类似简单程序,还有点不完整,等到后面再完善吧。 不含左递归和每个非终结符的所有候选式的终结首符集都两两不相交条件 暂时先放在一边,也是后面再回头理解。

    感觉学习资料还不全,模仿了一个类似简单程序,还有点不完整,等到后面再完善吧。


    不含左递归每个非终结符的所有候选式的终结首符集都两两不相交条件
    暂时先放在一边,也是后面再回头理解。
























    展开全文
  • 词法分析程序scaner( ),sym;error( ) 每个函数名是相应的非终结符,函数体是根据右部符号串的结构编写。 当遇到终结符时,则编写语句if(当前读入的符号==a)则读入下一个单词当遇到非终结符A时,则编写语句调用A...
  • 【20200416】编译原理课程课业打卡十六之构造预测分析表&递归下降分析程序 一、课业打卡十六之构造预测分析表&递归下降分析程序 二、知识巩固 1、预测分析表构造步骤 2、预测分析表【LL(1)分析表】的构造实例详解 3...
  • 递归下降分析程序

    2016-12-16 21:36:00
    练习构造递归下降语法分析程序的方法,熟悉上下文无关文法的使用,加深对课堂教学的理解;提高语法分析方法的实践能力 二、 实验内容和要求 利用c语言构造语法分析程序 三、 实验方法、步骤及结...
  • 对文法 G: E→E+T|T 构造出G的递归下降分析程序。程序显示输出 T→T*F|F 匹配过程(即自上而下生成语法分析树的步骤, F→(E)|i 输出各匹配产生式序号即可)。
  • 掌握最基本的自顶向下分析方法,即递归下降程序方法,理解其特点和适用范围(回溯,左递归等现象),锻炼递归调用程序构造方法。
  • 练习构造递归下降语法分析程序的方法,熟悉上下文无关文法的使用,加深对课堂教学的理解;提高语法分析方法的实践能力 二、实验内容和要求 对于给定的文法G[E] E->TE’ E’->+TE’ | ε T->FT’...
  • 1、实验目的:  ...编程实现给定算术表达式的递归下降分析器。  算术表达式文法如下:  E-->E+T|T  T-->T*F|F  F-->(E)|i  3、设计说明:  首先改写文法为LL(1)文法;然后为每一个非终结符,构造相应
  • 编译原理|递归下降分析程序

    千次阅读 2019-12-10 00:13:35
    递归下降分析程序 一、实验目的 掌握最基本的自顶向下分析方法,即递归下降子程序方法,理解其特点和适用范围(回溯,左递归等现象),锻炼递归调用程序构造方法。 二、实验内容 给定CP语言中简单算术表达式...
  • 递归下降分析程序

    千次阅读 2010-11-25 18:13:00
    【实验内容】 文法:E→E+T | T,T→T*F | F,F→(E) | i 根据该文法编写递归下降分析程序: 1. 输入:任意符号串。 2. 处理:递归调用分析输入串是否合法。 3. 输出:串是否...
  • 文法:E->TE' E'->+TE'|ε T->FT' T'->*FT'|ε F->(E)|i 构造上述LL(1)文法的递归下降分析程序
  • 题目要求: 掌握最基本的自顶向下分析方法,即递归下降程序方法,理解其特点和适用范围(回溯,左递归等现象),锻炼递归调用程序构造方法。
  • 递归下降分析

    千次阅读 2020-03-18 19:25:35
    根据某一文法编制调试递归下降分析程序,以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验预习提示 1、递归下降分析法的功能 词法分析器的功能是利用函数之间的递归...
  • 递归下降分析

    2013-06-04 22:25:29
    递归下降分析器的设计与实现:根据算术表达式的语法定义,设计相应的文法...将该文法改造为LL(1)文法,并构造相应的递归下降分析程序。该程序能够对输入字符串进行语法分析,并输出“语法正确”或“语法错误”的结果。
  • 2. 算符优先文法关系表的构造; 3. 算符优先分析算法的设计。 四、 实验步骤 1. 准备  阅读课本有关章节,确定算术表达式的文法,设计出算符优先关系表上机;  考虑好设计方案;  设计出模块结构、测试数据,...
  • 递归下降分析程序设计实验目的实验内容函数定义程序流程图源代码测试用例 实验目的   掌握最基本的自顶向下分析方法,即递归下降子程序方法,理解其特点和适用范围(回溯,左递归等现象),锻炼递归调用程序的...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 178
精华内容 71
关键字:

递归下降分析程序构造