LINUX.ORG.RU

YACC


0

1

Доброго времени суток, вот программа на яке

     /* Simplest Context free grammar (0^n1^n) */
 
     %{    #include <ctype.h>
     #include <stdio.h>
       #define YYSTYPE char         // Type of input
       int  yylex   (void);
       void yyerror (char const *);
     %}
 
  // Main symbols of grammar (synonyms: terminals, tokens, etc.)
     %token ONE   
     %token TWO
    %left UR
 
     %% /* Grammar rules and actions follow.  */
 
     input:    /* empty */   { printf("\n\tThis program expecting string as\n");}
             | input line
     ;
 
     line:     '\n'          { printf ("empty line was introduced\n");}
	     |error '\n' {yyerrok;}
		| exp '\n'      { printf ("\t n = %i\n", $1); }
     ;
     exp:   ONE TWO       { $$ = 1; }
	     | TWO ONE
             |ONE  exp  TWO    
	     |TWO  exp ONE   { $$ = $2 + 1;}
     ;
     %%
     int yylex (void)
     {
       int c;

       /* Skip white space  */
       while ((c = getchar ()) == ' ' || c == '\t')
         ;
       /* Process symbols  */
       if (c == '0') {
        
         return ONE;
       }
       else
         if (c == '1') {
         
           return TWO;
         }
         else
         /* Return end-of-input.  */
         if (c == EOF)
           return 0;
       /* Return a single char.  */
       return c;
     }
     void yyerror (char const *s)
     {
       fprintf (stderr, "stderror: %s\n", s);      
     }
     int
     main (void)
     {
       return yyparse ();
     }
он выдает ошибку shift reduce в правиле exp,как это можно исправить и почему появилась эта ошибка программа должна распознавать обратно-зеркальные двоичные наборы, где значения симметричных разрядов не совпадают спасибо

вроде shift-reduce это не ошибка, ошибка только reduce-reduce. ты уверен, что yacc выдает именно ошибку?

anonymous ()
Ответ на: комментарий от anonymous

да, но в любом случае программа работает не правильно

mikemike ()

почему появилась эта ошибка

При построении множества LR-пунктов в один прекрасный момент возникнет ситуация, когда в одном множестве (с номером k) окажутся следующие пункты ( я использую * вместо точки) :

  • exp -> ONE TWO *, ONE // приведет к записи в ячейку таблицы <k,ONE> reduce
  • exp -> * ONE TWO, ONE // приведет к записи в ячейку таблицы <k,ONE> shift

Не знаю как yacc, но bison в случае shift/reduce-конфликтов оставляет по умолчанию shift. Если это справедливо и в отношении yacc, то программа неправильно работает потому что сочетание лексем ONE и TWO на вершине стека никогда не свернется в exp.

nerh ()
Ответ на: комментарий от mikemike

а что означает *?

http://en.wikipedia.org/wiki/LR_parser#Items * в моем примере вместо точки была использована.

и можно ли это как-нибудь исправить?

У меня пока идей нет. Это вам в образовательных целях такое реализовать нужно?

nerh ()

Из википедии:

The set of deterministic context-free languages is a proper subset of the set of context-free languages that possess an unambiguous context free grammar. For example, the language of even-length palindromes on the alphabet of 0 and 1 has the simple, unambiguous grammar S → 0S0 | 1S1 | ε, but it cannot be parsed by a deterministic push down automaton.[3]

Язык в примере - это похоже почти то же самое, т.е. по-идее разобрать его с помощью yacc не выйдет.

abacaba ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.