Как определить, может ли слово быть выведено в следующей грамматике, используя библиотеку стрелок Swiestra и Duponcheel? - PullRequest
Новая
       139

Как определить, может ли слово быть выведено в следующей грамматике, используя библиотеку стрелок Swiestra и Duponcheel?

4 голосов
/ 28 октября 2019

В этом посте: статья Джона Хьюза, о которой я собираюсь рассказать, - «Обобщение монад до стрел», 1998 (http://www.cse.chalmers.se/~rjmh/Papers/arrows.pdf);. Для определения грамматики я собираюсь использовать стандартную запись G = (N, T, P, S); Заглавные латинские буквы - нетерминалы; строчные латинские буквы - терминалы; строчные греческие буквы - элементы (N ⋃ T)*.

Я пытаюсь понять библиотеку разбора Swiestra и Duponcheel Arrow, но ямне не удается заполучить оператор секвенирования. Например: 

 Let G = ({S, H, E, L, O},
          {h, e, l, o},
          {S -> HELLO, 
           H -> h, 
           E -> e, 
           L -> l, 
           O -> o},
          S)

Давайте докажем, что это LL (1) -грамма: если мы рассмотрим нетерминальный X, есть правило (X -> α), но нет правила (X -> β), так как есть только одно правило, содержащее данный нетерминал слева (для каждого элемента N). Таким образом, follow-sets не имеет ничего для перехвата с .

Итак, как можно видеть, язык, производный от этой грамматики, состоит только из одного слова - L(G) = {hello}.

Это очень тривиальный пример, но я делаюне совсем понимаю, как я могу разобрать парсингr такого рода с использованием реализации Джоном Хьюзом оператора секвенирования для парсера Swiestra и Duponcheel с помощью стрелок (чтобы избежать утечки пространства O (n), которая возникает, когда мы реализуем парсер следующим образом:

wordParse = char 'h' >> char 'e' >> char 'l' >> char 'l' >> char 'o' >> return "hello").

РЕДАКТИРОВАТЬ: В случае, если я ошибаюсь из-за определения в скобках, вызывающего утечку пространства, что является общим смыслом идеи Суестры и Дюпоншила?

...