VPF::[Delphi] Левая факторизация грамматики

ARAV

Дата 31.10.2006, 05:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 5
Регистрация: 31.10.2006

Репутация: нет
Всего: нет

Всем добрый день!
Очень надеюсь на вашу помощь в решении моей задачи.
Суть в следующем:
Пусть имеется некоторый набор правил, например:

S->abSa
S->aaAb
S->b
A->baAb
A->b

Необходимо произвести над ними преобразование, называемое левой факторизацией:
Если у нас совпадает символ до ‘->’ (как символ S в примере), то мы рассматриваем строки, следующие после символа ‘->’ (т.е. в данном случае это строки ‘abSa’, ‘aaAb’, ‘b’). Если в этих строках есть совпадающий начальный символ (например, символ ‘a’ в первых двух строках), то во все такие строки заменяются на следующее правило: S->aF и добавляются новые правила: F-> bSa и F->aAb (то есть те символы, которые шли после совпавшего).
У меня уже написана часть задачи, в которой все эти правила разбиты по следующему принципу: каждый символ до знака '->' становится новым 'правилом' которому будут сопоставляться строки, находящиеся после символа '->'. Если символ до знака '->' повторяется (как символ S в примере), то новое правило не создается, а просто дополняется еще одной строчкой из символов после стрелки.

В итоге правила должны быть преобразованы к следующему виду:

S->aF
S->b
A->bG
F->bSa
F->aAb
G->aAb
G->E (здесь E обозначает пустой символ).

У меня с использованием записей получилось только разделить все эти правила, чтобы их удобнее было сравнивать:
left: S
alternative: [abc] [aab] [ba]
left: A
alternative: [bcd]

Вот основная часть кода программы:

Код

type

  TRule=record

    left: Char;

    alternatives: array of string;

  end;



  TRules=array of TRule;



procedure TForm1.FormCreate(Sender: TObject);

var Rule : TRules;

begin

  Finalize(Rule);

end;



procedure TForm1.Button1Click(Sender: TObject);

var

  s, s1, s2 : string;

  Rule : TRules;

  i, j, k, n, n1: integer;

begin

  for i := 0 to Memo3.Lines.Count - 1 do

  begin

    s1 := Memo3.Lines[i];

    j := 0;

    while (j < Length(Rule)) and (Rule[j].left <> s1[1]) do

      Inc(j);



    if j = Length(Rule) then

    begin

      SetLength(Rule, Length(Rule) + 1);

      Rule[j].left := s1[1];

      SetLength(Rule[j].alternatives, 1);

      Rule[j].alternatives[0] := copy(s1, 4, length(s1));

    end

    else

    begin

      n := Length(Rule[j].alternatives);

      SetLength(Rule[j].alternatives, n + 1);

      Rule[j].alternatives[n] := copy(s1, 4, length(s1));

    end;

  end;



  Memo5.Lines.Clear;

  Memo6.Lines.Clear;

  Self.Memo6.Lines.Add('');

  for i := 0 to Length(Rule) - 1 do

  begin

    s := ' ';

    Memo6.Lines.Add(Rule[i].left);

    for j := 0 to Length(Rule[i].alternatives) - 1 do

      s := s + '  [' + Rule[i].alternatives[j] + ']';

    Memo6.Lines.Add(s);

    for j := 0  to Length(Rule[i].alternatives) - 1 do

    Memo5.Lines.Add(Rule[i].alternatives[j]);

  end;

Буду очень благодарен за любую помощь…
Модератор: у нас есть возможность выбора типа подсветки. Например, я сейчас установил подсветку delphi (кнопка имеет выпадающий список подсветок)

Это сообщение отредактировал(а) alexeis1 - 31.10.2006, 10:51

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »