YACC - Yet Another Compiler Compiler

[ Содержание ] [ Предыдущая ] [ Следующая ]

Приложение C: Продвинутый пример

В этом приложении дается пример грамматики с использованием некоторых продвинутых возможностей, обсуждавшихся в главе 10. Пример с настольным калькулятором из приложения A изменен так, чтобы получился настольный калькулятор, который обеспечивает арифметику с интервалами плавающих точек. Калькулятор понимает константы с плавающей точкой, арифметические операции +, -, *, /, унарный -, и = (присваивание) и имеет 26 переменных с плавающей точкой, от "a" до "z". Более того, он также понимает интервалы, написанные в виде ( x , y ) где x меньше или равен y. Также могут использоваться 26 интервалов-переменных - от "A" до "Z", которые также могут использоваться. Использование подобно подобно тому, что было в приложении A; присваивания не возвращают значений, и ничего не печатают, тогда как выражения печатают значения (с плавающей точкой или интервала).

В этом примере исследуются некоторые интересные возможности Yacc-а и C. Интервалы представляются в виде структуры, состоящей из значений левого и правого концов, хранимых в виде double. Этим структурам при помощи typedef дается имя типа, INTERVAL. Стек значений Yacc-а также может содержать числа с плавающей точкой и целые (используемые как индекс в массивах, содержащих значения переменных). Заметьте, что общая стратегия сильно зависит от возможности присваивать структуры и union-ы в C. В действительности многие действия вызывают функции, также возвращающие структуры.

Также стоит заметить использование YYERROR для обработки условий ошибки: деление на интервал, содержащий 0 и интервал, записанный в неправильном порядке. Hа самом деле, механизм восстановления после ошибок в Yacc-е используется для отбрасывания остатка строки-нарушительницы.

В дополнение к смешиванию типов на стеке значений, эта грамматика также демонстрирует интересное использование синтаксиса для отслеживания типа (т.е. скалярного или интервального) промежуточных выражений. Заметьте, что скаляр может быть автоматически преобразован в интервал, если контекст требует интервального значения. Это вызывает большое количество конфликтов при обработке грамматики Yaccом: 18 сдвиг/понижение и 26 понижение/понижение. Эта проблема может быть увидена при взгляде на две водные строки

2.5 + ( 3.5 - 4. )

2.5 + ( 3.5 , 4. )

Заметьте, что 2.5 используется в выражении интервального типа во втором примере, но этот факт неизвестен до тех пор, пока не прочитана ","; к этому времени 2.5 закончена и парсер не может вернуться и изменить свое мнение. Говоря более обще, может быть необходимо посмотреть вперед на произвольное количество токенов, чтобы решить, преобразовывать ли скаляр в интервал. Эта проблема обходится с использованием двух правил для каждого бинарного оператора, работающего с интервалами: одно, когда левый операнд - скаляр и одно - когда левый операнд - интервал. Во втором случае правый операнд должен быть интервалом, так что преобразование будет применено автоматически. Hесмотря на это уклонение, все еще остается много случаев, когда преобразование может или не может быть применено, что ведет к вышеуказанным конфликтам. Они разрешаются перечислением правил, требующих скаляров, первыми в файле спецификаций; таким образом, конфликты разрешаются в сторону сохранения скалярно-типизированных значений скалярно-типизированными до тех пор, пока они вынужденно не преобразовываются в интервалы.

Этот способ обработки производных типов очень поучителен, но не очень общий. Если бы было много типов выражений, а не просто два типа, количество требуемых правил возросло бы драматически, а количество конфликтов - еще более драматически. Таким образом, несмотря на поучительности примера, в обычной среде программирования лучше будет хранить информацию о типе как часть значения, а не как часть грамматики.

Hаконец, немного о лексическом анализе. Единственная необычная вешь - обработка констант с плавающей точкой. Подпрограмма библиотеки C atof используется для произведения преобразования из строки символов в значения с двойной точностью. Если лексический анализатор определяет ошибку, он реагирует на нее, возвращая токен, запрещенный в грамматике, вызывая синтаксическую ошибку в парсере и отсюда восстановления после ошибки.


%{
# include 
# include 
typedef struct interval 
{ 
	double lo, hi; 
} INTERVAL;
INTERVAL vmul(), vdiv();
double atof();
double dreg[ 26 ];
INTERVAL vreg[ 26 ];
%}
%start lines
%union 
{ 
	int ival; double dval; 
	INTERVAL vval; 
}
/* индексы в массивах dreg, vreg */
%token  DREG VREG  
/* константа с плавающей точкой */
%token  CONST 
/* выражение */
%type  dexp 
/* интервальное выражение */
%type  vexp 
/* информация о приоритетах операторов */
%left '+' '-'
%left '*' '/'
/* приоритет унарного минуса */
%left UMINUS 
%%
lines
  : /* empty */
  | lines line
  ;
