Информатика -продвинутый курс



         

МЕТАЯЗЫКИ ОПИСАНИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ - часть 2


означают, что в том (сугубо модельном) языке, на который эта метаформула распространяется, под термином <переменная> понимается любая из букв А или В, а под термином <выражение> - любая из следующих десяти записей: А; В; А+А; А+В; В+А; В+В; А-А; А-В: В-А; В-В Знак 1 следует читать «или».

Правая часть метаформулы может содержать правило построения допустимых последовательностей. Допускаются рекурсивные определения терминов и понятий, т.е. когда в правой части формулы участвует понятие, определяемое левой частью. Например, пусть необходимо ввести понятие <двоичный код>, под которым понимался любая непустая последовательность цифр 0 и 1. Тогда простое и компактное рекурсивное определение с помощью метаформул выглядит так:

<двоичная цифра>::= 0|1

<двоичный код>::=<двоичная цифра>|<двоичный код> <двоичная цифра>

Рекурсия здесь не мешает конструктивному построению понятия <двоичный код>, так как по принятым правилам при первом обращении к рекурсивно определяемому понятию следует ограничиться нерекурсивной частью формулы, т.е. под двоичным кодом понимать двоичную цифру - 0 или 1. Но при втором обращении к метаформуле, определяющей двоичный код, мы имеем варианты (конечно, неполные) понятия <двоичный код>, и можем применить рекурсию, которая даст нам следующие варианты этого понятия: 0 1 00 01 10 11, т.е. все возможные одно- и двухцифровые двоичные коды. Очевидно, что при следующих применениях рекурсии мы получим любой возможный двоичный код.

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

<двоичный код>::=<двоичная цифра><двоичная цифра>

И еще, для полноты множества синтаксических конструкций, необходимо определить конструкцию <пусто>:




Содержание  Назад  Вперед