Implemente um analisador sintáctico para reconhecimento duma expressão lógica, utilizando um parser descendente predictivo. A gramática é a seguinte:
E → E or E | E xor E | E and E | not E | ( E ) | ID | INT | REAL
onde ID é um identificador (letra seguida de letra ou número), INT um número inteiro e REAL um número real.
Para se implementar o parser descendente predictivo é necessário eliminar a ambiguidade e a recursividade esquerda. As únicas 3 alternativas da produção E com recursividade esquerda são as 3 primeiras, pelo que têm de ser transformadas de modo a utilizar recursividade direita.
Para isso começa-se por dividir esta produção em duas uma com todos os starters, isto é tokens que podem aparecer no início da produção E, e que são not E,(E),ID,INT e REAL (F) e outra com as restantes alternativas mas já sem a recursividade esquerda (E').
No gramática seguinte a alternativa not E, foi transformada em not F, pois o operador lógico not, tem precedência sobre tdos os outros operadores lógicos.
E → F E'
E' → or F E'
E' → xor F E'
E' → and F E'
E' → ε
F → ( E )
F → not F
F → ID
F → INT
F → REAL
Um parser descendente predictivo é obtido, transformando cada uma das produções num procedimento, que vai consumindo os tokens e chamando as produções que aparecem do lado direito.
Este parser faz recuperação de erros ignorando-o e tentando encaixar o token que produziu o erro nas produções seguintes.
%{
enum {OR,XOR,AND,NOT,ABRIR_P,FECHAR_P,INT,REAL,ID,FIM,ERRO};
int coluna=0;
%}
/* definição de dígito */
digito [0-9]
letra [a-zA-Z]
%%
or coluna+=strlen(yytext);return OR;
xor coluna+=strlen(yytext);return XOR;
and coluna+=strlen(yytext);return AND;
not coluna+=strlen(yytext);return NOT;
"(" coluna+=1;return ABRIR_P;
")" coluna+=1;return FECHAR_P;
{digito}+ coluna+=strlen(yytext);return INT;
({digito}*,)?{digito}+([Ee][-+]?{digito}+)? coluna+=strlen(yytext);return REAL;
{letra}({letra}|{digito})* coluna+=strlen(yytext);return ID;
[ \t] coluna+=1;
<<EOF>> |
\n return FIM;
. coluna+=1;printf ("Erro léxico:%s\n",yytext);
%%
void e();
void e2();
void f();
void erro(char *);
int token;
void erro(char *s) {
printf("Erro sintactico: %s na coluna %d\n",s,coluna-strlen(yytext));
}
/* E -> F E' */
void e() {
f();
e2();
}
/* E' -> or F E' | xor F E' | and F E' | */
void e2() {
if (token==OR || token==OR || token==AND) {
token=yylex();
f();
e2();
}
/* como esta produção tem uma alternativa vazia, não vamos chamar a função
erro quando o token não é OR, XOR ou AND */
}
/* F -> ( E ) | not F | ID | INT | REAL */
void f() {
switch (token) {
case ID :
case INT :
case REAL : token=yylex();
break;
case ABRIR_P : token=yylex();
e();
if (token==FECHAR_P)
token=yylex();
else
erro("falta ')'");
break;
case NOT : token=yylex();
f();
break;
/* como não existe alternativa vazia, vamos apresentar
um erro se o token não for um doa anteriores */
default: erro("falta operando");
}
}
main(){
token=yylex();
do {
e();
if(token==FIM)
printf("análise concluida\n");
else
printf("erro sintactico:erro desconhecido (falta operador) na coluna %d\n",coluna-strlen(yytext));
}while(token!=FIM);
}
/* se definir esta função não necessita de compilar com o parâmetro -lfl */
int yywrap()
{
return(1);
}
Ultima alteração: sexta-feira, 24 de Novembro de 2000 às 21:29