Реферат: Алгоритм нисходящего разбора. Нисходящие распознаватели

це, о своих сыновьях, а также о своем месте в грамматике и выходной це-

почке. И никому не нужны точные сведения о том, что происходит в других

местах. Это как раз и есть то, к чему мы вообще стремимся в программиро-

вании: в каждом сегменте программы или в подпрограмме необходимо забо-

титься о собственной входной и выходной информации и ни о чем более.

Для имитации усыновления и отречения сыновей в программах использу-

ют стек типа LIFO (последний вошел - первый вышел), или, как его иногда

называют, "магазин".

Опишем алгоритм в более явном виде:

Положим, во-первых, что грамматика задана списком в одномерном мас-

сиве GRAMMAR таким образом, что каждое множество правил

U ::= x|y|...|z

представлено, как Ux|y|...|z|$. То есть каждый символ занимает одну

ячейку, за каждой правой частью следует вертикальная черта "|", а за

последним символом следует "|$". Таким образом, грамматика

Z ::= E#

E ::= T+E|T

T ::= F*T|F

F ::= (E)|i

будет выглядеть как

ZE#|$ET+E|T|$TF*T|F|$F(E)|i|$

Каждый элемент стека соответствует человеку и состоит из пяти

компонент

(GOAL,i,FAT,SON,BRO)

которые означают следующее:

1. GOAL - цель, т.е. символ, который человек ищет. Таким обра-

зом, в незакрытой в данный момент части предложения ему предстоит

найти такую голову, которая приводится к GOAL, и закрыть ее. GOAL

передается ему отцом.