line 
  : dexp '\n'
    { printf( "%15.8f\n", $1 ); }
  | vexp '\n'
    { printf("(%15.8f , %15.8f )\n", 
      $1.lo, $1.hi ); }
  | DREG '=' dexp '\n'
    { dreg[$1] = $3; }
  | VREG '=' vexp '\n'
    { vreg[$1] = $3; }
  | error '\n'
    { yyerrok; }
  ;
dexp 
  :    CONST
  |    DREG
    { $$ = dreg[$1]; }
  |    dexp '+' dexp
    { $$ = $1 + $3; }
  |    dexp '-' dexp
    { $$ = $1 - $3; }
  |    dexp '*' dexp
    { $$ = $1 * $3; }
  |    dexp '/' dexp
    { $$ = $1 / $3; }
  |    '-' dexp~~  %prec UMINUS
    { $$ = - $2; }
  |    '(' dexp ')'
    { $$ = $2; }
  ;
vexp 
  : dexp
    { $$.hi = $$.lo = $1; }
  | '(' dexp ',' dexp ')'
    { $$.lo = $2; $$.hi = $4;
      if( $$.lo > $$.hi ){
        printf(
          "interval out of order\n");
        YYERROR;
      }
    }
  | VREG
    { $$ = vreg[$1]; }
  | vexp '+' vexp
    { $$.hi = $1.hi + $3.hi; 
      $$.lo = $1.lo + $3.lo; }
  | dexp '+' vexp
    { $$.hi = $1 + $3.hi; 
      $$.lo = $1 + $3.lo; }
  | vexp '-' vexp
    { $$.hi = $1.hi - $3.lo; 
      $$.lo = $1.lo - $3.hi; }
  | dexp '-' vexp
    { $$.hi = $1 - $3.lo; 
      $$.lo = $1 - $3.hi; }
  | vexp '*' vexp
    { $$ = vmul( $1.lo, $1.hi, $3 ); }
  | dexp '*' vexp
    { $$ = vmul( $1, $1, $3 ); }
  | vexp '/' vexp
    { if( dcheck( $3 ) ) YYERROR;
      $$ = vdiv( $1.lo, $1.hi, $3 );
    }
  | dexp '/' vexp
    { if( dcheck( $3 ) ) YYERROR;
      $$ = vdiv( $1, $1, $3 );
    }
  | '-' vexp    %prec UMINUS
    { $$.hi = -$2.lo; 
      $$.lo = -$2.hi; }
  | '(' vexp ')'
    { $$ = $2; }
  ;
%%
/* размер буфера для чисел 
  с плавающей точкой */
# define BSZ 50 
/* лексический анализ */
yylex()
{
  register c;
  while( (c=getchar()) == ' ' ) 
	{ /* skip over blanks */ }
  if( isupper( c ) ) {
    yylval.ival = c - 'A'; return( VREG );
  }
  if( islower( c ) ) {
    yylval.ival = c - 'a'; return( DREG );
  }
  if( isdigit( c ) || c=='.' ) {
    /* пожирание цифр, точек, экспонент */
    char buf[BSZ+1], *cp = buf;
    int dot = 0, exp = 0;
    for( ; (cp-buf)= BSZ )
      printf( 
      "константа слишком длинная: обрезана\n");
    else ungetc( c, stdin ); 
    /* вернуть обратно последний 
      прочитанный символ */
    yylval.dval = atof( buf );
    return( CONST );
  }
  return( c );
}
INTERVAL hilo( a, b, c, d )
double a, b, c, d;
{ 
/* возвращает наименьший интервал, 
   содержащий a, b, c и d
   используется процедурами *, / */
  INTERVAL v;
  if( a>b ) { v.hi = a; v.lo = b; }
  else { v.hi = b; v.lo = a; }
  if( c>d ) {
    if( c>v.hi ) v.hi = c;
    if( dv.hi ) v.hi = d;
    if( c= 0. && v.lo <= 0. ) {
    printf( 
    "интервал -- знаменатель содержит 0.\n" );
    return( 1 );
  }
  return( 0 );
}
INTERVAL vdiv( a, b, v )
double a, b;
INTERVAL v;
{
  return( 
    hilo( a/v.hi, a/v.lo, 
          b/v.hi, b/v.lo ) );
}

[ Содержание ] [ Предыдущая ] [ Следующая ]

c 1998-2000 SoloTony (Antonio Solo)

solotony@mail.ru