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

[Camelion]

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

Открыть спойлер

Code
Описание лексем:
[src=C]
%{
#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]); }
[/src]
Анализатор
[src=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© {
case CLASS: c = yylex(); _class();
break;
default:
compilation_error(yyget_text());
break;
}
}

// Ожидает тип класса
_class() {
#ifdef DEBUG
printf("_class() %d\n", c);
#endif

switch© {
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© {
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© {
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© {
// Имя класса, либо (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© {
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© {
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);
}

[/src]

Открыть спойлер

Входные данные
[src=CPP]
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:ispel( 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:ispel( 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:ispel( 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:ispel( 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:ispel( 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:ispel( 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:ispel( 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:ispel( 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:ispel( 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:ispel( 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:ispel( 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:ispel( 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:ispel( 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:ispel( myself.sm,
myself::Skill_GetAbnormalType( @s_shackle1 ) );
}
}
}
}
}
}
[/src]

[Zubastic]

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

[Camelion]

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

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

[учусь]

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

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]

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

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

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

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