P′′
P′′ — низкоуровневый язык программирования, созданный в 1964 году Коррадо Бёмом.
Определение
P′′ формально определяется как набор слов алфавита из 4 инструкций {R, λ, (, )} следующим образом:
Синтаксис
- R и λ — слова.
- Если p и q — слова, то pq — слово.
- Если q — слово, то (q) — слово.
- Остальные последовательности символов не являются словами.
Семантика
{a0, a1, ..., an} (n ≥ 1)
— алфавит бесконечной ленты (аналогичной ленте машины Тьюринга),a0
- пустой символ.- R — перенос головки ленты на одну ячейку вправо.
- λ — заменить текущий символ
ai
наai+1
(an
заменяется наa0
) и переместить головку на одну ячейку влево. - (q) — повторять операцию (операции) q, пока значение текущей ячейки не равно
a0
. - Операции выполняются слева направо в том порядке, в котором они записаны, до тех пор, пока справа ничего не останется.
Дополнительные факты
- P′′ — первый полный по Тьюрингу язык программирования без оператора GOTO.
- Команды языка Brainfuck (за исключением ввода и вывода) могут быть переведены на P′′ и обратно:
Brainfuck | P′′ |
---|---|
> | R |
< | L=r'λ |
+ | r=λR |
- | r'=rrrrr...rr (n раз) |
[ | ( |
] | ) |
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.