mayton Тема - комбинаторная логика (КЛ). Опущу детали. Интересущиеся почитают книжку Душкина или Вики.
Или более фундаментальные труды Хаскелла Карри. Вкратце.
эээээ.... как бы сказать помягче.
Не надо их читать. Есть намного более лучшие, понятные и поступательно развивающие тему книги.
Можешь начать с Michael Sipser, Introduction to the Theory of Computation.
Душкина я не листал, но судя по нестандартности терминов которые ты использовал - читать его не надо.
А Curry тут слегка не в тему, тебя зацепил разбор грамматик, а у Curry это мизерный этап, к Curry надо приходить уже хорошо разбираясь в грамматиках.

Ну это что касается теории...

mayton Ради чего я всё это делаю.

1) Ну во первых - Just For Fun. Ради удовольствия. Ради spend time.
2) Во вторых, чтобы освоить интересный раздел ФП и применить эти знания
в будущем в других смежных областях. В обработке текста.
3) Попутно поковырять С/C++ и трансляторы и запилить свой собственный "deqaws" или
обфускатор.

Вопрос первый, ты очень огорчишься если я ткну пальцем в Yacc/Bison и скажу что эти приложения как раз и делают то о чем ты говоришь? :)
А еще есть целый язык OCaml в котором разбор грамматик является фичей встроенной в сам язык. И мне сильно кажется что всего Верблюда именно ради этого и делали. Очень уж легко на нем делать трансляторы, за счет всего остального...

mayton В чём пока еще я не разобрался
Как доказать конечность комбинаций? Возможны ли зацикливания и рекурсии?Конечность? А что ты под этим понимаешь?

И да, рекурсии возможны.
Вот тебе рекурсия:
A = Aa | ɛ
А зацикливания невозможны.

Зато могут быть проблемы неоднозначности:
A = ba|Ba
B = b
В этом случае строку "ba" можно описать двумя разными путями.

maytonКак постулировать "число" и "операции" над ним?
NUMBER = DIGIT | NUMBER DIGIT
DIGIT = 0|1|2|3|4|5|6|7|8|9

OPERATIONS = NUMBER OPERATOR NUMBER | OPERATIONS OPERATOR NUMBER
OPERATOR = + | - | * | /


maytonКак синтезировать строительные блоки - DO,WHILE,IF,IF-ELSE и использовать их?
STATEMENTS = STATEMENTS STATEMENT | STATEMENT
STATEMENT = WHILE_DO | DO_WHILE | IF_BLOCK | SOME_OTHER_PRIMITIVES
WHILE_DO = WHILE CONDITION DO STATEMENTS LOOP
DO_WHILE = DO STATEMENTS WHILE CONDITION
CONDITION = LOGIC_OPERAND LOGIC_OPERATOR LOGIC_OPERAND



maytonСуществует ли "контекст" аппликаций?Нет, по определению.
Вспоминай как все это называется... Хотя... Судя по "комбинаторам" и "аппликациям" Душкин не смог найти стандартные названия "терминалы" и "правила".
В общем намекаю: в нормальной литературе это называется "Context Free Grammar"...

maytonКак "оптимизировать" строковые замены?Никак. Если некоторая цепочка распознавания может быть оптимизирована - значит строку можно распознать двумя способами, оптимизированным и не оптимизированным. А значит у нас появляется неоднозначность которая совершенно недопустима.

Dima TПогуглил
Комбинаторная логика
Комбинаторы — это просто!

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

maytonКонечность? А что ты под этим понимаешь?

И да, рекурсии возможны.
Вот тебе рекурсия:
A = Aa | ɛ
А зацикливания невозможны.

Я здесь не понимаю что обозначает символ |
И не понимаю как толковать комбинатор А. Символ "|" означает "или".
В сумме это все читается:
Правило А это Правило А и символ "a" или пустая строка.
На практике - любая строка состоящая из нескольких (от нуля до бесконечности) символов "a".

maytonЭта книга?
http://cglab.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf
Нет, на моей книжной полке стоит другая (ISBN 9780534950972), но судя по оглавлению это тоже можно читать.

Хотя я бы поставил третью главу после четвертой и пятой. Мне кажется что надо сначала разобраться что такое определяемые и неопределяемые языки (пятая глава) прежде чем браться за внеконтестную грамматику. Но большинство учебников (включая Сипсера) со мной не согласны .... Но это мелочи на самом деле :)

maytonNUMBER = DIGIT | NUMBER DIGIT
DIGIT = 0|1|2|3|4|5|6|7|8|9

OPERATIONS = NUMBER OPERATOR NUMBER | OPERATIONS OPERATOR NUMBER
OPERATOR = + | - | * | /
Нет нет. Это не то.
....
Меня-же интересует другое. Формализация операций над целыми. Через индукцию.

Например:




Вобщем вроде как то вот так.Вот это как раз оно и есть.
Если ты хочешь еще и скобки и знак равенства распознавать, то просто чуть усложняешь уже показанные правила:
OPERATIONS = ( OPERATIONS ) | NUMBER OPERATOR NUMBER | OPERATIONS OPERATOR NUMBER | NUMBER
LOGIC_OPERATION = OPERATIONS LOGIC_OPERATOR OPERATIONS
LOGIC_OPERATOR = = | < | > | and | or
И все.


mayton Данная форма ЕМНИП называется ЕБНФ или разновидность ее.
И кажется надо ставить не равно а двоеточие и равно "::=".
Я не знаю что такое ЕБНФ, извините. А двоеточие или равенство это не так уж важно, это зависит от используемого парсера (и учебника). В большинстве случаев правила определяются вообще стрелочкой, но я не помню ю-код символа "стрелочка", так что использовал знак равенства. Ну извините.

maytonНикак. Если некоторая цепочка распознавания может быть оптимизирована - значит строку можно распознать двумя способами, оптимизированным и не оптимизированным. А значит у нас появляется неоднозначность которая совершенно недопустима.
Возможно я другое имел в виду. К примеру если я строю некую комбинаторную
машину, то я расчитываю что в выражении


при выполнении аппликаций я вынужден буду либо выполнять поочерёдно
всю последовательность нужных преобразований внутри строки либо
строить доп. структуры данных (бинарные деревья) для оптимизации
вычислений (особенно если формула будет в 100 или в 10000 крат
превышать образец который я привёл выше).ээээээ......
Во первых, ты никаких преобразований внутри строки не делаешь.
Во вторых, оптимизация вычислений это вещь совершенно отдельная от разбора строки.
Разбор строки это всегда превращение строки в дерево (не бинарное!). А что ты будешь делать с этим деревом потом, это уже совершенно другой вопрос и к собственно к процессу построения дерева не относится.

maytonАга. Вот эта? http://www.amazon.co.uk/dp/0534950973 yes