LL(1) грамматики

[Camelion]

Возникла необходимость сделать лексический и синтаксический анализатор "простого" класса. Изучив возможные варианты построения, более простыми и надежными(по сравнению с LR) показались LL(1) грамматики. Сказано - сделано, сходу было построено выделение лексем(flex), разобран заголовок класса, дело дошло до тела, и столкнулся с неприятностью. Для того, чтобы обработать объявления переменных, и вовремя перейти к обработке следующей секции - нужно предугадать, когда будет объявлена последняя переменная. Каким образом можно это сделать?

Code:

Свернуть ↑
Описание лексем:

 
%{
#include "NASC.h"
%}
%%
class { return(CLASS); }
: { return (EXTENDS_SYMBOL); }
\(null\) { return(NULL_PARENT); }
\{ { return(BODY_BEGIN); }
\} { return(BODY_END); }
parameter: { return(PARAMETER_SECTION); }
handler: { return(HANDLER_SECTION); }
 
[A-Za-z_][A-Za-z_0-9]+ { return(ID); }
[0-9]+ { return(INT_VALUE); }
[0-9]+\.[0-9]+ { return(FLOAT_VALUE); }
 
[ \t]+ { /* do nothing */ }
. { return(yytext[0]); } 
 
Code: C

Анализатор

 
#include "NASC.h"
#include <stdio.h>
 
#define DEBUG
 
int c;
 
main () {
	c = yylex();
	start(); // Запуск прохода по файлу
	printf("Success parse\n");	
}
 
// Проход по файлу
start() {
	#ifdef DEBUG 
	printf("start() %d\n", c);	
	#endif	
 
	switch(c) {
		case CLASS: c = yylex(); _class();
			break;
		default:
			compilation_error(yyget_text());
			break;	
	}
}
 
// Ожидает тип класса
_class() {
	#ifdef DEBUG 
	printf("_class() %d\n", c);	
	#endif	
 
	switch(c) {
		case INT_VALUE: c = yylex(); class_type();
			break;
		default:
			compilation_error(yyget_text());
			break;	
	}
}
 
// Ожидает имя класса
class_type() {
	#ifdef DEBUG 
	printf("class_type() %d\n", c);	
	#endif	
 
	switch(c) {
		case ID: c = yylex(); class_name();
			break;
		default:
			compilation_error(yyget_text());
			break;	
	}
}
 
// Ожидает символ наследования
class_name() {
	#ifdef DEBUG 
	printf("class_name() %d\n", c);	
	#endif	
 
	switch(c) {
		case EXTENDS_SYMBOL: c = yylex(); class_parent();
			break;
		default:
			compilation_error(yyget_text());
			break;	
	}
}
 
// Ожидает имя класса, от которого выполняется наследование
class_parent() {
	#ifdef DEBUG 
	printf("class_parent() %d\n", c);	
	#endif	
 
	switch(c) {
		// Имя класса, либо (null), если предка нет
		case ID: 
		case NULL_PARENT: c = yylex(); class_body_start();
			break;
		default:
			compilation_error(yyget_text());
			break;	
	}
}
 
// Ожидает символ начала тела класса "{"
class_body_start() {
	#ifdef DEBUG 
	printf("class_body_start() %d\n", c);	
	#endif	
 
	switch(c) {
		case BODY_BEGIN: c = yylex(); class_body(); 
			break;
		default:
			compilation_error(yyget_text());
			break;	
	}
}
 
// Ожидает один из следующих вариантов parameter: или handler:
class_body() {
	#ifdef DEBUG 
	printf("class_body() %d\n", c);	
	#endif	
 
	switch(c) {
		case PARAMETER_SECTION: c = yylex(); parameters(); 
			break;
		case HANDLER_SECTION: c = yylex(); // TODO: HANDLER SECTION
			break;		
		default:
			compilation_error(yyget_text());
			break;	
	}
}
 
// Обрабатывает секцию parameters:
parameters() {
 
}
 
compilation_error(char* text) {
	printf("Error in reading token%s\n", text);
}
 
 
Code: C

Свернуть ↑Развернуть ↓

Входные данные:

