Пример 1.8. КС-грамматика действительного числа, то есть цепочек от полного представления числа, типа -123.567Е-21

КС-грамматика действительного числа, то есть цепочек от полного представления числа, типа -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.9. Автоматная грамматика действительного числа.

Число может начинаться с " + " или " - " и тогда оставшуюся часть числа резонно назвать числом без знака. Число также может начаться любой цифрой (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 ", т.е. цепочек без целой и дробной частей. На данном этапе проигнорируем этот факт, чтобы не усложнять грамматику. ™

Дата добавления: 2014-01-11