![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Пример 1.4.
КС-грамматика действительного числа, то есть цепочек от полного представления числа, типа -123.567Е-21, до вырожденных: 0. или .1, т.е. в этом числе обязательна точка и хотя бы одна цифра в целой или дробной части. Терминалами здесь являются знаки - " + " и " - ", цифры от " 0 " до " 9 ", десятичная точка - ". " и символ " E ". То есть S = {+, -, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,., E }. В цепочке < число > можно выделить следующие основные компоненты: знак числа, целую часть, точку - ". ", дробную часть, символ " E ", знак порядка и само значение порядка. Отдельные компоненты или их группы могут отсутствовать. При таком разложении ". " и " E " - терминалы, а все остальное нетерминалы, требующие дальнейшей декомпозиции. Так < целая часть > - это одна цифра или несколько цифр, а < знак > - " + " или " - ". Нетрудно видеть, что знаки числа и порядка ничем не отличаются друг от друга и для них можно ограничиться одним понятием - знак. С точки зрения синтаксиса нет разницы и между целой частью, дробной частью и порядком и их вполне можно определить одно через другое. В результате имеем грамматику: (1) < число > ® < знак > < целая часть >.< дробная часть > Е < знак > < порядок> (2) < число > ® < целая часть >. < дробная часть > Е < знак > < порядок > (3) < число > ® < знак >. < дробная часть > Е < знак > < порядок > (4) < число > ® < знак > < целая часть >. Е < знак > < порядок > (5) < число > ® < знак > < целая часть >. < дробная часть > Е < порядок > (6) < число > ® < знак > < целая часть >. < дробная часть > (7) < число > ®. < дробная часть > Е < знак > < порядок > (8) < число > ® < целая часть >. Е < знак > < порядок > (9) < число > ® < целая часть >. < дробная часть > Е < порядок > (10) < число > ® < знак > < целая часть >. Е < порядок > (11) < число > ® < знак >. < дробная часть > Е < порядок > (12) < число > ® < целая часть >. < дробная часть > (13) < число > ® < знак >. < дробная часть > (14) < число > ® < знак > < целая часть >. (15) < число > ® < целая часть >. Е < порядок > (16) < число > ®. < дробная часть > Е < порядок > (17) < число > ® < целая часть >. (18) < число > ®. < дробная часть > (19) < целая часть > ® < цифра > < целая часть > (20) < целая часть > ® < цифра > (21) < дробная часть > ® < целая часть > (22) < порядок > ® < целая часть > (23) < цифра > ® 0 (24) < цифра > ® 1 (25) < цифра > ® 2 ....... (32) < цифра > ® 9 (33) < знак > ® + (34) < знак > ® - Используя БНФ (альтернативу и факультатив), эти 34 правила можно переписать в виде: < число > ® [ < знак > ] < целая часть >. [ < дробная часть > ] [ Е [ < знак > ] < порядок > ]ô [ < знак > ][ < целая часть > ] .< дробная часть > [ Е [ < знак > ] < порядок > ] < целая часть > ® < цифра > [ < целая часть > ] < дробная часть > ® < целая часть > < порядок > ® < целая часть > < цифра > ® 0 ô 1 ô 2 ô 3 ô 4 ô 5 ô 6 ô 7 ô 8 ô 9 < знак > ® + ô -. Техника построение А-грамматик определяется видом их правил, где в правой части первым должен стоять терминал. Для формирования таких правил просматриваются исходные цепочки, выписываются терминалы, которые можно встретить на очередном шаге, и вводятся нетерминалы, описывающие остаток цепочки. Созданные нетерминалы детализируются точно также как и исходный, то есть просматривается остаток цепочки и т.д. Пример 1.5. Автоматная грамматика действительного числа. Число может начинаться с " + " или " - ", и тогда оставшуюся часть числа резонно назвать числом без знака. Число также может начаться любой цифрой (0 - 9) и остаток цепочки будет тем же числом без знака. Наконец, число может начаться десятичной точкой ". ", и остаток такой цепочки уже иной. Если число без знака может в качестве продолжения содержать цифры и должно завершиться той же точкой, то после точки идет фрагмент цепочки, который точки уже не содержит. Есть смысл назвать этот фрагмент дробной частью и порядком. Рассуждая аналогичным образом, мы получим А-грамматику, где использованы следующие сокращения для имен нетерминалов: чис - число, чбз - число без знака, дчп - дробная часть и порядок, пор - порядок, пбз - порядок без знака: < ч > ® +< чбз > ô -< чбз > ô 0< чбз > ô 1< чбз > ô ... ô 9< чбз > ô .< дчп > < чбз > ® 0< чбз > ô 1< чбз > ô ... ô 9< чбз > ô .< дчп > ô. < дчп > ® 0< дчп > ô 1< дчп > ô ... ô 9< дчп > ô 0 ô 1 ô ... ô 9 ô E< пор > < пор > ® +< пбз > ô -< пбз > ô 0< пбз > ô 1< пбз > ô ... ô 9< пбз > ô 0 ô 1 ô ... ô 9 < пбз > ® 0< пбз > ô 1< пбз > ô ... ô 9< пбз > ô 0 ô 1 ô ... ô 9.
Данная грамматика допускает порождение совсем уж вырожденных цепочек, типа " -. " или " .Е1 ", т.е. цепочек без целой и дробной частей. На данном этапе проигнорируем этот факт, чтобы не усложнять грамматику.
|