Свернуть ↑

 
class 0 default_npc : (null)
{
parameter:
  int     DesirePqSize = 50;
  int     FavorListSize = 30;
  float   IdleDesire_DecayRatio = 0.000000;
  float   MoveAround_DecayRatio = 0.000000;
  float   DoNothing_DecayRatio = 0.000000;
  float   Attack_DecayRatio = 0.000000;
  float   Chase_DecayRatio = 0.000000;
  float   Flee_DecayRatio = 0.000000;
  float   GetItem_DecayRatio = 0.000000;
  float   Follow_DecayRatio = 0.000000;
  float   Decaying_DecayRatio = 0.000000;
  float   MoveToWayPoint_DecayRatio = 0.000000;
  float   UseSkill_DecayRatio = 0.000000;
  float   MoveTo_DecayRatio = 0.000000;
  float   EffectAction_DecayRatio = 0.000000;
  float   MoveToTarget_DecayRatio = 0.000000;
  float   IdleDesire_BoostValue = 0.000000;
  float   MoveAround_BoostValue = 0.000000;
  float   DoNothing_BoostValue = 0.000000;
  float   Attack_BoostValue = 0.000000;
  float   Chase_BoostValue = 0.000000;
  float   Flee_BoostValue = 0.000000;
  float   GetItem_BoostValue = 0.000000;
  float   Follow_BoostValue = 0.000000;
  float   Decaying_BoostValue = 0.000000;
  float   MoveToWayPoint_BoostValue = 0.000000;
  float   UseSkill_BoostValue = 0.000000;
  float   MoveTo_BoostValue = 0.000000;
  float   EffectAction_BoostValue = 0.000000;
  float   MoveToTarget_BoostValue = 0.000000;
  int     Dispel_Debuff = 0;
  int     Dispel_Debuff_Prob = 0;
 
handler:
  EventHandler NO_DESIRE()
  {
  }
 
  EventHandler TALK_SELECTED( talker )
  {
    myself::ShowPage( talker, "noquest.htm" );
  }
 
  EventHandler DEBUG_AI( creature, reply )
  {
    if( reply == 101 )
    {
      myself::Whisper( creature,
                       "** Direction : " + myself::GetDirectionToTarget( creature ) * 182 + "  " );
    }
  }
 
  EventHandler ABNORMAL_STATUS_CHANGED( speller, skill_id, skill_level, skill_name_id, s0, i0 )
  {
    if( Dispel_Debuff == 1 )
    {
      if( skill_level > 0 )
      {
        if( myself::Skill_GetAbnormalType( @s_shield_stun11 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
            gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_shield_stun11 ) ) > 0 )
        {
          myself::Dispel( myself.sm,
                          myself::Skill_GetAbnormalType( @s_shield_stun11 ) );
        }
        else if( myself::Skill_GetAbnormalType( @s_trance1 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_trance1 ) ) > 0 )
        {
          myself::Dispel( myself.sm,
                          myself::Skill_GetAbnormalType( @s_trance1 ) );
        }
        else if( myself::Skill_GetAbnormalType( @s_lightening_strike1 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_lightening_strike1 ) ) > 0 )
        {
          myself::Dispel( myself.sm,
                          myself::Skill_GetAbnormalType( @s_lightening_strike1 ) );
        }
        else if( myself::Skill_GetAbnormalType( @s_dance_of_medusa1 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_dance_of_medusa1 ) ) > 0 )
        {
          myself::Dispel( myself.sm,
                          myself::Skill_GetAbnormalType( @s_dance_of_medusa1 ) );
        }
        else if( myself::Skill_GetAbnormalType( @s_curse_fear1 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_curse_fear1 ) ) > 0 )
        {
          myself::Dispel( myself.sm,
                          myself::Skill_GetAbnormalType( @s_curse_fear1 ) );
        }
        else if( myself::Skill_GetAbnormalType( @s_dryad_root11 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_dryad_root11 ) ) > 0 )
        {
          myself::Dispel( myself.sm,
                          myself::Skill_GetAbnormalType( @s_dryad_root11 ) );
        }
        else if( myself::Skill_GetAbnormalType( @s_shackle1 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_shackle1 ) ) > 0 )
        {
          myself::Dispel( myself.sm,
                          myself::Skill_GetAbnormalType( @s_shackle1 ) );
        }
      }
    }
    else if( Dispel_Debuff == 2 )
    {
      if( skill_level > 0 )
      {
        if( myself::Skill_GetAbnormalType( @s_shield_stun11 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
            gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_shield_stun11 ) ) > 0 )
        {
          if( gg::Rand( 10000 ) < Dispel_Debuff_Prob )
          {
            myself::Dispel( myself.sm,
                            myself::Skill_GetAbnormalType( @s_shield_stun11 ) );
          }
        }
        else if( myself::Skill_GetAbnormalType( @s_trance1 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_trance1 ) ) > 0 )
        {
          if( gg::Rand( 10000 ) < Dispel_Debuff_Prob )
          {
            myself::Dispel( myself.sm,
                            myself::Skill_GetAbnormalType( @s_trance1 ) );
          }
        }
        else if( myself::Skill_GetAbnormalType( @s_lightening_strike1 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_lightening_strike1 ) ) > 0 )
        {
          if( gg::Rand( 10000 ) < Dispel_Debuff_Prob )
          {
            myself::Dispel( myself.sm,
                            myself::Skill_GetAbnormalType( @s_lightening_strike1 ) );
          }
        }
        else if( myself::Skill_GetAbnormalType( @s_dance_of_medusa1 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_dance_of_medusa1 ) ) > 0 )
        {
          if( gg::Rand( 10000 ) < Dispel_Debuff_Prob )
          {
            myself::Dispel( myself.sm,
                            myself::Skill_GetAbnormalType( @s_dance_of_medusa1 ) );
          }
        }
        else if( myself::Skill_GetAbnormalType( @s_curse_fear1 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_curse_fear1 ) ) > 0 )
        {
          if( gg::Rand( 10000 ) < Dispel_Debuff_Prob )
          {
            myself::Dispel( myself.sm,
                            myself::Skill_GetAbnormalType( @s_curse_fear1 ) );
          }
        }
        else if( myself::Skill_GetAbnormalType( @s_dryad_root11 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_dryad_root11 ) ) > 0 )
        {
          if( gg::Rand( 10000 ) < Dispel_Debuff_Prob )
          {
            myself::Dispel( myself.sm,
                            myself::Skill_GetAbnormalType( @s_dryad_root11 ) );
          }
        }
        else if( myself::Skill_GetAbnormalType( @s_shackle1 ) == myself::Skill_GetAbnormalType( skill_name_id ) &&
                 gg::GetAbnormalLevel( myself.sm, myself::Skill_GetAbnormalType( @s_shackle1 ) ) > 0 )
        {
          if( gg::Rand( 10000 ) < Dispel_Debuff_Prob )
          {
            myself::Dispel( myself.sm,
                            myself::Skill_GetAbnormalType( @s_shackle1 ) );
          }
        }
      }
    }
  }
}
 
