递归下降实现LL(1)文法分析C语言与Python实现

冷不防 2022-03-26 00:37 246阅读 0赞

对文法G的句子进行确定的自顶向下语法分析的充分必要条件是，G的任意两个具有相同左部的产生式A—>α|β 满足下列条件：  
（1）如果α、β均不能推导出ε，则 FIRST(α) ∩ FIRST(β) = ∅。  
（2）α 和 β 至多有一个能推导出 ε。  
（3）如果 β \*═> ε，则 FIRST(α) ∩ FOLLOW(A) = ∅。  
将满足上述条件的文法称为LL(1)文法。  
例子：  
E->TE’  
E’->+TE’ | ε  
T->FT’  
T’->\*F T’| ε  
F->(E) | i  
**C语言代码：**

#include<stdio.h>
    
    #include<string>
    char str[10];
    int index=0;
    void E();			//E->TX;
    void X();			//X->+TX | e
    void T();			//T->FY
    void Y();			//Y->*FY | e
    void F();			//F->(E) | i
    int main()
    {
    	int len;
    	int m;
    	printf("请输入要测试的次数：");
    	scanf("%d",&m);
    	while(m--)
    	{
    		printf("请输入算数表达式：");
    		scanf("%s",str);
    		len=strlen(str);
    		str[len]='#';
    		str[len+1]='\0';
    		E();
    		printf("正确语句！\n");
    		strcpy(str,"");
    		index=0;
    	}
    	return 0;
    }
    void E()
    {
        T();
        X();
    }
    void X()
    {
    	if(str[index]=='+')
    	{
    	    index++;
    		T();
    		X();
    	} 
    }
    void T()
    {
    	F();
    	Y();
    }
    void Y()
    {
    	if(str[index]=='*')
    	{
            index++;
    		F();
    		Y();
    	}
    }
    void F()
    {
    	if(str[index]=='i')
    	{
    		index++;
    	}
    	else if (str[index]=='(')
    	{	 
    		index++;
    		E();
    		if(str[index]==')')
    		{
    			index++; 
    		}else{
    			printf("\n分析失败!\n");
    			exit (0);
    		}
    	} 
    	else{
    		printf("分析失败!\n"); 
    		exit(0);
    	}
     }

**Python代码：**

'''
    E->TM
    M->+TM|~
    T->FN
    N->*FN|~
    F->i|(E)
    '''
    
    
    import time
    index = 0
    
    
    def ParseE():
        ParseT()
        ParseM()
    
    
    def ParseM():
        global index
        if strx[index] == '+':
            index += 1
            ParseT()
            ParseM()
    
    
    def ParseT():
        ParseF()
        ParseN()
    
    
    def ParseN():
        global index
        if strx[index] == '*':
            index += 1
            ParseF()
            ParseN()
    
    
    def ParseF():
        global index
        if strx[index] == 'i':
            index += 1
        elif strx[index] == '(':
            index += 1
            ParseE()
            if strx[index] == ')':
                index += 1
            else:
                print('NO,输入不合法')
        else:
            print('NO,输入不合法')
    
    
    strx_ = input('输入表达式')
    #strx_ = 'i+i*i'
    a = time.clock()
    strx_ += '#'
    x = 1
    while x:
        index = 0
        strx = strx_
        strx += '#'
        ParseE()
        x -= 1
    
    b = time.clock()
    print(b-a)

[20190114194858378.png]: /images/20220326/e16f7107ac114bdd90f0cbdc6da00154.png
[omegaxyz.com]: http://omegaxyz.com