Пусть  {‘a’, ‘b’, …, ‘z’}* = T* - Лекция Модель вычислений фон Неймана и традиционные языки Лекция Модель вычислений... структурированная строка структурированная строка символы Учебный сайт
Учебные материалы


Пусть  {‘a’, ‘b’, …, ‘z’}* = T* - Лекция Модель вычислений фон Неймана и традиционные языки Лекция Модель вычислений...



Пусть  {‘a’, ‘b’, …, ‘z’}* = T*

  • Пусть  {‘a’, ‘b’, …, ‘z’}* = T*

  • = → 0 – любое одиночное вхождение ‘a’ в 

  • = → 0 любая подстрока, состоящая из ‘a’ длины 0, 1, …

  • = → 0 – любая подстрока, состоящая из ‘a’ длины 1, 2, …

  • = → 0 – любая подстрока, состоящая из ‘a’ длины N N – переменная. Если она означенная, то ее значение определяет длину, если нет, то она означивается как длина 0.

  • = → 0 – любая подстрока вида aN bN cN Na, Nb, Nc, X и Y – переменные

  • = → 0 – та подстрока вида aN bN cN для которой N наибольшее

  • Соглашения о стратегии сопоставления: первое вхождение, все вхождения, максимальное вхождение и др.

  • Детерминатив – элемент образца, который сопоставляется (обычно наиболее простым способом) в первую очередь с целью сузить число рассматриваемых вариантов



Приспособить к практическим нуждам теоретический Алгорифм Маркова:

  • Приспособить к практическим нуждам теоретический Алгорифм Маркова:

    • { i  i }, где i, iT*, T — алфавит символов
  • Циклически повторяются в строгом порядке

    • поиск i (всегда с самого начала строки),
    • замена его на i в перерабатываемой строке.
  • Завершение цикла предусматривается в двух случаях:

    • Когда ничто не может быть найдено, и
    • Когда выполняется продукция специального вида:
  • i   i



i строится как

структурированная строка

, из следующего:

  • i строится как

    структурированная строка

    , из следующего:

    • символы

      T, не являющиеся скобками. Множество символов –

      T

      = T \ {

      (

      ,

      )

      }
    • конкретизационные скобки k

      и

      .

      (они могут сбалансировано появиться в строке в результате ее переработки)
    • выражения

      — произвольные последовательности символов и скобок, сбалансированные по скобкам, в том числе и пустые последовательности, и отдельные символы. Множество всех выражений –

      E

      = (

      T

      {

      (

      ,

      )

      }{

      k

      ,

      .

      })* , из которого удалены несбалансированные по скобкам строки
    • термы

      — либо отдельные символы, либо выражения, заключенные в простые или конкретизационные скобки. Множество всех термов обозначается как 

      W

      (

      W

      =(

      T

      (E)

      ))
    • символы переменных

      , различаются по видам
      • s-переменные:

        s1

        ,…,

        sNs

        — могут принимать в качестве значения только символы из перерабатываемой строки;
      • w-переменные:

        w1

        ,…,

        wNw

        — могут принимать в качестве значения только термы;
      • v- переменные:

        v1

        ,…,

        vNv

        — могут принимать в качестве значения только непустые выражения;
      • e-переменные:

        e1

        ,…,

        eNe

        — могут принимать в качестве значения произвольные (в том числе и пустые) выражения


Продукции Рефала принимают следующий вид:

  • Продукции Рефала принимают следующий вид:

  • k

    i

    .

    i (левая часть  правая часть)
  • где i (

    T

    E

    V

    SWVE)*, i (

    T

    E

    V

    SWVE{

    k

    ,

    .

    })*,
  • (i и i сбалансированы по скобкам).

  • Перерабатываемая строка (выражение) обрамляется конкретизационными скобками (технический прием)

  • 10 ... 23
    Карта сайта

    Последнее изменение этой страницы: 2018-09-09;



2010-05-02 19:40
referat 2018 год. Все права принадлежат их авторам! Главная