Code: C++

Свернуть ↑Развернуть ↓

[Zubastic]

Может я неправильно понял, но при объявлении используются ключевые слова для типа данных? Может искать в строке название и есть оно не найдено то закрывать объявляющую секцию?

[Camelion]

Сообщение от Zubastic

Может я неправильно понял, но при объявлении используются ключевые слова для типа данных? Может искать в строке название и есть оно не найдено то закрывать объявляющую секцию?

В таком случае это будет неверно для переменных, объявленных внутри функций, (будет искаться следующая секция, что ошибочно, так как уже идет обработка этой секции)

[учусь]

может что-то такое

1:

Свернуть ↑

Свернуть ↑Развернуть ↓

если на входе терминал(int,float, имя_класса и тд) -> делаем цикл (больше,маленькие буквы, цифры) пока не знак "=" -> цикл по цифрам до ";" -> проверяем, есть ли еще терминалы -> начали новый анализ -> иначе нету переменных.

зы. "Для того, чтобы КС-грамматика была LL(1)-грамматикой, необходимо, чтобы множества выбора для правил с одинаковыми левыми частями не пересекались, т.е. не имели общих терминальных символов." - будешь ли делать такую проверку?)

[Camelion]

Сообщение от учусь

может что-то такое

1:

Свернуть ↑

Свернуть ↑Развернуть ↓

если на входе терминал(int,float, имя_класса и тд) -> делаем цикл (больше,маленькие буквы, цифры) пока не знак "=" -> цикл по цифрам до ";" -> проверяем, есть ли еще терминалы -> начали новый анализ -> иначе нету переменных.

зы. "Для того, чтобы КС-грамматика была LL(1)-грамматикой, необходимо, чтобы множества выбора для правил с одинаковыми левыми частями не пересекались, т.е. не имели общих терминальных символов." - будешь ли делать такую проверку?)

То есть после каждого ';' в секции parameters проверять следующий терминал (float, int)/handlers/end_of_class, и в зависимости от этого терминала переходить к дальнейшему разбору?

[Array]

Нашёл кусок грамматики про объявление переменных:

<def>			->	int var <def_end>
<def_end>		->	; | , var <def_end> | <init> ;
<init>			->	= <com_expr> ;
<com_expr>		->	<expr> <oper> <com_expr> | ;
<oper>			->	) | + | - | / | * | < | > | <= | >= | == | != | && | ||
<expr>			->	var | const | ( <expr>

Вот так транслятор выглядел

Давай таблицу разбора делай и вперёд.

[учусь]

мне тоже кажется, что лучше сначала на бумажке написать полную грамматику. потом применить алгоритмы(устранение недостижимых, рекурсивных и тд) и получить LL(1), а то бесконечные циклы вылезут. но это мое мнение.

нашел самописные реализации алгоритмов:

1:

Свернуть ↑

Свернуть ↑Развернуть ↓

[Camelion]

Array, учусь, А может LALR(1) лучше подойдет для такого рода разбора?

Добавлено через 3 часа 53 минуты
Всем спасибо, особоенно Array и учусь. Успешно построил грамматику с использованием LALR(1).

[Yorie]

Думаю, что Вашу проблему можно было бы решить LL(1)-парсером с использованием Look Ahead алгоритма. Собственно, yylex поддерживает такую возможность.
Вообще, восходящие алгоритмы для парсеров более приоритетны, т.к. класс разбираемых грамматик нисходящих алгоритмов является подклассом для множества разбираемых грамматик восходящих алгоритмов.

[Ashe]

Сообщение от Yorie

Думаю, что Вашу проблему можно было бы решить LL(1)-парсером с использованием Look Ahead алгоритма.

Сообщение от Camelion

Всем спасибо, особоенно Array и учусь. Успешно построил грамматику с использованием LALR(1).

Собственно так и было сделано.

P.S. Некропост наказывается по закону.