对文法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语言代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#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代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
''' 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) |
