Сопоставление строки с образцом — 2 (Prolog)

  • В этой теме 0 ответов, 1 участник, последнее обновление 2 месяца назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6793
      @admin
      StudLance.ru

      Альтернативный подход к решению этой задачи рассмотрен в соседней теме.

      Постановка задачи

      Необходимо разработать программу, осуществляющую сопоставление произвольно последовательности символов с заданным шаблоном (образцом). Для задания шаблона используются следующие специальные символы:

      • «символ» — алфавитно-цифровой символ;
      • «+» — непустая последовательность символов;
      • «?» — один любой символ;
      • «*» — любая последовательность символов.

      Шаблон: (+, H, *, M, ?)

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

      Проектирование программы

      Проектирование системы — это процесс ее декомпозиции, то есть разделения на маленькие и простые части.

      Наиболее сложной частью программы, очевидно, является функция разбора строки в соответствии с выражением. Эта функция, в соответствии с заданием должна иметь различное поведение для различных типов шаблона (*, +, ?, другой символ), поэтому, в соответствии с принципом Единственной обязанности (SRP) целесообразно разделить эту функцию на несколько.

      Другой нетривиальной частью программы является вывод на экран результатов — функция должна вести себя по разному в случаях если исходную строку удалось сопоставить хоть с одним шаблоном и если такое сопоставление не возможно. Причем, в первом случае — функция должна выполнить все возможные сопоставления и вывести на экран результаты. Поэтому, функцию вывода результатов тоже имеет смысл разделить на две.

      Схема логической программы

      Пусть, пользователь вызывает фукнцию run, на вход которой передается входная строка. Эта функция проверяет возможность сопоставления (вызывает match) и, если оно возможно, выводит на экран все возможные варианты (с помощью print_all_matches). Выглядеть функция run может так:

        run(String):-
          match(String, ["+", "H", "*", "M", "?"], _Strings), !,
          print_all_matches(String);
          write(String), write(" -> "), write("not matched with \"+H*M?\""), nl.

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

      Функция вывода на экран всех вариантов сопоставления должна вызывать функцию match для получения этих вариантов по очереди, если же варианты кончились — завершать свою работу. Каждый полученный вариант выводится на экран, для получения следующего варианта выполняется встроенный предикат fail, который завершает работу «неудачей», а значит — приводит к попытке Prolog-интерпретатора получить другие варианты.

        print_all_matches(String):-
          match(String, ["+", "H", "*", "M", "?"], Strings), 
          write(String),
          write(" ----> "), write(Strings), nl, fail.
        print_all_matches(_String).

      Функция match должна по-очереди перебирать параметры шаблона и с каждым из них выполнять сопоставление исходной строки. В качестве результата, эта функция возвращает список, состоящий из подстрок исходной строки. каждая из которых соответствует своему шаблону. Для сопоставления с конкретными символами шаблона, эта функция обращается к вспомогательным функциям:

      • «символ» — match_char;
      • «+» — match_not_empty_string;
      • «?» — match_any_symbol;
      • «*» — match_any_string.

      Сопоставление считается успешным, если одновременно закончились параметры шаблона и входная строка оказалась пуста:

        match(Source, Patterns, Strings):-
          Source = "", Patterns = [], Strings = [].
        match(Source, ["+"|TailPatterns], [MatchedString|TailStrings]):-
          !, match_not_empty_string(Source, MatchedString, SourceTail),
          match(SourceTail, TailPatterns, TailStrings).
        match(Source, ["*"|TailPatterns], [MatchedString|TailStrings]):-
          !, match_any_string(Source, MatchedString, SourceTail),
          match(SourceTail, TailPatterns, TailStrings).
        match(Source, ["?"|TailPatterns], [MatchedString|TailStrings]):-
          !, match_any_symbol(Source, MatchedString, SourceTail),
          match(SourceTail, TailPatterns, TailStrings).
        match(Source, [HeadPattern|TailPatterns], [MatchedString|TailStrings]):-
          frontchar(HeadPattern, Char, ""), % HeadPattern = Char + ""
          match_char(Source, Char, MatchedString, SourceTail),
          match(SourceTail, TailPatterns, TailStrings).

      Каждая из вспомогатльных функций принимает на вход исходную строку, а match_char также принимает символ. Эти функции возвращают:
      — сопоставленную подстроку — левую часть;
      — остальную часть строки — правую часть.

      Функция match_char реализуется посредством вызова стандартной функции frontchar, отделяющей символ от строки. Для формирования «левой части» выполняется второй вызов frontchar, формирующий новую строку из символа и пустой строки. Функция match_any_symbol без труда реализуется через match_char:

      match_char(Source, Char, Left, Right):-
          frontchar(Source, Char, Right), % Source = Char + Right
          frontchar(Left, Char, ""). % Left = Char + ""
      
      match_any_symbol(Source, Left, Right):-
          match_char(Source, _, Left, Right).

      Функция match_any_string с помощью frontchar по-очереди отделяет от строки символы (который затем, с помощью того же frontchar, прикрепляются к «левой части»):

      match_any_string(Source, "", Source).
      match_any_string(Source, Left, Right):-
          frontchar(Source, Head, Tail), % String =  Head + Tail
          match_any_string(Tail, LeftPart, Right),
          frontchar(Left, Head, LeftPart). % Left = Head  + LeftPart

      Первое правило (в первой строке) этой функции возвращает пустую левую часть, а правая часть равна исходной строке.

      Второе правило отделяет первый символ строки, остальные — обрабатывает рекурсивно, к полученному результату прикрепляет первый символ.
      Во врезке показан процесс работы функции для строки "asd". Возвращаемые результаты выделены жирным шрифтом и пронумерованы, уровень вложенности рекурсивных вызовов показан отступами.

      Работа функции match_any_string полностью эквивалентна функции substr, описанной тут.

      Тестирование программы

      После запуска программы и вывода в консоль приглашения ко вводу, программа ожидает, что пользователь введет в консоль строку и нажмет клавишу «Enter». Примеры входных данных, на которых производилось тестирование и полученные результаты приведены в таблице 1.

      Исходное выражение

      Полученное

      сообщение

      Пояснение

      1

      Hello worMd

      not match

      Перед «H» нет символов

      2

      …Hello worMd

      [«…»,»H»,»ello wor»,»M»,»d»]

      3

      …Hello Helen. My name is Ma

      [«…»,»H»,»ello Helen. My name is «,»M»,»a»]

      Первый вариант сопоставления

      [«…»,»H»,»ello Helen. My name is «,»M»,»a»]

      Второй вариант сопоставления

      Все приведенные в таблице варианты протестированы одним запросом (целью), в конце которой строка для сопоставления запрашивается с клавиатуры (в соответствии с заданием):

      goal 
        run("Hello worMd"),
        run("...Hello worMd"),
        run("...Hello Helen. My name is Ma"),
        write("Enter string: "),
        readln(String),
        run(String).

      Результат ее выполнения приведен на рисунке:

      Исходный код программы целиком:

      domains
        strings = string*
      predicates
        nondeterm match(string, strings, strings)
        
        nondeterm match_not_empty_string(string, string, string)
        nondeterm match_any_string(string, string, string)
        nondeterm match_any_symbol(string, string, string)
        nondeterm match_char(string, char, string, string)
        
        nondeterm print_all_matches(string)
        
        nondeterm run(string)
      clauses  
        match_any_string(Source, "", Source).
        match_any_string(Source, Left, Right):-
          frontchar(Source, Head, Tail), % String =  Head + Tail
          match_any_string(Tail, LeftPart, Right),
          frontchar(Left, Head, LeftPart). % Left = Head  + LeftPart
          
        match_not_empty_string(Source, Left, Right):-
          match_any_string(Source, Left, Right), NOT(Left = "").
          
        match_char(Source, Char, Left, Right):-
          frontchar(Source, Char, Right), % Source = Char + Right
          frontchar(Left, Char, ""). % Left = Char + ""
          
        match_any_symbol(Source, Left, Right):-
          match_char(Source, _, Left, Right).
          
        match(Source, Patterns, Strings):-
          Source = "", Patterns = [], Strings = [].
        match(Source, ["+"|TailPatterns], [MatchedString|TailStrings]):-
          !, match_not_empty_string(Source, MatchedString, SourceTail),
          match(SourceTail, TailPatterns, TailStrings).
        match(Source, ["*"|TailPatterns], [MatchedString|TailStrings]):-
          !, match_any_string(Source, MatchedString, SourceTail),
          match(SourceTail, TailPatterns, TailStrings).
        match(Source, ["?"|TailPatterns], [MatchedString|TailStrings]):-
          !, match_any_symbol(Source, MatchedString, SourceTail),
          match(SourceTail, TailPatterns, TailStrings).
        match(Source, [HeadPattern|TailPatterns], [MatchedString|TailStrings]):-
          frontchar(HeadPattern, Char, ""), % HeadPattern = Char + ""
          match_char(Source, Char, MatchedString, SourceTail),
          match(SourceTail, TailPatterns, TailStrings).
          
        print_all_matches(String):-
          match(String, ["+", "H", "*", "M", "?"], Strings), 
          write(String),
          write(" ----> "), write(Strings), nl, fail.
        print_all_matches(_String).
          
        run(String):-
          match(String, ["+", "H", "*", "M", "?"], _Strings), !, print_all_matches(String);
          write(String), write(" -> "), write("not matched with \"+H*M?\""), nl.
      goal 
        run("Hello worMd"),
        run("...Hello worMd"),
        run("...Hello Helen. My name is Ma"),
        write("Enter string: "),
        readln(String),
        run(String).
      

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×